缩短整数数组

Question

为了避免发明热水，我在这里问...

我有一个包含大量数组的应用程序，但它的内存不足。

因此，我们的想法是将 List 压缩为其他具有相同接口的东西（例如 IList），但不是 int 我可以使用更短的整数。

例如，如果我的值范围是 0 - 100.000.000，我只需要 ln2(1000000) = 20 位。因此，我可以删除多余的部分并将内存需求减少 12/32 = 37.5%，而不是存储 32 位。

你知道这样的数组的实现吗？ c++ 和 java 也可以，因为我可以轻松地将它们转换为 c#。

附加要求（因为每个人都开始让我摆脱这个想法）：

• 列表中的整数是唯一的，
• 减少位数
• 它们没有特殊的属性，因此它们不能以任何其他方式压缩，然后如果值范围是一百万，则 例如，列表的大小为 2 到 1000 个元素，但它们的数量会很多，因此 BitSets
• 新数据容器的行为不应像可调整大小的数组（关于方法 O()-ness）

编辑：

请不要告诉我不要这样做。对此的要求是经过深思熟虑的，它是剩下的唯一选项。

此外，1M 的值范围和 20 位只是一个示例。我的情况具有所有不同的范围和整数大小。

此外，我还可以有更短的整数，例如 7 位整数，然后将

00000001
11111122
22222333
33334444
444.....

前 4 个元素打包为 5 个字节。

---

几乎完成了编码 - 很快就会发布......

Answer 1

由于您只能以字节量分配内存，因此您实际上是在问是否/如何将整数放入 3 个字节而不是 4 个字节（但请参见下面的#3）。这不是一个好主意。

1. 由于没有 3 字节大小的整数类型，因此您需要使用其他东西（例如不透明的 3 字节缓冲区）来代替它。这需要您将对列表内容的所有访问包装在执行转换的代码中，以便您仍然可以将“int”放入并拉出“int”。
2. 根据架构和内存分配器，请求 3 字节块可能根本不会影响程序的内存占用（它可能只是在堆上堆满不可用的 1 字节“洞”）。
3. 从头开始重新实现列表以使用不透明字节数组作为其后备存储可以避免前面的两个问题（并且它还可以让您压缩最后一位内存而不是整个字节），但这是一个艰巨的任务并且很容易发生到错误。

您可能想尝试以下操作：

• 不同时将所有这些数据保留在内存中。如果每个整数 4 个字节，则需要在内存耗尽之前达到数亿个整数。为什么您同时需要所有这些？
• 如果可能，通过不存储重复项来压缩数据集。上亿的话，肯定有几个。
• 如果可能的话，更改数据结构，使其存储连续值之间的差异（增量）。这可能不是很难实现，但是您实际上只能期望大约 50% 的改进（这可能还不够），并且它将完全破坏您索引到列表中的能力恒定时间。

Answer 2

将 32 位转换为 24 位的一种选择是创建一个自定义结构，用于存储 3 个字节内的整数：

public struct Entry {
    byte b1; // low
    byte b2; // middle
    byte b3; // high

    public void Set(int x) {
        b1 = (byte)x;
        b2 = (byte)(x >> 8);
        b3 = (byte)(x >> 16);
    }

    public int Get() {
        return (b3 << 16) | (b2 << 8) | b1;
    }
}

然后您可以创建一个 List。

var list = new List<Entry>();
var e = new Entry();
e.Set(12312);
list.Add(e);
Console.WriteLine(list[0].Get()); // outputs 12312

Answer 3

这让我想起了 base64 和类似的二进制到文本编码。
它们采用 8 位字节，并进行一系列位调整，将它们打包成 4 位、5 位或 6 位可打印字符。
这也让我想起了Zork信息交换标准码（ZSCII），它把3个字母打包成2个字节，每个字母占5位。
听起来您想要获取一堆 10 位或 20 位整数并将它们打包到 8 位字节的缓冲区中。

源代码可用于许多处理单个位的打包数组的库
(a
b
c
d
e）。

也许你可以
(a) 下载该源代码并修改源代码（从某些 BitArray 或其他打包编码开始），重新编译以创建一个新的库，用于处理打包和解包 10 位或 20 位整数而不是单个位。
可能需要更少的编程和测试时间
(b) 编写一个库，从外部看，其行为与 (a) 类似，但在内部它将 20 位整数分解为 20 个单独的位，然后使用（未修改的）BitArray 类存储它们。

Answer 4

编辑：鉴于您的整数是唯一的，您可以执行以下操作：存储唯一的整数，直到您存储的整数数量是最大数量的一半。然后切换到存储您没有的整数。这将减少 50% 的存储空间。

在尝试使用 20 位整数之前，可能值得探索其他简化技术。

如何处理重复的整数？如果有大量重复的整数，您可以通过将整数存储在 Dictionary 中来减少存储大小，其中键是唯一的整数，并且值是相应的计数。请注意，这假设您不关心整数的顺序。

您的整数都是唯一的吗？也许您存储了许多 0 到 1 亿范围内的唯一整数。在这种情况下，您可以尝试存储您没有的整数。然后，当确定您是否有一个整数 i 时，只需询问它是否不在您的集合中。