为了避免发明热水,我在这里问…
我有一个有很多数组的应用程序,内存不足。
所以我们的想法是把List<int>
压缩成其他的东西,比如有相同的接口(IList<T>
),但是我可以使用更短的整数来代替int
。
例如,如果我的值范围是0-100.000.000,我只需要ln2(1000000)=20位。因此,我不需要存储32位,而是可以修剪多余的部分,将内存需求减少12/32=37.5%。
你知道这种数组的实现吗?C++和Java也可以,因为我可以很容易地将它们转换成C。
附加要求(因为每个人都开始让我放弃这个想法):
列表中的整数是唯一的
它们没有特殊的性质,所以它们不能以任何其他方式压缩,然后减少比特数。
例如,如果值的范围是一百万,那么列表的大小将是2到1000个元素,但是会有很多元素,因此没有位集
新的数据容器的行为应该类似于可重新调整大小的数组(关于方法o()-ness)
编辑:
请不要告诉我不要这样做。这方面的要求经过深思熟虑,这是唯一剩下的选择。
此外,1米的值范围和20位的它只是一个例子。我有各种不同范围和整数大小的箱子。
另外,我可以有更短的整数,例如7位整数,那么打包将是
00000001
11111122
22222333
33334444
444.....
对于前4个元素,压缩为5个字节。
几乎完成编码-将很快发布…
最佳答案
由于只能以字节数量分配内存,因此实际上是在询问是否/如何将整数放入3字节而不是4字节(请参见下面的3)。这不是个好主意。
由于没有3字节大小的整数类型,因此需要在其位置使用其他类型(例如不透明的3字节缓冲区)。这将要求您在执行转换的代码中包装对列表内容的所有访问,以便您仍然可以将“int”放入并拉出“int”。
根据体系结构和内存分配器的不同,请求3字节块可能根本不会影响程序的内存占用(它可能只会在堆中留下不可用的1字节“洞”)。
从头开始重新实现列表以使用不透明字节数组作为其备份存储可以避免前面两个问题(它还可以让您挤压每一个最后一位的内存,而不仅仅是整个字节),但这是一个很高的顺序,而且很容易出错。
你可能想试试这样的方法:
不能同时将所有这些数据保存在内存中。如果每个int有4个字节,那么在内存耗尽之前需要达到数亿个整数。为什么你同时需要它们?
如果可能,通过不存储重复数据来压缩数据集。如果你高达数亿,肯定会有几个。
更改数据结构,以便存储连续值(增量)之间的差异(如果可能)。这可能不是很难实现,但你只能现实地期待50%的改善(这可能还不够),这将完全摧毁你在固定时间内索引到列表中的能力。