cython中稀疏矩阵的快速存取：记忆视图与字典向量

Question

我使用了cython来加速python的瓶颈。该任务是计算由csc格式（数据、indptr、索引）提供的cholesky分解给出的稀疏矩阵的选择性逆（S以下）。但是这个任务并不重要，最终它是一个3次嵌套的for循环，我必须访问S fast的元素

当我使用完整/巨大矩阵的记忆视图时

double[:,:] Sfull

然后访问条目，算法非常快，符合我的期望。但很明显，只有当矩阵Sfull适合内存时，这才可能实现

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

cdef vector[map[int, double]] S

事实证明，使用这种数据结构访问循环中的元素的速度要慢20倍左右。这是预料之中的还是存在其他问题？您是否看到其他数据结构

非常感谢您的任何意见或帮助！ 最好的 曼努埃尔

下面是cython代码，其中带有完整memoryview的版本被注释掉

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

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