排序数组的紧凑数据结构

Question

我有一张有排序数字的桌子，如：

1 320102
2 5200100
3 92010023
4 112010202
5 332020201
6 332020411
: 
5000000000 3833240522044511
5000000001 3833240522089999
5000000002 4000000000213312

给定记录号，我需要以O(log )时间为单位的值。记录号是64位长，没有丢失的记录号码.这些值是64位长的，它们被排序，值(N)

显而易见的解决方案是简单地执行一个数组并使用记录号作为索引。这将花费64位每值.

但我想要一种更有空间效率的方法来做到这一点。因为我们知道值总是在增加，所以应该是可行的，但是我不记得有一个数据结构允许我这样做。

一种解决方案是在数组上使用deflate，但这不会给我访问元素的O(log )--因此不能接受。

你知道有一种数据结构会给我：

• O(log )供查阅
• 空间要求<64位/值

=编辑=

因为我们事先知道所有的数字，所以我们可以找到每个数字之间的区别。通过取这些差异的第99百分位数，我们将得到一个相对较小的数字。采用log2将给我们表示适度数字所需的比特数--让我们称之为适度比特。

然后创建以下内容：

64-bit value of record 0
64-bit value of record 1024
64-bit value of record 2048
64-bit value of record 3072
64-bit value of record 4096

然后为所有记录创建一个delta表：

modest-bits difference to record 0
modest-bits difference to previous record
1022 * modest-bits difference to previous record
modest-bits difference to record 1024

记录k*1024的微小位差总是为0，所以我们可以将其用于信令。如果它不是零，那么下面的64位将是指向下一个1024条记录为64位值的简单数组的指针。

由于选择适度值作为第99百分位数，这最多只会发生1%的时间，从而浪费最多1% *n*适度位+ 1% *n*64位* 1024。

空间:O(适度位*n+64位*n/ 1024 + 1% *n*适度位+ 1% *n*64位* 1024)

查找: O(1 + 1024)

(99%及1024 %可能须予调整)

= Edit2 =

基于上面的想法，但浪费更少的空间。创建以下内容：

64-bit value of record 0
64-bit value of record 1024
64-bit value of record 2048
64-bit value of record 3072
64-bit value of record 4096

对于所有不能用适度位表示的值，请将大值表创建为一棵树：

64-bit position, 64-bit value
64-bit position, 64-bit value
64-bit position, 64-bit value

然后为所有记录创建一个delta表，即每1024条记录重置一次：

modest-bits difference to record 0
modest-bits difference to previous record
1022 * modest-bits difference to previous record
modest-bits difference to record 1024

但也可以重置大值表中的每个值。

空间:O(适度位*n+64位*n/ 1024 + 1% *n*2*64位)。

查找需要搜索大值表，然后查找第1024‘值，最后求和适度位值。

查找: O(log (大值表)+1+ 1024) =O(Log)

你能改进一下吗？还是以另一种方式做得更好？

Answer 1

正如你在问题中所概述的那样，我会分块做。选择一个块大小k，在这里你可以接受平均k/2值的解码，然后才能到达你想要的值。对于n个总值，您将有n/k块。带有n/k项的表将指向数据流，以查找每个块的起始点。查找该表中的位置将是二进制搜索的O(log(n/k))，或者如果该表足够小，如果它很重要，则可以使用一个辅助哈希表来表示O(1)。

每个块的起始值为64位。之后的所有值都将从前面的值存储为增量。我的建议是将这些三角存储为一个Huffman代码，它说明下一个值中有多少位，然后是那么多位。将为每个块优化Huffman代码，并将该代码的描述存储在块的开头。

您可以简化这一点，只需在每个值前面加上6个位数，其位数在1..64范围内，实际上是一个平面Huffman代码。根据比特长度的直方图，优化的Huffman代码与平坦代码相比可以减少大量的比特。

一旦你设置了这个，你就可以用k做实验，看看你能做多小，但对压缩的影响还是有限的。

Answer 2

我不知道有这样的数据结构。

明显的解决方案，以获得空间和不松太快将是创建您自己的结构与不同的数组大小，根据不同的int大小，您所存储的。

伪码

class memoryAwareArray {
    array16 = Int16[] //2 bytes
    array32 = Int32[] //4 bytes
    array64 = Int64[] //8 bytes

    max16Index = 0;
    max32Index = 0;

    addObjectAtIndex(index, value) {
      if (value < 65535) {
        array16[max16Index] = value;
        max16Index++;
        return;
      }
      if (value < 2147483647) {
        array32[max32Index] = value;
        max32Index++;
        return;
      }

      array64[max64Index] = value;
      max64Index++;
    }

    getObject(index) {
      if (index < max16Index) return(array16[index]);
      if (index < max32Index) return(array32[index-max16Index]);
      return(array64[index-max16Index-max32Index]);
    }
}

沿着这些路线的东西不应该改变太多的速度，如果你填满整个结构，你会节省大约7千兆气体。当然，你不会存那么多钱，因为你的价值观之间有差距。