存储数千个电话号码的最有效方法

在下文中，我将数字视为整数变量（而不是字符串）：

对数字进行排序。将每个数字分成前五位和后五位。前五位数字在数字之间是相同的，因此只需存储一次。这将需要 17 位存储空间。单独存储每个数字的最后五位数字。这将需要每个数字 17 位。

回顾一下：前 17 位是公共前缀，随后的 1000 组 17 位是按升序存储的每个数字的后五位。

总共我们查看 1000 个号码的 2128 个字节，或每个 10 位电话号码 17.017 位。

搜索是 O(log n)（二分搜索），完整枚举是 O(n)。

这是对 aix's answer 的改进。考虑为数据结构使用三个“层”：第一个是前五位（17 位）的常量；所以从现在开始，每个电话号码只剩下剩下的五位数字了。我们将剩余的五位数字视为 17 位二进制整数，并使用一种方法存储这些位中的 k 位，并使用 17 - k = m不同的方法，最后确定 k 以最小化所需的空间。

我们首先对电话号码进行排序（全部缩减为 5 位小数）。然后我们计算有多少电话号码的前m位二进制数全为0，有多少电话号码前m位最多为0...01，有多少电话号码前m位位最多为 0...10 等，直到前 m 位为 1...11 的电话号码的计数 - 最后计数为 1000（十进制）。有 2^m 个这样的计数，每个计数最多为 1000。如果我们省略最后一个（因为我们知道它无论如何都是 1000），我们可以将所有这些数字存储在 (2^m - 1) 的连续块中* 10 位。 （10 位足以存储小于 1024 的数字。）

所有（减少的）电话号码的最后 k 位连续存储在内存中；因此，如果 k 是 7，则该内存块的前 7 位（位 0 到 6）对应于第一个（缩减的）电话号码的后 7 位，位 7 到 13 对应于后 7 位第二个（减少的）电话号码等。这需要 1000 * k 位，总共 17 + (2^(17 - k) - 1) * 10 + 1000 * k，在 k = 10 时达到最小值 11287。所以我们可以将所有电话号码存储在 ceil( 11287/8)=1411 字节。

通过观察我们的数字都不能以例如 1111111（二进制）开头，可以节省额外的空间，因为以它开头的最小数字是 130048，而我们只有五个十进制数字。这允许我们从第一个内存块中删除一些条目：我们只需要 ceil(99999/2^k) 而不是 2^m - 1 个计数。这意味着公式变为

17 + ceil(99999/2^k) * 10 + 1000 * k

对于 k = 9 和 k = 10 或 ceil(10997/8) = 1375 字节，这令人惊讶地达到其最小值 10997。

如果我们想知道某个电话号码是否在我们的集合中，我们首先检查前五个二进制数字是否与我们存储的五个数字匹配。然后我们将剩余的五位数字分成其顶部 m=7 位（即 m 位数字 M）和其低位 k=10 位（数字 K）。我们现在找到前 m 位最多为 M - 1 的简化电话号码的数量 a[M-1]，以及前 m 位最多为 M 的简化电话号码的数量 a[M]，都来自第一个位块。我们现在检查第二个内存块中第 a[M-1] 个和第 a[M] 个 k 位序列之间是否找到 K；在最坏的情况下，有 1000 个这样的序列，所以如果我们使用二进制搜索，我们可以在 O(log 1000) 操作中完成。

下面是用于打印所有 1000 个数字的伪代码，其中我将第一个内存块的第 K 个 k 位条目访问为 a[K]，将第二个内存块的第 M 个 m 位条目访问为 b[M] （这两个都需要一些繁琐的写操作）。前五位数字在数字 c 中。

i := 0;
for K from 0 to ceil(99999 / 2^k) do
  while i < a[K] do
    print(c * 10^5 + K * 2^k + b[i]);
    i := i + 1;
  end do;
end do;

也许 K = ceil(99999/2^k) 的边界情况出了点问题，但这很容易解决。

最后，从熵的角度来看，不可能在小于 ceil(log[2](binomial(10^5, 10^3)) 中存储全部小于 10^5 的 10^3 个正整数的子集) = 8073。包括前 5 位我们需要的 17 位，还有 10997 - 8090 = 2907 位的差距。看看是否有更好的解决方案，您仍然可以相对有效地访问数字，这是一个有趣的挑战！

