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 不一定是最节省空间的存储(您没有提到对查找性能的任何要求)。

例如，考虑将其存储为嵌套列表，使用 1 元组来区分叶值(尽管我们可能会想出更简洁的方法):

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

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

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

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

可以改为编码为

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

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

---

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

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

3. 如果您需要快速进行查找，您可以进行反向查找。例如，这可能是一组包含一个键的每个序列(所以你有一百万个键)。在对包含 x 的序列和包含 y 的序列进行联合后，您需要迭代结果以查看哪些具有 x 和y 顺序正确。

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