存储大量整数值的紧凑数据结构

Question

我正在开发一个应用程序，需要传递大量的Int32值。预计每个集合包含100万到5000万个项目，其中每个项目是范围在0到5000万之间的数据库键。我预计在任何给定集合中，id的分布在这个范围内是随机的。 我所需的操作非常简单：

- 添加新值 - 迭代所有值

由于这些集合的内存使用情况存在严重问题，因此我正在寻找一种可以比简单的List或HashSet更有效地存储id的数据结构。 我已经看过了BitArray，但是如果id很稀疏，它可能会浪费空间。 我也考虑过位trie，但是我不确定如何计算该解决方案对于预期数据的空间效率。 如果只能容忍误判，则Bloom Filter非常适合。

我希望得到适用于此目的的数据结构的任何建议。 我对即用型和自定义解决方案都感兴趣。

编辑：回答您的问题：

- 不需要对项目进行排序。 - “传递”意味着在方法之间传递以及序列化和发送到网络上。 我显然应该提到这一点。 - 可能会有相当多的这些集合在内存中（约100个）。

- Odrade

---

5000万个4字节项目意味着200兆字节；在现今这个时代，真的太多了吗？ :) - Cosmin

你是否正在寻找比O(1)插入和O(n)遍历所有值更好的数据结构？看起来LinkedList<T>正是你想要的。 - Joseph Yaduvanshi

“序列化并通过网络发送”听起来像是优化访问时间，以便在内存中操作这些东西已经不再重要了 :) 你到底在做什么？ - Jamie Treworgy

即使在较低的端口（10^6项），位集合比简单的32位整数数组（6MB vs 3.8MB）大不到50％，这是您可以获得的最紧凑的显式表示。我认为位集合在这里是一个明显的选择。 - Nick Johnson

又想到一个方法，可以在位集上使用非常简单的压缩方案，这将大大减小n较小时的大小，并且在最坏情况下最多只会有12%的影响。使用每个字节的第一个位来编码跳过，例如0表示正常处理接下来的7位，1表示跳过接下来的n个值，其中接下来的7位是n。这也会加快较小n值的迭代速度。 - Jamie Treworgy

Answer 1

使用BitArray。它仅使用大约6MB的内存；唯一的真正问题是迭代是Theta(N)，即您必须遍历整个范围。但是局部性很好，您可以在一个操作中分配整个结构。

至于浪费空间：在最坏情况下浪费了6MB。

编辑：好的，你有很多集合并且你正在序列化。对于在磁盘上进行序列化，我建议使用6MB文件：）

对于通过网络发送，请迭代并考虑发送范围而不是单个元素。这需要一个排序结构。

您需要很多这些集合。考虑是否有600MB可用。否则，请查看：

• 按字节排序的尝试：O(1)插入，O(n)迭代，比位排序具有更低的常数因子
• 自定义哈希表，可能是通过C++/CLI的Google sparsehash
• 存储范围/区间的BSTs
• 超级节点BSTs

- Fred Foo

---

+1. 我对访问时间的断点很感兴趣。与长格式相比，您只需要访问一个字节即可迭代8个数字。使用位运算符可以非常快速地获取给定起始点处给定字节的每个#。我想知道数学计算如何工作，完全加载集合的迭代断点大约在1/32（150万条记录）左右？例如，位集的速度必须低于1.5百万。或者我没有考虑到迭代过程中涉及的所有内容。 - Jamie Treworgy

迭代可能会跳过一些块的k个全零位，其中k可能是8、16、32或64。集合变得越密集，速度就会变慢，特别是如果值是均匀分布的。 - Fred Foo

比起天真的实现，这个实现好了32倍...不错，先生！ - Cosmin

OP已经提出了这个建议。我只是怀疑是否有什么能够超越这种表示方式，包括我之前的建议，因为项目数量可能接近完整范围，而位集合几乎没有开销。 - Fred Foo

密集的集合越来越稠密，速度就会变慢 - 我甚至没有考虑跳过。即使考虑到这一点，似乎也可以通过内存访问与 int 列表相比减少 1/32 的方式来部分弥补。另一方面，需要进行数学运算才能返回每个数字。 - Jamie Treworgy