http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automaton

我曾经接受过一次采访，他们询问了数据结构。我忘记了“数组”。

我可能会考虑使用一些压缩版本的 Trie（可能是 @Misha 建议的 DAWG）。

这将自动利用它们都有一个共同的前缀这一事实。

搜索将以恒定时间执行，打印将以线性时间执行。

我以前听说过这个问题（但没有前 5 位相同的假设），最简单的方法是 Rice Coding：

1）由于顺序无关紧要，我们可以对它们进行排序，并只保存连续值之间的差异。在我们的例子中，平均差异为 100.000 / 1000 = 100

2) 使用莱斯码（基数 128 或 64）甚至哥伦布码（基数 100）对差异进行编码。

编辑：以 128 为基数的 Rice 编码估计（不是因为它会给出最好的结果，而是因为它更容易计算）：

我们将按原样保存第一个值（32 位）。其余 999 个值是差异（我们希望它们很小，平均为 100）将包含：

一元值 value / 128（可变位数 + 1 位作为终止符）
value % 128 的二进制值（7 位）

我们必须以某种方式估计变量位数的限制（我们称之为 VBL）：
下限：认为我们很幸运，没有差异大于我们的基数（在这种情况下为 128）。这意味着给 0 个额外的位。
上限：由于所有小于 base 的差异都将被编码为数字的二进制部分，我们需要在一元中编码的最大数字是 100000/128 = 781.25（甚至更少，因为我们不希望大多数差异为零）。

所以，结果是 32 + 999 * (1 + 7) + variable(0..782) bits = 1003 + variable(0..98) bytes。

这是 Bentley 的 Programming Pearls 中的一个众所周知的问题。

解决方案：从数字中去掉前五位数字，因为它们对于每个数字都是相同的。然后使用按位运算来表示剩余的 9999 个可能值。您只需要 2^17 位来表示数字。每个位代表一个数字。如果设置了该位，则该号码在电话簿中。

要打印所有数字，只需打印该位与前缀连接的所有数字。要搜索给定的数字，请执行必要的位运算来检查数字的按位表示。

您可以在 O(1) 中搜索一个数字，并且由于位表示，空间效率最大。

HTH 克里斯。

固定存储 1,000 个数字的 1073 字节：

这种存储方式的基本格式是存储前5位数字，每组一个计数，每组每个数字的偏移量。

前缀：我们的 5 位前缀占用前 17 位。

分组：接下来，我们需要找出一个合适的数字分组。让我们尝试每组大约有 1 个号码。因为我们知道有大约 1000 个数字要存储，所以我们将 99,999 分成大约 1000 个部分。如果我们选择组大小为 100，会有浪费的位，所以我们尝试组大小为 128，可以用 7 位表示。这为我们提供了 782 个小组合作。

计数：
接下来，对于 782 个组中的每一个，我们需要存储每个组中的条目计数。每个组的 7 位计数将产生 7*782=5,474 bits，这是非常低效的，因为我们选择组的方式所表示的平均数约为 1。

因此，我们有可变大小的计数，组中的每个数字前导 1，后跟 0。因此，如果我们在组中有 x 个数字，我们将用 x 1's 后跟 0 来表示计数。例如，如果我们在一个组中有 5 个数字，则计数将由 111110 表示。使用这种方法，如果有 1,000 个数字，我们最终会得到 1000 个 1 和 782 个 0，总共 1000 + 782 = 1,782 位用于计数。

偏移量：
最后，每个数字的格式将只是每组的 7 位偏移量。例如，如果 00000 和 00001 是 0-127 组中的唯一数字，则该组的位将为 110 0000000 0000001。假设有 1,000 个数字，则将有 7,000 位用于偏移。

因此，我们假设 1,000 个数字的最终计数如下：

17 (prefix) + 1,782 (counts) + 7,000 (offsets) = 8,799 bits = 1100 bytes

现在，让我们检查通过四舍五入到 128 位的组大小选择是否是组大小的最佳选择。选择 x 作为表示每个组的位数，大小的公式为：

Size in bits = 17 (prefix) + 1,000 + 99,999/2^x + x * 1,000

