用于稀疏x/y坐标列表的Python数据结构

Question

考虑x/y坐标列表和字节'计数'.x/y的范围可能是0到5000,即2500万个单元.

然而,数据将非常稀少,最多只有几千个条目,大多数坐标将没有条目.

偶尔会查找/添加结构(例如,如果x = 5和y = 10然后是++),但更频繁地转换为x/y/count列表(排序并不重要)

用于查找的最快数据结构显然是一个二维数组,但是你正在查看大约24 MB的内存,并且输出列表的迭代可能很昂贵.对于磁盘存储,您可以实现gif样式压缩,其中0字节后跟另一个字节表示x空单元格,其他任何东西都是单元格值 - 但这对内存情况没有帮助.

字典的字典可能是查找/迭代速度和内存使用之间的良好平衡.

是否还有其他合适的数据结构我应该考虑(内置于Python,现有库还是更通用的数据结构？

Answer 1

由点(即2元组)声音键入的字典对我有好处.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