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

我有一个包含大量数组的应用程序,并且内存不足.

所以我的想法是压缩List< int>对于别的东西,它将具有相同的接口(例如IList< T>),但是代替int,我可以使用更短的整数.

例如,如果我的值范围是0 – 100.000.000,我只需要ln2(1000000)= 20位.因此,不是存储32位,而是可以减少多余的内存并将内存需求降低12/32 = 37.5％.

你知道这种数组的实现吗？ c和java也可以,因为我可以很容易地将它们转换为c#.

附加要求(因为每个人都开始让我想到这个想法)：

>列表中的整数是唯一的
>它们没有特殊属性,因此它们不能以任何其他方式压缩,然后减少位数
>如果值范围是一百万例如,列表的大小将是2到1000个元素,但是会有很多,所以没有BitSet
>新数据容器应该像可重新调整大小的数组(关于方法O() – ness)

编辑：

请不要告诉我不要这样做.对此的要求经过深思熟虑,并且是唯一的选择.

此外,1M值的范围和20位仅是一个例子.我有所有不同范围和整数大小的情况.

此外,我甚至可以有更短的整数,例如7位整数,然后打包

00000001
11111122
22222333
33334444
444.....

对于前4个元素,打包成5个字节.

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

解决方法:

由于您只能在字节量子中分配内存,因此您实际上是在询问/如何将整数拟合为3个字节而不是4个(但请参见下面的#3).这不是一个好主意.

>由于没有3字节大小的整数类型,您需要在其位置使用其他内容(例如,不透明的3字节缓冲区).这将要求您在执行转换的代码中包装对列表内容的所有访问权限,这样您仍然可以将“ints”放入并拉出“整数”.
>根据体系结构和内存分配器的不同,请求3字节块可能根本不会影响程序的内存占用(它可能只会使用不可用的1字节“漏洞”乱丢垃圾堆).
>从头开始重新实现列表以使用不透明的字节数组作为其后备存储将避免前两个问题(并且它还可以让你挤出每个最后一点内存而不是整个字节),但这是一个很高的顺序而且非常容易出错.

你可能想要尝试类似的东西：

>不要将所有这些数据同时保存在内存中.每个int 4个字节,在内存耗尽之前,你需要达到数亿个整数.为什么你需要同时使用所有这些？
>如果可能,通过不存储重复项来压缩数据集.如果你达到数亿,肯定会有一些.
>如果可能,更改数据结构以便存储连续值(增量)之间的差异.这可能不是很难实现,但你只能实际地期望在50％的改进(可能还不够)的情况下,并且它将完全破坏你在恒定时间内索引列表的能力.