数学差，这里怎么算的？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3389 天前的主题，其中的信息可能已经有所发展或是发生改变。

无意看了篇文章

http://www.jointforce.com/jfperiodical/article/925?m=d03

「这个稀疏的数列存储在5字节的序列中，3个字节表示尾部，2个字节表示数据。尾部按照升序排列，所以搜索变的简单了（二分搜索）。

对于持久化存储，具有相同前缀的数字存储在一个文件中，该文件的第一个字节是类型的指示框。这些共需1.8GB的空间，这些数据可以存储在内存中，通过webserver进行发布。」

1. 前面不是说按偏移来存吗？每固定一个头四位，需要10^6 * 2Byte(block_size) = 2MB，怎么突然又说要用3个 Byte 来存尾六位数了？
2. 1.8GB 是怎么算的？

郁闷啊。

谢谢

字节

1.8gb

尾部

5 条回复 • 2015-07-31 23:21:20 +08:00

Xs0ul

2015-07-31 14:15:07 +08:00

1、尾6位有10^6种，2个字节只有65536种，所以要3个字节

final0pro

2015-07-31 14:27:23 +08:00

@Xs0ul 对我知道。但是之前不是说拿偏移来存尾六位的吗？

address 0 = 000, 000结尾的信息
address 1 = 000, 001结尾的信息
...
address 999,999 = 999,999结尾的信息

1,000,000个电话，每个电话还需要2Byte 的信息

->

1M * 2B = 2MB，这种不需要存尾六位的电话呀？

Xs0ul

2015-07-31 15:09:58 +08:00

@final0pro 他后面的方法应该已经不用数组下标来表示那6位了，要不然也不需要二分查找了，直接按下标来就行了

Xs0ul

2015-07-31 15:23:55 +08:00

@final0pro 我看了下原文，其实是翻译的不好。

原文说的是在这些电话号码里，不同前缀的号码组，有的比较稀疏，有的比较密集（比如国内138这种老手机号就比较密集，新虚拟运营商的那种号码就比较稀疏）。

对于比较密集的，就是用你说的那种，把所有后缀都存上，用flag来表示是否存在；对于稀疏的，就用5字节来存储存在的号码。

final0pro

2015-07-31 23:21:20 +08:00

@Xs0ul many thanks!