Python稀疏坐标列表的数据结构

Question

想象一下，我们有一组 x/y 坐标和一个字节的 'count'。这些 x/y 坐标的范围大概是从 0 到 5000，这样一来就会有大约 2500 万个单元格。

不过，这些数据其实是比较稀疏的，最多也就几千个有效的条目，大部分的坐标都是没有数据的。

这个结构偶尔会被查找或添加数据（比如，如果 x=5 和 y=10 有数据，那就加一），但更频繁的操作是把它转换成一个 x/y/count 的列表（排序并不重要）。

最快的查找方式显然是用一个二维数组，但这样会占用大约 24 MB 的内存，而且输出列表时的遍历可能会很耗时。至于存储在磁盘上，你可以实现类似 gif 的压缩方式，0 字节后面跟着另一个字节表示 x 个空单元格，其他的就是单元格的值——但这对内存的使用并没有帮助。

使用字典的字典可能是查找速度、遍历速度和内存使用之间的一个不错平衡。

还有没有其他合适的数据结构可以考虑的呢？比如 Python 内置的、现有的库，或者更通用的数据结构？

Answer 1

这应该和处理稀疏矩阵差不多，稀疏矩阵就是在很大的数据范围内，只有少量的元素是有值的，大部分地方都是零。这里有很多可以深入了解的内容，你可以看看这个链接了解更多：http://en.wikipedia.org/wiki/Sparse_matrix

Answer 2

scipy有很多种不同的稀疏数组类型。

总共有七种稀疏矩阵类型可供选择：
csc_matrix：压缩稀疏列格式
csr_matrix：压缩稀疏行格式
bsr_matrix：块稀疏行格式
lil_matrix：列表的列表格式
dok_matrix：键字典格式
coo_matrix：坐标格式（也叫做IJV，三元组格式）
dia_matrix：对角线格式

Answer 3

用一个字典来存储一个点（也就是一个二元组）听起来不错。它的查找速度和数组一样快，都是O(1)，而且占用的空间更小。只要你不需要进行范围查询之类的操作，这样做应该没问题。

# increment
p = (x, y)
counts[p] = counts.get(p, 0) + 1

# list
for (p, count) in counts.iteritems():
    x, y = p
    print x, y, count