python - 向量化列表理解中的嵌套 for 循环

Question

我有两个字符串列表，用于计算 Damerau–Levenshtein 距离 检查哪些是相似的。我列出的问题超过 200k+，并且理解它需要相当多的时间。对于距离计算，我使用 pyxDamerauLevenshtein 包，它是用 Cython 编写的，因此应该没有瓶颈

series = ([damerau_levenshtein_distance(i, j) for i in original_string for j in compare_string])

这就是我的代码的样子，我想知道是否可以以某种方式对其进行矢量化以提高性能，或者也许采用其他方式来加速计算？

我的数据集是什么:

原始字符串 - 它是 pd.一系列独特的街道名称

比较字符串 - 这是 pd.一系列手动输入的街道名称，我想比较它们以查找相似性

输出应该是这样的:

   Original    Compare   Distance
0  Street1     Street1      1
1  Street2     Street1      2
2  Street3     Street1      3
3  Street4     Street3      5
4  Street5     Street3      5
5  Street6     Street6      1

Answer 1

如果您能想到一种使用map(或imap)函数而不是嵌套循环的方法，那么您可以尝试使用multiprocessing充分利用您的CPU。例如，在本例中:

pool.map(lambda j: map(lambda i: damerau_levenshtein_distance(i, j),original_string),compare_string) 

其中“pool.map”是多处理映射，第二个“map”是常规映射。

下面是一个快速但实用的多处理示例，它可以涵盖您正在寻找的内容。我对它的结构有点不同，以避免一些酸洗问题，并让它在后台稍微异步计算，因为你的列表很长......
(这绝对可以改进，但希望可以作为您的示例的概念验证)

import multiprocessing as mp
import itertools

list1 = range(5)
list2 = range(5)

def doSomething(a,b):
    return a+b #Your damerau_levenshtein_distance function goes here

def mapDoSomething(args):
    i = args[0] #An element of list2
    otherlist = args[1] #A copy of list1
    return [doSomething(i,j) for j in otherlist]

if __name__ == '__main__':
    pool = mp.Pool()
    answer = pool.imap(mapDoSomething,zip(list2,itertools.repeat(list1)))
    print(list(answer)) #imap will compute the results in the background whilst the rest of the code runs. You can therefore ask for individual lists of results, and it won't block unless the result hasn't been computed yet. To do this, you would use answer.next() or iterate over the results somewhere else. However, by converting to a list here, I'm forcing all results to finish before printing. This is only to show you it worked. For larger lists, don't do this.
    pool.close()
    pool.join()

这段代码产生:

[[0, 1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [3, 4, 5, 6, 7], [4, 5, 6, 7, 8]]

list1 的每个元素与 list2 的每个元素一起操作(我添加了它们)，我认为这就是您在代码中尝试使用字符串列表执行的操作。

代码设置了进程池，然后使用 imap 将对 list2 进行操作的处理拆分到多个进程中。 zip 函数延迟地将 list2 的元素与 list1 的完整副本分组，因为 imap 仅支持具有单个参数的函数。然后，该组被拆分并在 mapDoSomething 中使用，后者对 list1 中的每个元素和 list2 中的每个元素运行 doSomething 函数。

由于我使用了 imap，列表在计算后就会立即打印出来，而不是等待整个结果完成。