java – 压缩数字数组

如果是这样,您可以尝试压缩数据块并在需要时解压缩.块越大,可以节省的内存越多,速度越差.恕我直言没什么好处.您还可以将数据压缩并解压缩到内存中.

否则,即,如果没有规律性,每个条目至少需要log(9)/ log(2)= 3.17位,没有什么可以改善它.

通过将5个数字打包成一个短数,你可以非常接近这个值.如9 ** 5 = 59049< 65536 = 2 ** 16,几乎完美.你需要每位数3.2位,没有大赢.通过该公式给出五个数字的包装

a + 9 * (b + 9 * (c + 9 * (d + 9 * e)))

并且通过预先计算的表来解压缩是微不足道的.

问题更新后更新

Further information: I just did a little experimenting,and it turns out,that on average 2.14 consecutive numbers have the same value. There are 1 zero,154 ones,10373 twos,385990 threes,8146188 fours,85008968 fives,265638366 sixes,70791576 sevens and 80 eights. So more than half of the numbers are 6s.

事实上平均有大约2.14个连续数字是相同的可能导致一些压缩,但在这种情况下它没有说什么.几乎只有五个和六个,所以似乎暗示了遇到两个相等的连续数字.

鉴于这一事实,您可以忘记我的上述优化.由于您可以单独处理单个零,因此实际上只有8个值.因此,每个值只需要3位,零点需要一个索引.

您甚至可以为低于4或高于7的所有值创建HashMap,存储1 154 10373 385990 80个条目,每个值仅使用2位.但这还远非理想.

假设没有规律性,你需要每个值1.44位,因为这是entropy.你可以浏览所有5元组,计算它们的直方图,并使用1个字节来编码255个最频繁的元组.所有剩余的元组都将映射到第256个值,告诉您必须在HashMap中查找稀有元组值.

一些评价

我很好奇它是否可行.将5个数字打包成一个字节需要85996340个字节.有近500万个元组不适合,所以我的想法是为它们使用哈希映射.假设重新开始而不是链接它是有意义的保持它可能50％满,所以我们需要1000万条目.假设TIntShortHashMap(将索引映射到元组),每个条目占用6个字节,导致60 MB.太糟糕了.

在一个字节中只包含4个数字,消耗107495425个字节,并留下159531个不适合的元组.这看起来更好,但是,我确信更密集的包装可以得到很大改善.

由这个小program产生的结果：

*** Packing 5 numbers in a byte. ***
Normal packed size: 85996340.
Number of tuples in need of special handling: 4813535.

*** Packing 4 numbers in a byte. ***
Normal packed size: 107495425.
Number of tuples in need of special handling: 159531.