V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
final0pro
V2EX  ›  问与答

数学差,这里怎么算的?

  •  
  •   final0pro · 2015-07-31 13:45:10 +08:00 · 1714 次点击
    这是一个创建于 3163 天前的主题,其中的信息可能已经有所发展或是发生改变。
    无意看了篇文章

    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 是怎么算的?


    郁闷啊。

    谢谢
    5 条回复    2015-07-31 23:21:20 +08:00
    Xs0ul
        1
    Xs0ul  
       2015-07-31 14:15:07 +08:00
    1、尾6位有10^6种,2个字节只有65536种,所以要3个字节
    final0pro
        2
    final0pro  
    OP
       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
        3
    Xs0ul  
       2015-07-31 15:09:58 +08:00
    @final0pro 他后面的方法应该已经不用数组下标来表示那6位了,要不然也不需要二分查找了,直接按下标来就行了
    Xs0ul
        4
    Xs0ul  
       2015-07-31 15:23:55 +08:00   ❤️ 1
    @final0pro 我看了下原文,其实是翻译的不好。

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

    对于比较密集的,就是用你说的那种,把所有后缀都存上,用flag来表示是否存在;对于稀疏的,就用5字节来存储存在的号码。
    final0pro
        5
    final0pro  
    OP
       2015-07-31 23:21:20 +08:00
    @Xs0ul many thanks!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5870 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 02:20 · PVG 10:20 · LAX 19:20 · JFK 22:20
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.