对 x 的整数值最小化这个方程得到 x=6，它产生 8,580 位 = 1,073 字节。因此，我们理想的存储如下：

组大小：2^6 = 64

组数：1,562

总存储量：1017（前缀加 1）+ 1563（计数中的 0）+ 6*1000（偏移量）= 8,580 位 = 1,073 字节

把这作为一个纯粹的理论问题，把实现放在一边，最有效的方法是在一个巨大的索引表中索引所有可能的 10000 个最后数字的集合。假设您恰好有 1000 个数字，则需要 8000 多位来唯一标识当前集合。不可能有更大的压缩，因为这样你就会有两组被标识为相同的状态。

这样做的问题是，您必须将程序中的 2^8000 个集合中的每一个都表示为 lut，甚至 google 都无法远程执行此操作。

查找将是 O(1)，打印所有数字 O(n)。插入将是 O(2^8000)，理论上是 O(1)，但实际上是不可用的。

在一次采访中，我只会给出这个答案，如果我确定公司正在寻找能够跳出框框思考的人。否则，这可能会让你看起来像一个不关心现实世界的理论家。

编辑：好的，这是一个“实现”。

构建实现的步骤：

取一个大小为 100 000*(1000 选择 100 000) 位的常量数组。是的，我知道这个阵列需要比宇宙中的原子多几个数量级的空间。将这个大数组分成每块 100 000 个块。在每个块中，为最后五位数字的一个特定组合存储一个位数组。

这不是程序，而是一种元程序，它将构建一个巨大的 LUT，现在可以在程序中使用。在计算空间效率时，程序的常量通常不会被计算在内，所以我们在进行最终计算时并不关心这个数组。

以下是如何使用此 LUT：

当有人给你 1000 个号码时，你将前五位数字分开存储。找出你的数组中的哪些块与这个集合匹配。将集合的编号存储在单个 8074 位编号中（称为 c）。

这意味着对于存储，我们只需要 8091 位，我们已经证明这是最佳编码。然而，找到正确的块需要 O(100 000*(100 000 选择 1000))，根据数学规则是 O(1)，但实际上总是需要比宇宙时间更长的时间。

查找很简单：

前五位数字的条带（其余数字将称为 n'）。测试它们是否匹配 计算 i=c*100000+n' 检查 LUT 中 i 处的位是否设置为 1

打印所有数字也很简单（实际上需要 O(100000)=O(1)，因为您总是必须检查当前块的所有位，所以我在上面计算错误）。

我不会称其为“实施”，因为公然无视限制（宇宙的大小和这个宇宙存在的时间，或者这个地球将存在）。但是理论上这是最优解。对于较小的问题，这实际上是可以做到的，有时也会做到。例如 sorting networks 是这种编码方式的一个示例，可以用作递归排序算法的最后一步，以获得很大的加速。

这相当于存储一千个小于 100,000 的非负整数。我们可以使用算术编码之类的东西来做到这一点。

最终，这些数字将存储在排序列表中。我注意到列表中相邻数字之间的预期差异是 100,000/1000 = 100，可以用 7 位表示。还有很多情况需要超过 7 位。表示这些不太常见情况的一种简单方法是采用 utf-8 方案，其中一个字节表示一个 7 位整数，除非设置了第一位，在这种情况下，读取下一个字节以产生一个 14 位整数，除非它的第一位被设置，在这种情况下，下一个字节被读取以表示一个 21 位整数。

所以连续整数之间的差异至少有一半可以用一个字节表示，其余几乎所有的差异都需要两个字节。一些数字，以大于 16,384 的差异分隔，将需要三个字节，但其中不能超过 61 个。然后，平均存储量约为每个数字 12 位，或更少，或最多 1500 字节。

这种方法的缺点是检查数字的存在现在是 O(n)。但是，没有指定时间复杂度要求。

写完后发现上面已经推荐了ruslik的区别方法，唯一的区别就是编码方案。我的可能更简单但效率较低。

只是快速询问我们不想将数字更改为基数 36 的任何原因。它可能不会节省太多空间，但它肯定会节省搜索时间，因为你会看到少于 10 位的数字。或者我会根据每个组将它们分成文件。所以我会命名一个文件（111）-222.txt，然后我只会在其中存储适合该组的数字，然后让它们按数字顺序可查看，这样我总是可以查看文件是否存在。在我进行更大的搜索之前。或者是正确的，我会运行二进制搜索一个文件，看看它是否存在。以及对文件内容的另一次搜索

