python - 在python中高效存储一组整数序列

Question

我有一大组整数序列，下面是小样本:

1
2
1
1 2
1 3 2
4
1 3 2
...

简单地将它们存储为元组列表会给我带来内存错误，因此我正在寻找可以保存它们(或等效信息)的更好的数据结构。序列之间的顺序并不重要(即序列没有 id)，但需要保留每个序列内的顺序。

关于如何有效地做到这一点有什么想法吗？我正在考虑嵌套字典；上面的例子看起来像这样:

{1: {2: {-1: 1}, 
     3: {2: {-1: 2}, -1: 0}, 
    -1: 2}, 
 2: {-1: 1}, 
 4: {-1: 1}}

“叶子”值(由键 -1 给出)是各个序列的计数。当然，这并没有利用所有键都是整数的事实。

粗略地说，我希望管理大约十亿个序列，平均长度为 3，具有大量冗余。不同整数的数量约为一百万。有什么好的想法/现有的库吗？

编辑:

构建数据结构的“子集”应该是有效的，如下所示。给定一个整数 x，仅获取包含 x 的序列。例如，如果x=2，那么我们将从初始数据结构构建以下子集:

{1: {2: {-1: 1}, 
     3: {2: {-1: 2}, -1: 0}, 
    -1: 0}, 
 2: {-1: 1}}

如果可能的话，我还希望能够构建一个子集，如下所示。我指定一对整数(x,y)，对应的子集是x和y同时出现的序列集合，并且第一个 x 出现在第一个 y 之前。例如，对于 (x,y)=(1,2) 我们会得到

{1: {2: {-1: 1}, 
     3: {2: {-1: 2}, -1: 0}, 
    -1: 0}}

我没有明确的 O(log n) 要求，最终它应该尽可能快地运行:) 不幸的是，我无法提供实际的数据样本，因为它不是我的分享。

Answer 1

考虑到冗余量，您可以使用 Trie 获得良好的压缩效果。 ，它会折叠所有常见前缀。

看起来您的嵌套字典结构的目标是这个方向，但 HashMap 不一定是最节省空间的存储(您没有提到对查找性能的任何要求)。

例如，考虑将其存储为嵌套列表，并使用一元组来区分叶值(尽管我们可能会想出更清晰的东西):

trie = [ [1, (2,),
             [2, (1,)],
             [3, [2, (2,)]],
         [2, (1,)],
         [4, (1,)]
       ]

平均长度为 3，这应该相当浅，并且希望使用列表而不是字典在每个级别上都有更少的松弛。

请注意，如果某些分支又长又裸，您可以以代码复杂性为代价压缩冗余深度。考虑子树

[1, [2, [3, ... [n, (1,)]...]]]

可以编码为

[1, 2, 3, ..., n, (1,)]

只要你区分平面序列和同级序列(这里，叶子始终是一个元组，子树始终是一个列表，其他任何东西都是平面序列中的下一个元素)。

---

新的子集要求更加复杂。我可以想到一些可能的方法:

1. 天真的/暴力搜索:再次取决于您的访问模式，您可以返回一个生成器，而不是匹配子树(子尝试)的渴望的完整深度副本
2. 在每个子树的顶部存储一个布隆过滤器，指示在其中找到的值。 您的搜索工作方式与 (1) 相同，只是您可以快速跳过无法匹配的子树。
   • 每个级别的过滤器只是其子级中的过滤器的逻辑“或”

3. 如果需要快速查找，可以进行反向查找。例如，这可能是包含一个 key 的每个序列的集合(因此您将拥有一百万个 key )。将包含 x 的序列与包含 y 的序列进行并集后，您需要迭代结果以查看哪个序列具有 x 和y 以正确的顺序。

   此方案的困难在于表示每个序列。您要么需要一个到 Trie 中叶节点的链接(并且能够以某种方式从叶到根进行迭代)，要么需要每个序列的单独平面副本，这似乎很浪费