元素智能访问非常大的稀疏矩阵的有效结构(Python/Cython)

Question

我正在寻找一种有效的数据结构来表示Python/Cython中非常大的整数矩阵,重点关注元素操作.

我目前正在构建一个模型,该模型需要在大型高度稀疏矩阵上进行大量元素操作(在2MMx500k矩阵上读取/写入大约500亿次).以前我在较小的数据上运行实验,并使用Python与Cython和Numpy数组,并且理想情况下将继续使用现有基础结构的某些部分.

到目前为止我已查看/实施了许多选项.它们可能没有完全优化,但所有实现都应该足够好,以便对每种方法的潜力给出切合实际的想法.我已经通过创建一个2MMx500k矩阵进行测试,添加了25MM元素,然后再次删除它们.这反映了我需要的那种操作.

29 minutes: Cython lists to fill scipy.sparse.coo -> sparse.dok 
10 minutes: Cython lists to fill scipy.sparse.coo -> sparse.lil 
 3 minutes: Dict, s.t. A["%d_%d" % (i,j)] contains M[i][j]
 3 minutes: Dict, s.t. A[(i,j)] contains M[i][j]
<1 minute:  Dict, s.t. A[i*N,j] contains M[i][j]
<1 minute:  <std::map> using Cython

到目前为止,黑客攻击一个词典表现最好,但仍然相当慢.这也感觉太糟糕了,所以我假设必须有一个更有效的方法,特别是考虑到dict解决方案并没有真正使用任何潜在的Cython可以提供.是否有更多的Cythonic解决方案？不幸的是,谷歌并没有太大的帮助(或者我没有正确的搜索关键词).

任何有关如何做到这一点的建议将不胜感激!

编辑1

两个字典解决方案之间的区别在于A ["%d_%d"%(i,j)]变体访问速度更快,而A [(i,j)]变体的设置速度更快.

                                                  Setup    Execution
Dict, s.t. A["%d_%d" % (i,j)] contains M[i][j]    180s      30s
Dict, s.t. A[(i,j)] contains M[i][j]               66s     104s
Dict, s.t. Dict, s.t. A[i*N,j] contains M[i][j]    40s       8s

虽然A ["%d_%d"%(i,j)]在当前测试中稍微慢一点,但从长远来看,最好是因为设置成本只会增加10倍,执行成本为我的实际实验因子10,000x.

编辑2

我可以通过删除字符串操作来进一步加速字典版本,而是使用大整数表示,通过在第一个上使用适当大的乘数来连接两个索引以避免冲突.使用cdef输入乘法:

cdef unsigned int key(int a, int b): return a * 10000000 + b

通过优化字典或将数据结构移动到C可能仍然可以进一步提高速度,但这应该足够快以达到我的目的.不过,任何其他建议仍然非常受欢迎!如果我找到使用stl映射或类似数据结构的更有效的解决方案,将报告回来.

编辑3

根据同事的建议,我还使用<std::map>它的Cython接口实现了系统,将数据存储在<int,int>地图中.dict一旦我们拥有大量数据,实施实际上比实施速度稍慢,关键区别在于访问速度:

                  Small data (25MM elements)         Large data (250MM elements)
          Time    total    setup    read/write       total    setup    read/write
Dict[int keys]      40s      25s       8s             369s     269s      72s
<std::map>          26s      11s      12s             376s     169s     177s

Answer 1

如果您不进行基于行或基于列的访问，则可以使用带有元组键（如 ）的字典A[(i,j)]。