针对超大稀疏矩阵的高效逐元素访问结构（Python/Cython）

Question

我正在寻找一种高效的数据结构，用于在Python/Cython中表示一个非常大的整数矩阵，重点是元素级的操作。

我现在正在构建一个模型，需要对一个非常大的、稀疏的矩阵进行大量的元素级操作（大约在一个2百万乘50万的矩阵上进行500亿次读写）。之前我在较小的数据上进行过实验，使用了Python、Cython和Numpy数组，理想情况下我希望继续使用现有的一些基础设施。

我已经查看和实现了一些选项。虽然它们可能没有完全优化，但所有的实现都足够好，可以给出每种方法潜力的真实想法。我通过创建一个2百万乘50万的矩阵，添加2500万元素，然后再将它们移除来进行测试。这反映了我需要的操作类型。

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

目前，拼凑一个字典的方式表现最好，但仍然相当慢。而且这感觉像是一个临时解决方案，所以我认为一定有更高效的方法，特别是考虑到字典的解决方案并没有真正利用Cython的潜力。不知道有没有更符合Cython风格的解决方案？可惜谷歌没有提供太多帮助（或者我没有找到正确的搜索关键词）。

如果有任何建议，我将非常感激！

编辑 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,000倍，这对我的实际实验来说。

编辑 2

我可以通过去掉字符串操作，改用一个大的整数表示法来进一步加速字典版本，方法是将两个索引用一个合适的大乘数连接在一起，以避免冲突。乘法是用cdef类型定义的：

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

通过优化字典或将数据结构移到C中，可能仍然有进一步提高速度的可能，但这对于我的目的来说应该已经足够快了。如果还有其他建议，我仍然非常欢迎！如果我找到使用stl map或类似数据结构的更高效的解决方案，会再回来报告。

编辑 3

根据同事的建议，我还通过Cython接口实现了使用<std::map>的系统，将数据存储在<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)]。