Cython 中稀疏矩阵的快速访问：Memoryview 与字典向量的比较

Question

我使用了Cython来加速Python中的瓶颈。任务是计算稀疏矩阵的选择性逆（下面的S），其由csc格式（数据，indptr，indices）给出的Cholesky分解所确定。但这个任务并不是真正重要的，最终它只是一个3层嵌套的for循环，在其中我必须快速访问S的元素。

当我使用一个完整/巨大矩阵的memoryview时，...

double[:,:] Sfull

如果能够访问这些条目，那么算法会非常快，并且符合我的期望。但很明显，只有当矩阵Sfull适合内存时才有可能做到这一点。

我的方法是使用字典/映射的列表/向量，这样我也可以相对快速地访问元素。

cdef vector[map[int, double]] S

事实证明，使用该数据结构在循环内部访问元素的速度大约慢了20倍。这是否符合预期或存在其他问题？您能否看到其他数据结构可供选择？

非常感谢任何意见或帮助！ 最好的祝福， Manuel

下面是Cython代码，其中版本包含完整的内存视图已被注释掉。

cdef int invTakC12( double[:] id_diag, double[:] data, int len_i, int[:] indptr, int[:] indices, double[:, :] Sfull):


cdef vector[map[int, double]] S = testDictC(len_i-1) #list of empty dicts
cdef int i, j, j_i, lc
cdef double q 




for i in range(len_i-2, -1, -1):

    for j_i in range(indptr[i+1]-1, indptr[i]-1, -1):
        j = indices[j_i]

        q = 0

        for lc in range(indptr[i+1] -1, indptr[i], -1):

            q += data[lc] * S[j][ indices[lc] ]
            #q += data[lc] * Sfull[ indices[lc], j ]
  
        S[j][i] = -q
        #Sfull[i,j] = -q
        

        if i==j:
            S[j][i] +=  id_diag[i]
            #Sfull[i,j] += id_diag[i]
        else:
            S[i][j] -=  q
            #Sfull[j,i] -= id_diag[i]
    

return 0

- Delgado

---

你可能会发现使用unordered_map比map更好。对于许多操作来说，它更快。 - DavidW

Answer 1

您可以独立访问数组 - 例如：

cdef double[:] S_data = S.data
cdef np.int32_t[:] S_ind = S.indices
cdef np.int32_t[:] S_indptr = S.indptr

如果这样太不方便，你可以将它们作为指针放入C结构中：

cdef struct mapped_csc:
    double *data
    np.int32_t *indices
    np.int32_t *indptr

- anymous.asker