为什么不保持简单？使用结构数组。

所以我们可以将前 5 位数字保存为常数，所以暂时忘记这些。

65535 是 16 位数字中最多可以存储的，我们可以拥有的最大数字是 99999，它适合第 17 位数字，最大为 131071。

使用 32 位数据类型是一种浪费，因为我们只需要额外的 16 位中的 1 位......因此，我们可以定义一个具有布尔（或字符）和 16 位数字的结构......

假设 C/C++

typedef struct _number {

    uint16_t number;
    bool overflow;
}Number;

这个结构只占用 3 个字节，我们需要一个 1000 个数组，所以总共 3000 个字节。我们将总空间减少了 25%！

至于存储数字，我们可以做简单的按位数学

overflow = (number5digits & 0x10000) >> 4;
number = number5digits & 0x1111;

而反过来

//Something like this should work
number5digits = number | (overflow << 4);

要打印所有这些，我们可以在数组上使用一个简单的循环。检索特定数字当然是在恒定时间内发生的，因为它是一个数组。

for(int i=0;i<1000;i++) cout << const5digits << number5digits << endl;

要搜索一个数字，我们需要一个排序数组。所以当数字被保存时，对数组进行排序（我个人会选择归并排序，O(nlogn)）。现在要搜索，我会采用合并排序方法。拆分数组，看看我们的数字落在哪一个之间。然后仅在该数组上调用该函数。递归执行此操作，直到找到匹配并返回索引，否则，它不存在并打印错误代码。这种搜索会非常快，最坏的情况仍然比 O(nlogn) 好，因为它绝对会在比合并排序更短的时间内执行（每次只递归分割的一侧，而不是两边:)），哪个是 O(nlogn)。

我的解决方案：最佳情况 7.025 位/数字，最坏情况 14.193 位/数字，粗略平均 8.551 位/数字。流编码，无随机访问。

甚至在阅读 ruslik 的答案之前，我就立即想到了对每个数字之间的差异进行编码，因为它会很小并且应该相对一致，但解决方案还必须能够适应最坏的情况。我们有一个包含 100000 个数字的空间，其中仅包含 1000 个数字。在一个完全统一的电话簿中，每个号码都会比前一个号码大 100：

55555-12345 55555-12445 55555-12545

如果是这种情况，它将需要零存储来编码数字之间的差异，因为它是一个已知常数。不幸的是，数字可能与理想的步长 100 不同。我将对与理想增量 100 的差异进行编码，因此如果两个相邻的数字相差 103，我将编码数字 3，如果两个相邻的数字相差 92，我将编码将编码-8。我将理想增量 100 的增量称为“方差”。

方差的范围可以从 -99（即两个连续的号码）到 99000（整个电话簿由号码 00000…00999 和一个附加的最远号码 99999 组成），这是 99100 个可能值的范围。

我的目标是分配最小的存储空间来编码最常见的差异并在遇到更大的差异时扩展存储空间（例如 ProtoBuf 的 varint）。我将使用 7 位的块，6 位用于存储，并在末尾使用一个附加标志位来指示此差异与当前块之后的附加块一起存储，最多三个块（这将提供最大3 * 6 = 18 位存储，有 262144 个可能的值，比可能的方差数（99100）多。每个附加块后面的提升标志都有更高的位，所以第一个块总是有位 0-如图5所示，可选的第二个块有6-11位，可选的第三个块有12-17位。

单个块提供 6 位存储，可容纳 64 个值。我想映射 64 个最小的方差以适应该单个块（即 -32 到 +31 的方差），所以我将使用 ProtoBuf ZigZag 编码，最大方差为 -99 到 +98（因为不需要对于超过 -99 的负方差），此时我将切换到常规编码，偏移 98：

Variance  |  Encoded Value
-----------+----------------
    0      |       0
   -1      |       1
    1      |       2
   -2      |       3
    2      |       4
   -3      |       5
    3      |       6
   ...     |      ...
  -31      |      61
   31      |      62
  -32      |      63
