Python在大矩阵中找到相似向量的最快方法

Question

我正在尝试编写一个Python函数，它接受一个向量（1x128），然后在一个大的未排序矩阵（2000x128）中找到最相似的列。该函数在应用程序中调用了约 100000 次。当我在台式电脑上工作时没有问题，但在树莓派上工作速度非常慢。这是我的功能；

def find_similar_index(a):
    d = []
    norma=np.linalg.norm(a)
    for i in range(0, 1999):
        d.append(np.abs(np.linalg.norm(a - A[:, i]))/norma)
    return np.argmin(d)

我可以改进此功能中的任何内容以加快工作速度吗？我可以使用Raspberry Pi的GPU进行这种计算吗？

Answer 1

这是一种使用broadcasting和 的方法np.einsum-

\n\n

subs = (a[:,None] - A)\nsq_dist = np.einsum(\'ij,ij->j\',subs, subs)\nmin_idx = np.abs(sq_dist).argmin()\n

\n\n

sq_dist使用公式的另一种方法(a-b)^2 = a^2 + b^2 - 2ab-

\n\n

sq_dist = (A**2).sum(0) + a.dot(a) - 2*a.dot(A) \n

\n\n

有了np.einsum，这将提升为 -

\n\n

sq_dist = np.einsum(\'ij,ij->j\',A,A) + a.dot(a) - 2*a.dot(A)\n

\n\n

另外，由于我们只对最近的索引以及距离的最终结果感兴趣，np.linalg.norm给定输入数组中的实数，我们可以跳过np.abs并跳过按比例缩小的过程norma。

\n\n

运行时测试

\n\n

方法 -

\n\n

def app0(a,A): # Original approach\n    d = []\n    for i in range(0, A.shape[1]):\n        d.append(np.linalg.norm(a - A[:, i]))\n    return np.argmin(d)\n\ndef app1(a,A):\n    subs = (a[:,None] - A)\n    sq_dist = np.einsum(\'ij,ij->j\',subs, subs)\n    return sq_dist.argmin()\n\ndef app2(a,A):\n    sq_dist = (A**2).sum(0) + a.dot(a) - 2*a.dot(A) \n    return sq_dist.argmin()\n\ndef app3(a,A):\n    sq_dist = np.einsum(\'ij,ij->j\',A,A) + a.dot(a) - 2*a.dot(A)\n    return sq_dist.argmin()\n

\n\n

因为，您提到 isvector的形状(1x128)，并且您正在寻找A该向量中的类似列，所以似乎每列都有长度128，因此我假设它A是 shape (128, 2000)。有了这些假设，这里是使用列出的方法的设置和计时 -

\n\n

In [194]: A = np.random.rand(128,2000)\n     ...: a = np.random.rand(128)\n     ...: \n\nIn [195]: %timeit app0(a,A)\n100 loops, best of 3: 9.21 ms per loop\n\nIn [196]: %timeit app1(a,A)\n1000 loops, best of 3: 330 \xc2\xb5s per loop\n\nIn [197]: %timeit app2(a,A)\n1000 loops, best of 3: 287 \xc2\xb5s per loop\n\nIn [198]: %timeit app3(a,A)\n1000 loops, best of 3: 291 \xc2\xb5s per loop\n\nIn [200]: 9210/287.0 # Speedup number\nOut[200]: 32.09059233449477\n

\n