存储了一百万个电话号码

在内存方面，存储100万个电话号码最有效的方法是什么？

显然这是谷歌的一个面试问题，请给出你的想法。

48665 次浏览
小开

我猜是未签名的 Int32或者国际号码是未签名的 Int64

使用32位无符号整数，大小为4MB

小开

这确实取决于要在存储的数据库上运行哪些操作。

简单的方法是使用无符号整数，如果只需要存储它们，那么使用字典对原始文本表示进行一些压缩可能会小一些。

小开

用空格分隔的 ASCII 编写它们。

使用您喜欢的压缩算法压缩生成的字符串。如果顺序不重要，那么首先对它们进行排序可能有助于压缩，让你的重复次数更加紧密。

哦，你想要高效率的随机访问吗? 那你应该说。

小开

对数字块进行霍夫曼编码可能会得到非常好的结果。如果这些数字是混合类型的(例如，一些美国数字，一些海外数字，包括访问代码) ，你需要另外几个位来指定它们是哪种类型(因此要使用哪些块)。

如果数字的范围很小——例如7位数——存储它们最简洁的方法可能是将它们视为整数，对它们进行排序，并存储(霍夫曼编码的)值的差异。例如，对于7位(10 ^ 7种可能性)的10 ^ 6个数字，每个数字大约需要 log2(10) ~ = 3.3位。

小开

在求职面试中，这个问题的重点是评估应聘者解决问题的能力。因为问题的焦点是 记忆效率，在我看来，正确的答案是问面试官: “这些电话号码是国际性的，还是仅限于一个国家?”如果电话号码仅限于一个国家，那么每个国家都有按州和城市分配电话号码的简单规则，这就简化了最大限度地提高存储效率的任务。

小开

如果你查看 北美电话区号计划的数据字段表示，你会得出结论: 在每个区号中，1 + 新人民军 + NXX + xxxx 的美国电话号码可以以每个电话号码字段少于22位的形式存储。添加区号和数据代表任何美国(加拿大)电话号码可以舒适地适合在32位。这是位字段表示，而不是 int。

然而，你在这方面的想法不应该是以美国为中心的。当然，问题不仅仅是把100万个电话号码压缩到尽可能少的位数。

美国电话号码可短至3位(内部 PBX 拨号计划) ，长至22位(1 + NPA + NXX + xxxx + 11位内部 PBX 拨号计划)。如果电话号码仅限于 国际电联指定的数字格式，那么最多可以有15位数字加上1位的“ +”。

然后，您可能应该定义一个可变位字段表示，表示3位到22位(或 ITU 为15位)之间的任何电话号码，每个位字段都有一个 X 位头字段来表示字段的格式。

然后将这些位字段放入压缩的 位数组位数组中。位数组可以用 试试或其他方法进行索引。

这种方法的效率取决于100万个电话号码的格式、访问它们的速度以及未来更多不同格式的电话号码的数据结构的灵活性。恕我直言，这不仅仅是为“正确”答案计数。

小开

首先，我观察到它们从不以0开始，因为0在开始时被用作转义字符。所以我可以简单地把电话号码看作整数。如果不是这样的话，我会简单地在数字前面加上一个“1”，然后把它转换成整数。这不会显著影响编码效率(可能是几个字节的固定开销)。如果电话号码中的10位数字之外还有其他字符，则以大于10的基数进行编码。但这会影响效率。

我会按尺寸升序排列。然后计算差异。然后使用 Protobuf 作为打包的重复字段对差异进行序列化。

这个方法类似于 RexKerr 的方法，只不过我使用的是针对 Huffman 编码器的 Protobuf 的惰性解决方案。可能会大一点，因为 Protobuf 的整数编码是通用的，没有考虑到电话号码的概率分布。但是编写代码要容易得多，因为我只需要使用一个现有的原型程序设计器。一旦您超过了 UInt64的大小，即电话号码长度超过19位，就会出现问题。文件格式仍然支持它，但是大多数实现都不支持。

如果没有索引访问时间将非常糟糕，但它应该相当紧凑。

小开

如果内存是我们最大的考虑因素，那么我们根本不需要存储数字，只需要存储 i 和 i + 1之间的 delta。

现在，如果号码范围从2000000-9999999，那么有7,999,999个可能的电话号码。由于我们有100万个数，并且假设它们是均匀分布的，我们在序列数 n _ i 和 n _ i + 1之间有一个 E = n _ i + 1-n _ i ~ 8(3位)的期望距离。所以对于一个32位的 int，我们可以存储多达10个连续的偏移量(大约400kb 的最佳总内存占用量) ，但是在某些情况下，我们可能需要一个大于8的偏移量(也许我们有400个，或者1500个.在这种情况下，我们可以简单地保留整型数的前2位作为头，它告诉我们使用什么帧大小来读取它存储的位。例如，我们可以使用: 00 = 3x10,01 = 5x6,10 = 7x4,11 = 1 * 30。

小开

一个可能的解决办法是

  1. 把数字分类
  2. 从一个数字到下一个数字的增量编码

三角洲的频率分布会非常不平衡。

我做了一个实验，使用一个简单的类似于 BER 的打包方法，用一个7 + 3 + 3 + ... 位编码，编码函数是

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)

通过这种方法，我得到了100万个10位数字，前5位数字是从1000个随机前缀中选出的，平均每个数字为8.83位(封装大小为1104188)。

小开

我想我们可以在这里使用1百万大小的比特向量。

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);
}
小开

一个三元搜索树是一个特殊的 trie 数据结构，它可以提高内存效率，并且仍然可以启用(作为 trie)部分匹配。

Http://en.wikipedia.org/wiki/ternary_search_tree

小开

假设我们假设每个电话号码与美国格式(3位区号)-(7位数字号码)一致

这是个10位数的号码。

然而，在处理电话号码的时候是有规则的。首先，它们是稀疏的，这意味着并非所有可能的区号都被使用。在这种情况下，一个简单的树就是 a-ok。我的意思是想想看... 你只需要269 + 26加拿大。这是相当小的，你已经削减了大部分的空间加上增加搜索时间。不仅如此，它还可以增强位置信息。

之后，你会得到一个7位数的数字。这可以存储在单个32位整数中。对插入进行排序，你就有了一个相当快的检索机制，因为你可以对数字的其余部分进行二进制搜索。

小开

对于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 */

提交答案