一组整数元组的Memoryefficient数据结构

Question

我有一个计算问题，涉及大量的整数元组，我必须将它们存储在一个集合中。在更多详细信息中，设置为：

• 有一个正整数n（<；=10）和许多长度为n的整数元组
• 我有一个巨大的X这样的元组集合，它是通过许多步骤构建的
• 在每个步骤中，我经常检查一些元组t是否在X中；如果不是，则在每次迭代结束时将这些元组添加到X
• 然后我必须迭代X的元素来进行其他一些计算

到目前为止，我已经使用了Python内置的set类，而且还可以。{}的大小得到了多达500万个条目，这占用了大约3–3.5 GB的内存（集合{}以及一些额外的数据）。我面临着将其扩展到3000-5000万个条目（或更多）的需要，因此我正在为此寻找一种内存效率更高的数据结构

因此，该数据结构的要求如下：

• 每个条目只出现一次
• 有快速的成员测试和快速插入
• 对所有条目进行迭代并不难

这种数据结构的明显候选对象是Trie，但我看到的实现并不完全符合我的需要。最好的选择似乎是PrefixSet来自pygtrie（至少是最好的记录）。但正如下面的简短测试所示，它实际上占用的空间至少是原来的2-5倍

from pygtrie import PrefixSet
from random import randint
from pympler import asizeof

t = PrefixSet()
s = set()

for i in range(100000):
    x = tuple(randint(0, 15) for _ in range(10))
    t.add(x)
    s.add(x)

print('|s|={} |t|={}'.format(asizeof.asizeof(s), asizeof.asizeof(t)))

给予

|s|=16995032 |t|=75835376

所以，很明显，它没有利用输入数据特性（好吧，为什么要这样做呢？它是一个相当通用的类）

Question: what is the most memory-efficient set-like data structure for storing integer tuples of a fixed length? Which of such data structes are already realised in Python?

Answer 1

如果您希望优化内存使用，则必须利用数据中的模式。除非元组中的值的分布是真正随机的，否则10个位置中应该有一些位置的不同值比其他位置少。这就是树结构存储可以用来减少内存使用的方法

例如，对于100万个元组，如果元组中的第一项在所有元组中仅具有值3、5和9，则将9项后缀元组存储在3个集合的字典中应节省相当于99997个整数的空间（理论上）：

{
   3: set(of all 9-tuples that should be prefixed by 3)
   5: set(of all 9-tuples that should be prefixed by 3)
   9: set(of all 9-tuples that should be prefixed by 3) 
}

您可以基于x最小不同位置对多个级别的前缀执行此操作，直到字典的开销超过经济成本为止

{
   (3,7): set(of all 8-tuples that should be prefixed by (3,7) )
   (3,1): set(of all 8-tuples that should be prefixed by (3,1) )
   (3,4): set(of all 8-tuples that should be prefixed by (3,4) )
   (5,4): set(of all 8-tuples that should be prefixed by (5,4) )
   ...
}

当然，最不明显的项可能不是第一项，因此您可能需要一种映射来重新排列此词典中的位置

在随机生成的数据上测试这种存储优化的问题在于，项的随机性违背了分层存储的目的，并将其置于最坏情况下。即使有一些位置组合减少了不同值的数量，也必须将前缀大小计数减少比层次结构增加的开销更多的空间（我的测试表明集合在存储小整数的元组方面非常有效，因此它们很难被击败）

简言之，如果您知道您的数据有一些分布模式，可以让您选择一个好的分组级别，那么您应该能够通过将位置映射到它们的结构（并且不给它们整个元组来管理）来受益于Trie或PrefixSet。否则，很难实现任何有意义的内存节约