"迭代是Theta(n)" - 这可能并不是一个很大的问题。位集始终至少有2%被占用，因此迭代与集合中元素数量成比例相比，与整个范围成比例相比的差异是50倍而不是不同的复杂度。 - Steve Jessop

Answer 2

我认为答案取决于你所说的“传递”是什么意思，以及你想要实现什么目标。你说你只是在列表中添加：你添加的频率有多高？列表增长速度如何？内存使用的可接受开销与重新分配内存的时间相比如何？

在最坏的情况下，50,000,000个32位数字= 200兆字节，使用最有效的数据存储机制。假设你在最坏的情况下可能会使用这么多，那么一直使用这么多内存可以吗？这比经常重新分配内存好吗？典型使用模式的分布情况是什么？您可以始终只使用预先分配到整个5000万的int []。

至于你的操作的访问速度，没有什么比迭代和添加到预先分配的内存块更快的。

来自OP编辑：内存中可能会有相当数量的这些集合（约100个）。

嘿。你需要一次性在内存中存储100组1到5000万个数字的集合吗？我认为位集方法是唯一可行的方式。

那将是600兆字节。虽然不算小，但除非它们（通常）大部分为空，否则你很难找到更有效的存储机制。

现在，如果你不使用位集，而是使用动态大小的结构，并且它们可以以更少的空间开始，那么你就会遇到真正丑陋的内存分配/释放/垃圾回收场景。

假设你确实需要这样做，尽管我只能想象为什么。所以你的服务器有大量的内存，只需分配所需数量的6兆字节位集并回收它们。分配和垃圾回收不再是问题。是的，你正在使用大量的内存，但这似乎是不可避免的。

- Jamie Treworgy

---

一个位集只需要6MB的空间，但需要Theta(n)的迭代。 - Fred Foo

我不明白OP说的50亿32位值是从哪里来的，因为我没有看到这个50亿位数。 - Adam Houldsworth

其中每个项目都是在0-50,000,000范围内的数据库键（实际上是500,000,001位）。 - Fred Foo

我不会删除你的答案，因为它直接解决了内存方面的严重问题。但是我不确定如何直接迭代位 - 把一堆整数放入BitVectors中听起来并不好玩。 - Adam Houldsworth

@BlueRaja: 那么，OP提到的HashSet、trie和Bloom过滤器都不是有效的选项。 - Fred Foo

Answer 3

这将取决于您集合大小的分布情况。除非您期望大多数集合接近或等于您指定的最小值，否则我建议使用位集。为了覆盖范围高达50,000,000，位集的大小约为6兆字节。

与直接存储数字相比，对于您指定的最小大小集合，这可能略大一些（约为6兆字节而不是约为4兆字节），但对于最大大小集合来说，则要小得多（1/32^nd的大小）。

第二种可能性是使用增量编码。例如，不直接存储每个数字，而是存储该数字与上一个包含的数字之间的差异。给定最大幅度为50,000,000和最小大小为1,000,000项，一个数字与下一个数字之间的平均差异约为50。这意味着你可以在平均小于6位的情况下理论上存储差异。我可能会直接使用7个最低有效位，如果需要编码更大的间隔，则设置msb并（例如）将间隔的大小存储在较低的7位加上下一个三个字节中。这种情况不会经常发生，因此在大多数情况下，您仅使用一个字节来存储一个数字，相对于直接存储数字，压缩比约为4:1。在最好的情况下，这将使用约1兆字节的集合，在最坏的情况下约为50兆字节--相对于直接存储数字，压缩比为4:1。

如果您不介意一点额外的代码，您可以使用自适应方案--对于小型集合（最多6,000,000个数字），使用增量编码，对于大型集合，则使用位图。

- Jerry Coffin

---

这意味着理论上你可以平均只用<6位存储差异，虽然增加一个值可能会很耗费资源，因为它基本上是在数组中间插入新元素。不过，你可以便宜地添加一个大的负数偏差到末尾。那么问题就在于检测重复项，但对于向List<int>添加元素而言也是如此，问者似乎在功能上满意，仅对存储效率不满意。 - Steve Jessop