我在np.array中使用字符串，它有N^2的复杂度，对于10k行和10列，它需要1个多小时，它太慢了，但我无法想象如何加速它
有一个2D阵列，如：
X = np.array([['asd', 'qwe'], ['asd', 'rty']])但有几个更大的
哪种方法是创建所有行之间的成对距离的最快方法？
现在我用
from Levenshtein import ratio
#normalized levenshtein distance = levenshtein/(len(1st word)+len(2nd word))
vectorRatio = np.vectorize(ratio)
Q = np.zeros((len(X), len(X)))
for i in range(len(X)):
for j in range(len(X)):
Q[i][j] = 10 - sum(vectorRatio(X[i],X[j]))
1条答案
按热度按时间a11xaf1n1#
请注意，
np.vectorize并不是真正的矢量化，也不是为了提高性能，它基本上是一个for循环，它仍然比纯for循环快，因为for循环本身是用C语言完成的，但它的内容仍然只是纯python函数的调用。也就是说，您没有使用
np.vectorize的优势（不是很大）。您有3个嵌套循环（2个在行上，1个在列上），只有最后一个是由"矢量化"函数完成的。其他两个也可以是。的内部循环
例如，可以很容易地
虽然不太明显，但是通过一些广播，您还可以调用let外部循环来执行vectorRatio
X[None,...]是一个包含了一个二维数组的数组，这个二维数组就是你原来的X，而X[:,None,:]是一个由len(X)数组组成的数组，每一行都有1xlen(X)数组，所以，广播强制复制所有的行，把所有的行组合起来，有点像np.arange(10).reshape(-1,1) + np.arange(10,20).reshape(1,-1)，它产生了一个二维数组，这个二维数组包含了一对[0，10）中的一个数和[10，20年）所以，没有for循环了。
但是，
vectorRatio实际上只是为每对字符串调用ratio，所以在这个例子中，2 × 2 × 2 = 8次，在你的实际情况中，10000 × 10000 × 10 = 10亿次，np.vectorize的向量化只是加速了for本身（计数），而不是对ratio的10亿次调用。时间
| 案件|您的代码|无for循环|
| - ------|- ------|- ------|
| 2行2列|162微秒|51微秒|
| 10行10列|4.25毫秒|0.70毫秒|
| 100行10列|425毫秒|65毫秒|
| 1000行10列|43秒|6.5秒|
因此，可以肯定地说（毫不奇怪）它是一个O（n ²），对于你的10k/10情况，你的代码需要4300秒，而我的代码需要650秒。
这不是一个很大的增益系数（相比之下，我们在矢量化代码时通常获得的增益系数远远超过1000）。因为，同样，这不是一个真正的矢量化。但好吧，这仍然是1小时的等待节省了1小时10分钟的计算。