存储100万个电话号码
存储100万个电话号码的最有效的方式是记忆方式吗？
显然这是Google的面试问题，请给出您的想法。
如果记忆是我们最大的考虑，那么我们根本不需要存储数字，只需要存储i和i + 1之间的差值。
现在，如果数字范围从200 0000 – 999 9999，则有7,999,999个可能的电话号码。 既然我们有一百万个数字，而且假设它们是均匀分布的，那么序列号n_i和n_i + 1之间的期望距离为E = n_i + 1 – n_i〜8（3比特）。 因此，对于一个32位的int，我们可能会存储多达10个连续的偏移量（〜400kb最佳的总内存占用量），但是我们可能会有一些情况需要大于8的偏移量（也许我们有400或1500？）。 在这种情况下，我们可以简单地保留int的前2位作为头部，告诉我们用什么帧大小来读取它所存储的位。 例如，也许我们使用：00 = 3×10,01 = 5×6,10 = 7×4,11 = 1 * 30。
用ASCII编写，空格分隔。
使用您最喜爱的压缩algorithm对结果string进行压缩。 如果顺序不重要，先sorting它们可能有助于压缩，使您更加紧密地重复在一起。
哦，你想要有效的随机访问？ 那你应该说。
可能的解决scheme是
- sorting数字
- 编码从一个数字到下一个数字的三angular洲
三angular洲频率分布将高度偏斜。
我使用7 + 3 + 3 + …位编码对增量进行了简单的类似BER的打包方法的实验; 编码function是
def delta_write(x, b1, b2): lim = 1 << (b1 - 1) if x < lim: bit_write(x, b1) else: bit_write(lim + (x & (lim - 1)), b1) delta_write(x >> (b1 - 1), b2, b2)
（两个参数7和3是通过实验确定的）
采用这种方法，我从一千个随机前缀中选出了前五位数字，每个数字平均8.83位（打包大小1104188），得到了一百万个10位数字。
首先，我注意到它们从不以0开始，因为0在开始时被用作转义字符。 所以我可以简单地把电话号码视为整数。 如果不是这种情况，我只是简单地在数字前加一个“1”，然后将其转换为整数。 这不会显着影响编码效率（几个字节的开销可能是不变的）。 如果电话号码内部10位以外的其他字符的基数高于10，则这会损害效率。
我会按大小顺序排列。 然后计算差异。 然后使用protobuf作为压缩重复字段序列化差异。
这种方法类似于RexKerr的方法，除了我使用huffman编码器上的protobuf的懒惰解决scheme。 由于protobuf整数编码是通用的，并且不考虑电话号码的概率分布，所以可能有点大一些。 但是编码更容易，因为我只需要使用现有的protobuf序列化器。 一旦你超过了UInt64的大小，这将有问题，即有超过19位数字的电话号码。 文件格式仍然支持，但大多数实现不会。
没有索引访问时间将是非常糟糕的，但它应该是相当紧凑的。
作为特殊的数据结构的三元search树将是有效的，并且仍然能够（作为）部分匹配。
霍夫曼编码数字块可能会给出非常好的结果。 如果数字是混合types的（例如一些美国，一些海外包括访问代码），则需要另外几个位来指定它们是哪种types（以及哪些块使用）。
如果数字在一些小的范围内，例如七位数，那么最紧凑的方式就是把它们当作整数，对它们进行sorting，然后存储（霍夫曼编码的）值的差异。 例如，7位数字（10 ^ 7个可能性）中的10 ^ 6个数字，您希望每个数字需要大约log2（10）〜= 3.3位。
如果您查看北美编号scheme的数据字段表示，则可以得出结论：在每个区号中，1+ NPA + NXX + xxxx的美国电话号码可以存储在每个电话号码字段less于22位的位中。 添加区号和代表任何美国（加拿大）电话号码的数据可以舒适地适合32位。 这是作为一个位字段的表示 – 不是一个int。
但是，你的想法不应该以美国为中心。 当然，问题不仅仅是一个练习，就是将100万个电话号码压缩成尽可能less的位数。
美国的电话号码可以短至3位（内部集团电话拨号计划）至22位（1 + NPA + NXX + xxxx + 11位内部集团电话拨号计划）。 如果电话号码限于ITU指定的号码格式 ，则最多可以有15位数字加上“+”的1位。
然后你应该定义一个3位到22位（或ITU的15位）的电话号码的可变位字段表示，每个位字段有一个X位标题字段来表示字段的格式。
然后把这些位字段放入一个压缩位数组中 。 可能的是，位数组可以用索引或其他方法索引。
其效率基于100万个电话号码的格式，您希望以多快的速度访问这些电话号码，以及这种数据结构在将来使用不同格式的电话号码的灵活性如何。 这不仅仅是为了“正确的”答案恕我直言，计数位。
我猜想一个无符号的Int32或国际号码无符号的Int64
使用32位无符号整数将是4MB
这真的取决于你想要在存储的数据库上运行什么操作。
简单的方法是使用无符号整数，如果你只是需要存储它们，可能使用字典的原始文本表示上的压缩可能会更小。
在面试时，这个问题的关键是要确定申请人的解决问题的能力。 因为这个问题的重点是记忆效率 ，我认为正确的答案是问采访者：“电话号码是国际的，还是只限于一个国家？ 如果这些数字只限于一个国家，那么通过国家和城市分配电话号码的简单规则，可以简化记忆效率最大化的任务。
我想我们可以在这里使用大小为100万的位向量。
Java示例：
private BitSet dir = new BitSet(1000000); public void addTelephoneNumber(int number) { dir.set(number); } public void removeTelephoneNumber(int number) { if (dir.get(number)) { dir.flip(number); } } public boolean isNumberPresent(int number) { return dir.get(number); }
假设我们假定每个电话号码与美国（3位地区代码）格式 – （7位数字）一致，
这是一个10位数字。
但是，在处理电话号码时有接触的规则。 他们稀less，一个，这意味着不是所有可能的地区代码被使用。 在这种情况下，一棵简单的树就可以了。 我的意思是想想…你只需要269 + 26加拿大。 这是相当小的，你已经削减了很大一部分空间PLUS增加了search时间。 不仅如此，还可以增加位置信息。
之后，你有一个7位数的号码。 这可以存储在一个单一的32位整数。 sorting插入，你有一个非常快的检索机制，因为你可以做二进制search的数字的其余部分。
800万比特，每个比特1（使用）或0（可用）为800万个数字中的一个例子
100 0000 900 0000 = 8 million phone numbers, bit 1 = 1000000 and bit 8 million = 9000000
/******************************************************************************** Filename: Phone_Numbers.c Author: Paul Romsky Company: Autoliv AEL Date: 11 MAR 2013 Problem: What is the most efficient way, memory-wise, to store 1 million phone numbers? Caveats: There is no mention if the numbers are contiguous or not, so, to save space the numbers should be contiguous. The problem (as a specification) is rather vague and leaves a lot to interpretation, so many different methods may be desired, but which one(s) desired is not surely known. Are the phone numbers just the extension (last four digits), or do they include the exchange (the leading 3 digits), or do they also include area code and/or international numbers? There is no mention of the first number, only the range of numbers, so the first number 000-0000 is used. Although many numbers are not normally used, they could in fact be used as valid number sequences within the phone companies and are thus phone numbers nonetheless. Solution: A simple algorithm. If the numbers are not contiguous a fractal algorithm could be used. A standard ANSI C compiler should pack this program into a very small assembly module of only a few bytes. Revisions: Rev Date By Description --- ----------- -------------------- ------------------------------------------- - 11 MAR 2013 P. Romsky Initial Coding ********************************************************************************/ /* Includes */ #include <stdio.h> /* Functions */ /******************************************************************************** * * Main Entry Point * ********************************************************************************/ int main() { unsigned int Number; /* 1,000,000 Phone Number Storage 000-0000 through 999-9999 */ for(Number = 0000000; Number < 10000000; Number++) { /* Retrieve Numbers */ printf("%07u\n", Number); } return 0; } /* End */
