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

算法 大神们看过来

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

    有这么个需求:

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

    应该能压缩很多内容。
        3
    ChanneW   2015-09-08 21:50:31 +08:00
    干嘛不直接就在服务端给 ip 表中的每个客户端发:“你在我的名单里,自己看着办吧!”。
        4
    hahastudio   2015-09-08 21:53:00 +08:00
    为什么不是客户端向服务端查询自己在不在这个列表里?
        5
    leiz   2015-09-08 22:10:01 +08:00
    对咯,反过来做,客户端去服务器查询自己是否在列表里不是更好?
        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 ……
        7
    htfy96   2015-09-08 22:18:19 +08:00
    @htfy96 刚刚发现例子的开头 0/1 反了,当然这样处理会比较慢,可以考虑字节对齐等方法
        8
    pimin   2015-09-08 22:18:58 +08:00
    感觉逻辑应该在服务端完成,通知客户端执行即可。
        9
    adrianzhang   2015-09-08 22:20:07 +08:00
    用 celery??
        10
    hienchu   2015-09-08 22:28:57 +08:00
    其实我想说,单个 IP 按 4 个整数才 16Byte , 10000 个 ip 的 list 也才 160k ,单个 server 向 10000 个客户端推送 160k 数据,压力其实不大
        11
    iyangyuan   2015-09-09 08:22:46 +08:00 via iPhone   ♥ 1
    这不是算法问题,这是设计问题
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4180 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 24ms · UTC 02:02 · PVG 10:02 · LAX 18:02 · JFK 21:02
    ♥ Do have faith in what you're doing.