用于 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