算法 大神们看过来

[blackimpl]

有这么个需求:

服务端 push 一个 ip 列表到所有的客户端, 客户端拿到这个 ip 列表, 再判断这个列表里面有没有当前机器的 ip, 如果有的话, 执行特定的逻辑。

现在的问题是, 如果服务端要推送到 10000 台客户端的话, 这个 ip 类列表会过长, 增加服务端压力。

怎么在服务端压缩这些 ip 后, 客户端接收到这个 ip 列表的压缩内容后, 还可以根据自身 ip, 判断, 服务器端推送的内容是否包含当前机器 ip ？

ps ： 只考虑 ipv4.

[blackimpl]

大神求教

[keroro520]

根据 ip 列表建一棵字典树，用这棵字典树替代 ip 列表发送给客户端。

应该能压缩很多内容。

[ChanneW]

干嘛不直接就在服务端给 ip 表中的每个客户端发：“你在我的名单里，自己看着办吧！”。

[hahastudio]

为什么不是客户端向服务端查询自己在不在这个列表里？

[leiz]

对咯，反过来做，客户端去服务器查询自己是否在列表里不是更好?

[htfy96]

提供一个蛋疼的解法……

首先每个 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]

@htfy96 刚刚发现例子的开头 0/1 反了，当然这样处理会比较慢，可以考虑字节对齐等方法

[pimin]

感觉逻辑应该在服务端完成，通知客户端执行即可。

[adrianzhang]

用 celery??

[hienchu]

其实我想说，单个 IP 按 4 个整数才 16Byte ， 10000 个 ip 的 list 也才 160k ，单个 server 向 10000 个客户端推送 160k 数据，压力其实不大

[iyangyuan]

这不是算法问题，这是设计问题