Python 将方法应用于来自两个大型列表的元素对需要很长时间才能处理

Question

我有两个包含字符串的列表 - 两个列表的大小通常为 100,000 甚至更多。

我还有一个方法，它接受两个字符串并测量它们的相似度距离。我试过嵌套循环，例如

Results=[]
for i in list_1:
   for j in list_2:
      Results.append( (i, j, edit_distance(i, j)) )

问题是由于比较次数多，这段代码需要很长时间才能处理。我也尝试过 zip() 方法，但仍然需要很长时间。有没有办法使这种比较更快？

Answer 1

循环不是你的问题。为每对字符串调用 edit_distance 几乎占用了您所有的运行时间，因此这是您应该首先考虑提高性能的地方。

根据您发布的内容，您可以做出的最佳改进是将循环变成生成器以降低生成 100,000x100,000 元素列表的成本：

import itertools

def edit_distances(list1, list2):
    for i, j in itertools.product(list1, list2):
        yield (i, j, edit_distance(i, j))

Answer 2

正如 Woodford 已经建议的那样，您可以使用生成器做得更好 -- 如果您只需要通过某种迭代访问这些数字一次。如果您需要多次或以其他顺序索引或引用它们，那么您将需要完整的 table.

您的大部分时间可能浪费在扩大 10^10 个元素的列表上，一次一个元素。此外，如果这是一个行为良好的距离函数，那么您知道 f(i, j) == f(j, i) 和 f(i, i) == 0，因此您可以缩短计算时间如果您避免冗余计算，则略多于一半。

如果i == j，填0，不调用函数
记忆你的函数：如果 i > j，获取 f(j, i) 的存储值而不是重新计算。
用理解构建列表，而不是 10^10 append 次操作。

结果 = [0 如果我 == j 否则存储 [(j_str, i_str)] 如果 i > j 否则 edit_distance(i_str, j_str) 对于我，i_str 在 list_1 对于 j，j_str 在 list_2 ]

这里假设edit_distance负责更新内存stored。您可以在任何有关记忆的教程（以及有关动态规划的大多数参考资料）中找到详细信息。

Python applying a method to elements pairs from two large lists take long time to process