更快蟒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