我使用了Cython来加速Python中的瓶颈。任务是计算稀疏矩阵的选择性逆(下面的S),其由csc格式(数据,indptr,indices)给出的Cholesky分解所确定。但这个任务并不是真正重要的,最终它只是一个3层嵌套的for循环,在其中我必须快速访问S的元素。
当我使用一个完整/巨大矩阵的memoryview时,...
如果能够访问这些条目,那么算法会非常快,并且符合我的期望。但很明显,只有当矩阵Sfull适合内存时才有可能做到这一点。
我的方法是使用字典/映射的列表/向量,这样我也可以相对快速地访问元素。
当我使用一个完整/巨大矩阵的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
unordered_map
比map
更好。对于许多操作来说,它更快。 - DavidW