-----------|--------------- 6 bits
   32      |      64
  -33      |      65
   33      |      66
   ...     |      ...
  -98      |      195
   98      |      196
  -99      |      197
-----------|--------------- End of ZigZag
   100     |      198
   101     |      199
   ...     |      ...
  3996     |     4094
  3997     |     4095
-----------|--------------- 12 bits
  3998     |     4096
  3999     |     4097
   ...     |      ...
 262045    |    262143
-----------|--------------- 18 bits

方差如何编码为位的一些示例，包括指示附加块的标志：

Variance  |  Encoded Bits
-----------+----------------
     0     |  000000 0
     5     |  001010 0
    -8     |  001111 0
   -32     |  111111 0
    32     |  000000 1  000001 0
   -99     |  000101 1  000011 0
   177     |  010011 1  000100 0
 14444     |  001110 1  100011 1  000011 0

因此，示例电话簿的前三个数字将被编码为比特流，如下所示：

BIN 000101001011001000100110010000011001   000110 1     010110 1 00001 0
PH#           55555-12345                 55555-12448     55555-12491
POS                1                           2               3

最好的情况，电话簿是均匀分布的，没有两个电话号码的方差大于 32，因此每个号码使用 7 位加上 32 位作为起始号码，总共 32 + 7*999 = 7025 位。混合场景，其中 800 个电话号码的方差适合一个块 (800 * 7 = 5600)，180 个号码适合两个块 (180 * 2 * 7 = 2520)，19 个号码适合三个块 (20 * 3 * 7 = 399)，加上最初的 32 位，总共 8551 位。最坏的情况，25 个数字适合三个块（25 * 3 * 7 = 525 位），其余 974 个数字适合两个块（974 * 2 * 7 = 13636 位），加上 32 位用于盛大的第一个数字共有 14193 位。

Amount of encoded numbers   |
 1-chunk | 2-chunks | 3-chunks | Total bits
---------+----------+----------+------------
   999   |    0     |    0     |   7025
   800   |   180    |    19    |   8551
    0    |   974    |    25    |  14193

我可以看到可以执行四个额外的优化来进一步减少所需的空间：

第三块不需要完整的七位，它可以只有五位并且没有标志位。可以对数字进行初始传递，以计算每个块的最佳大小。也许对于某个电话簿，最好让第一个块有 5+1 位，第二个 7+1 和第三个 5+1。这将进一步将大小减少到至少 6*999 + 32 = 6026 位，加上两组三个位来存储块 1 和 2 的大小（块 3 的大小是所需 16 位的剩余部分），总共6032 位！相同的初始通道可以计算出比默认 100 更好的预期增量。也许有一个电话簿从 55555-50000 开始，所以它有一半的数字范围，所以预期增量应该是 50。或者可能存在非线性可以使用分布（可能是标准偏差）和其他一些最佳预期增量。这将减少典型的方差，并可能允许使用更小的第一个块。可以在第一遍中进行进一步的分析，以允许对电话簿进行分区，每个分区都有自己的预期增量和块大小优化。这将允许电话簿的某些高度统一的部分使用较小的第一块大小（减少消耗的比特数）和非统一部分的较大块大小（减少在继续标志上浪费的比特数）。

真正的问题是存储五位数的电话号码。

诀窍是您需要 17 位来存储 0..99,999 的数字范围。但是在传统的 8 字节字边界上存储 17 位是一件麻烦事。这就是为什么他们会问你是否可以通过不使用 32 位整数在不到 4k 的时间内完成。

问题：所有数字组合都可能吗？

由于电话系统的性质，可能的组合可能少于 65k。我会假设是的，因为我们谈论的是电话号码中的后五个位置，而不是区号或交换前缀。

问题：这个列表是静态的还是需要支持更新？

如果是静态，那么当需要填充数据库时，计算位数 50,000 并且位数 > = 50,000。分配 两个数组 uint16 的适当长度：一个用于 50,000 以下的整数，一个用于更高的集合。在较高的数组中存储整数时，减去 50,000，从该数组中读取整数时，加上 50,000。现在您已将 1,000 个整数存储在 2,000 个 8 字节字中。

00001 = 00001
12345 = 12345
50001 = reserved
00001 = 50001
12345 = 62345
65000 = end-of-list