缩短的整数数组

本文关键字：数组 整数 | 更新日期: 2023-09-27 18:18:15

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

我有一个包含大量数组的应用程序，它的内存即将耗尽。

所以我们的想法是将List<int>压缩成其他东西，它将具有相同的接口(例如IList<T>)，但我可以使用更短的整数代替int。

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

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

附加要求(因为每个人都开始让我放弃这个想法):

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

请不要告诉我不要这样做。这个要求是经过深思熟虑的，这是唯一的选择。

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

也可以是更短的整数，例如7位整数，那么打包将是

00000001
11111122
22222333
33334444
444.....

前4个元素，打包成5个字节。

几乎完成编码-将很快发布…

缩短的整数数组

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

  1. 由于没有3字节大小的整数类型，您需要使用其他东西(例如不透明的3字节缓冲区)来代替它。这就要求你在执行转换的代码中包装对列表内容的所有访问，以便你仍然可以放入"int"并取出"int"。
  2. 根据体系结构和内存分配器的不同，请求3字节的块可能根本不会影响程序的内存占用(它可能只是在堆中留下不可用的1字节"洞")。
  3. 从头开始重新实现列表，使用不透明的字节数组作为其后台存储将避免前面的两个问题(并且它还可以让您压缩每一个内存位，而不仅仅是整个字节)，但这是一个很高的要求，很容易出错。

你可能想尝试这样做:

  • 没有同时在内存中保存所有这些数据。如果每个int值为4字节，则需要在内存耗尽之前达到数亿个整数。为什么你同时需要所有这些呢?
  • 通过尽可能不存储重复数据集来压缩数据集。如果你有上亿的话，肯定会有几个。
  • 如果可能的话，更改数据结构以便存储连续值(增量)之间的差异。这可能不是很难实现，但是你只能现实地期望大约50%的改进(这可能还不够)，它将完全破坏你在固定时间内索引列表的能力。

从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<Entry>。

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

这让我想起了base64和类似的二进制到文本编码。它们使用8位字节，并进行一些位调整，将它们打包成4位、5位或6位可打印字符。这也让我想起了Zork信息交换标准代码(ZSCII)，它将3个字母打包成2个字节，其中每个字母占用5位。这听起来像是你想把一堆10位或20位的整数打包到一个8位字节的缓冲区中。

源代码可用于处理单个位的打包数组的许多库(一个bcde) .

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

Edit:假设您的整数是唯一的，您可以做以下操作:存储唯一的整数，直到您存储的整数数量是最大数量的一半。然后切换到存储没有的整数。这将减少50%的存储空间。

在尝试使用20位整型之前，

可能值得探索其他简化技术。

如何处理重复的整数?如果有很多重复，你可以通过将整数存储在Dictionary<int, int>中来减小存储大小，其中键是唯一的整数，值是相应的计数。注意，这假定您不关心整数的顺序。

所有的整数都是唯一的吗?也许你正在存储0到100mil范围内的许多唯一整数，在这种情况下，你可以尝试存储你没有的整数。然后，当确定您是否有一个整数i只是问它是否不在您的集合

相关文章：