2

我是 python 新手，我正在一个包含 200 万条记录的列表上运行一个模糊的字符串匹配逻辑。该代码正在运行，并且它也正在提供输出。问题是它非常慢。在 3 小时内它只处理 80 行。我想通过一次处理多行来加快速度。

如果它有帮助 - 我在我的机器上运行它，配备 16Gb RAM 和 1.9 GHz 双核 CPU。

下面是我正在运行的代码。

d = []
n = len(Africa_Company) #original list with 2m string records
for i in range(1,n):
    choices = Africa_Company[i+1:n]
    word = Africa_Company[i]
    try:
        output= process.extractOne(str(word), str(choices), score_cutoff=85)
    except Exception:
        print (word) #to identify which string is throwing an exception
    print (i) #to know how many rows are processed, can do without this also
    if output:
        d.append({'Company':Africa_Company[i], 
                  'NewCompany':output[0],
                  'Score':output[1], 
                  'Region':'Africa'})
    else:
        d.append({'Company':Africa_Company[i], 
                  'NewCompany':None,
                  'Score':None, 
                  'Region':'Africa'})


Africa_Corrected = pd.DataFrame(d) #output data in a pandas dataframe

提前致谢 ！

4

1 回答 1

6

这是一个受 CPU 限制的问题。通过并行，您最多可以将其加速两倍（因为您有两个内核）。你真正应该做的是加快单线程性能。Levenshtein 距离很慢，所以有很多机会可以加快速度。

  1. 使用修剪。不要试图在两个字符串之间运行完全模糊匹配，如果没有办法给出一个好的结果。尝试找到一个简单的线性算法，在模糊匹配之前过滤掉不相关的选择。
  2. 考虑索引。有什么方法可以索引你的列表吗？例如：如果您的匹配基于整个单词，请创建一个将单词映射到字符串的 hashmap。仅尝试匹配与当前字符串至少有一个单词相同的选项。
  3. 预处理。在您可以预处理的每场比赛中，是否对字符串进行了一些工作？例如，如果您的 Levenshtein 实现首先从您的字符串创建集合，请考虑首先创建所有集合，这样您就不必在每次匹配中一遍又一遍地做同样的工作。
  4. 有没有更好的算法可以使用？也许 Levenshtein 距离并不是最好的算法。
  5. 您使用的 Levenshtein 距离的实施是否最佳？这又回到了第 3 步（预处理）。您还可以采取其他措施来加快运行时间吗？

多处理只会以恒定的因素加速（取决于内核的数量）。索引可以带您进入较低复杂度的课程！因此，首先关注修剪和索引，然后是步骤 3-5。只有当您从这些步骤中挤出足够多的时间时，您才应该考虑多处理。

于 2017-01-10T14:50:54.913 回答