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

考虑x/y坐标列表和一个字节“count”。 x/y的范围可能是0到5000，即2500万个单元格。用于x/y坐标稀疏列表的Python数据结构

但是，数据将会相当稀疏地填充，最多只有几千个条目，并且大多数坐标将具有零个条目。

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

查找的最快数据结构显然是一个二维数组，但你在寻找24 MB内存，迭代输出一个列表可能会很昂贵。对于磁盘存储，您可以实现gif样式压缩，其中0字节后跟另一个字节表示x空单元格，其他任何内容都是单元格值 - 但这无助于内存情况。

字典的字典可能会很好地平衡查找/迭代速度和内存使用。

是否有我应该考虑（无论是内置于Python的任何其他合适的数据结构，现有的库或者更一般的数据结构？

来源

2011-05-17 Ryan

呃 - http://en.wikipedia.org/wiki/ Sparse_matrix＃Storing_a_sparse_matrix – Ryan 2011-05-17 21:03:42

注意自己，读完所有已发布的标签，然后张贴在SO ...这是所有;） – Ryan 2011-05-17 21:09:44

由点键控的字典（即，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

来源

2011-05-17 21:05:11

为什么不使用'counts = defaultdict（int）'这样你就可以写'counts [x，y] + = 1' – 2011-05-17 21:12:51

是的，'defaultdict'很酷，虽然它是在Python 2.5中添加的，所以使用'd .get（p，0）+ 1'方法对于Python 2.4及更早版本是可移植的，如果有人担心的话。 – 2011-05-17 21:17:16

@gnibbler：因为我的Python非常生锈，而且我忘记了它！ – 2011-05-17 21:27:03

SciPy的射程为different sparse arrays

有七个可用稀疏矩阵类型：
csc_matrix：压缩稀疏列格式
csr_matrix：压缩稀疏行格式
bsr_matrix：块稀疏行格式
lil_matrix：列表格式的列表
dok_matrix：字典密钥的格式
coo_matrix：坐标格式（又名IJV，三重峰格式）
dia_matrix：对角线格式

来源

2011-05-17 21:03:37

干杯gnibbler，从我+1是非常有用的，但我标记为另一个答案，因为它有助于在查看优化库之前了解这个概念。 – Ryan 2011-05-17 21:19:53

这应该是类似于在数据范围的大小的稀疏矩阵的工作，有很多的东西来啃这里http://en.wikipedia.org/wiki/Sparse_matrix

来源

2011-05-17 21:05:31 dfb

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

回答

相关问题