更快蟒Scipy CSR“向量”之间的余弦差异

Question

这是一个经典问题，但我相信很多人仍然在寻找答案。 这个问题是不同于this one，因为我的问题是两个稀疏向量（不是矩阵）之间的操作。

我写了一个blog post关于余弦Scipy空间距离（SSD）如何在数据维数越来越高（因为它适用于密集向量）时变慢。这篇文章是印度尼西亚语，但是我的实验设置&的结果应该很容易理解，不管语言如何（在帖子的底部）。

目前这种解决方案是用于高维数据的速度超过70倍（相比于SSD）&多个存储器高效：

import numpy as np 

    def fCosine(u,v): # u,v CSR vectors, Cosine Dissimilarity 
     uData = u.data; vData = v.data 
     denominator = np.sqrt(np.sum(uData**2)) * np.sqrt(np.sum(vData**2)) 
     if denominator>0: 
      uCol = u.indices; vCol = v.indices # np array 
      intersection = set(np.intersect1d(uCol,vCol)) 
      uI = np.array([u1 for i,u1 in enumerate(uData) if uCol[i] in intersection]) 
      vI = np.array([v2 for j,v2 in enumerate(vData) if vCol[j] in intersection])    
      return 1-np.dot(uI,vI)/denominator 
     else: 
      return float("inf") 

是否有可能进一步提高其功能（Python化或通过JIT /用Cython ???）。

Answer 1

下面是一个替代方案中，alt_fCosine，其中（我的机器上）可以尺寸10**5的CSR载体和10**4非零元素约3倍更快：

import scipy.sparse as sparse 
import numpy as np 
import math 

def fCosine(u,v): # u,v CSR vectors, Cosine Dissimilarity 
    uData = u.data; vData = v.data 
    denominator = np.sqrt(np.sum(uData**2)) * np.sqrt(np.sum(vData**2)) 
    if denominator>0: 
     uCol = u.indices; vCol = v.indices # np array 
     intersection = set(np.intersect1d(uCol,vCol)) 
     uI = np.array([u1 for i,u1 in enumerate(uData) if uCol[i] in intersection]) 
     vI = np.array([v2 for j,v2 in enumerate(vData) if vCol[j] in intersection])    
     return 1-np.dot(uI,vI)/denominator 
    else: 
     return float("inf") 

def alt_fCosine(u,v): 
    uData, vData = u.data, v.data 
    denominator = math.sqrt(np.sum(uData**2) * np.sum(vData**2)) 
    if denominator>0: 
     uCol, vCol = u.indices, v.indices 
     uI = uData[np.in1d(uCol, vCol)] 
     vI = vData[np.in1d(vCol, uCol)] 
     return 1-np.dot(uI,vI)/denominator 
    else: 
     return float("inf") 

# Check that they return the same result 
N = 10**5 
u = np.round(10*sparse.random(1, N, density=0.1, format='csr')) 
v = np.round(10*sparse.random(1, N, density=0.1, format='csr')) 
assert np.allclose(fCosine(u, v), alt_fCosine(u, v)) 

alt_fCosine可取代两个列表解析，向呼叫np.intersection1d 并形成一个Python集，其中两个调用np.in1d和高级 索引。

---

对于N = 10**5：

In [322]: %timeit fCosine(u, v) 
100 loops, best of 3: 5.73 ms per loop 

In [323]: %timeit alt_fCosine(u, v) 
1000 loops, best of 3: 1.62 ms per loop 

In [324]: 5.73/1.62 
Out[324]: 3.537037037037037