V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
blackimpl
V2EX  ›  数学

算法 大神们看过来

  •  
  •   blackimpl · 2015-09-08 21:10:37 +08:00 · 4544 次点击
    这是一个创建于 3341 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有这么个需求:

    服务端 push 一个 ip 列表到所有的客户端, 客户端拿到这个 ip 列表, 再判断这个列表里面有没有当前机器的 ip, 如果有的话, 执行特定的逻辑。
    
    现在的问题是, 如果服务端要推送到 10000 台客户端的话, 这个 ip 类列表会过长, 增加服务端压力。
    
    怎么在服务端压缩这些 ip 后, 客户端接收到这个 ip 列表的压缩内容后, 还可以根据自身 ip, 判断, 服务器端推送的内容是否包含当前机器 ip ?
    
    ps : 只考虑 ipv4.
    
    11 条回复    2015-09-09 08:22:46 +08:00
    blackimpl
        1
    blackimpl  
    OP
       2015-09-08 21:11:46 +08:00
    大神求教
    keroro520
        2
    keroro520  
       2015-09-08 21:45:49 +08:00
    根据 ip 列表建一棵字典树,用这棵字典树替代 ip 列表发送给客户端。

    应该能压缩很多内容。
    ChanneW
        3
    ChanneW  
       2015-09-08 21:50:31 +08:00
    干嘛不直接就在服务端给 ip 表中的每个客户端发:“你在我的名单里,自己看着办吧!”。
    hahastudio
        4
    hahastudio  
       2015-09-08 21:53:00 +08:00
    为什么不是客户端向服务端查询自己在不在这个列表里?
    leiz
        5
    leiz  
       2015-09-08 22:10:01 +08:00
    对咯,反过来做,客户端去服务器查询自己是否在列表里不是更好?
    htfy96
        6
    htfy96  
       2015-09-08 22:16:24 +08:00
    提供一个蛋疼的解法……

    首先每个 ip 可以转换成 0~2^32-1 之间的数,用串流表示比用 ascii 表示会小一点:
    192.168.0.1 -> 表示成 16 进制 C0A80001 只要 4 个字节……
    同理
    192.168.0.100 -> C0A80064
    192.168.2.40 -> C0A80228

    考虑到网段时常是连续的,可以先排个序,用如下表示一个 ip :
    0 开头表示就是这个 ip 地址就如后面的 32 位表示
    1 开头表示相对于上一个地址的偏移量。。。偏移量用 16 位表示

    所以上面这若干个 ip 就可以表示成
    1C0A80001 (33bits )
    00063 (17bits )
    00164 (17bits )

    这样总共只需要 67bits ,比之前的 3*4*8 = 96bits 少很多……

    而且这个方法不需要建树,编码和解码都比较方便,最坏情况也就多了 1 个 bit ……
    htfy96
        7
    htfy96  
       2015-09-08 22:18:19 +08:00
    @htfy96 刚刚发现例子的开头 0/1 反了,当然这样处理会比较慢,可以考虑字节对齐等方法
    pimin
        8
    pimin  
       2015-09-08 22:18:58 +08:00
    感觉逻辑应该在服务端完成,通知客户端执行即可。
    adrianzhang
        9
    adrianzhang  
       2015-09-08 22:20:07 +08:00
    用 celery??
    hienchu
        10
    hienchu  
       2015-09-08 22:28:57 +08:00
    其实我想说,单个 IP 按 4 个整数才 16Byte , 10000 个 ip 的 list 也才 160k ,单个 server 向 10000 个客户端推送 160k 数据,压力其实不大
    iyangyuan
        11
    iyangyuan  
       2015-09-09 08:22:46 +08:00 via iPhone   ❤️ 1
    这不是算法问题,这是设计问题
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1133 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 22:57 · PVG 06:57 · LAX 15:57 · JFK 18:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.