Contents

换阵营后忙活了几个月,终于有空写点东西了。想起几个月前在网易的面试,个别题目答得不太理想,后来想了许多,现在拿出来写写。

问题大致是这样的:

这里有个十万个IP组成的地址库,记录了一些IP区间和地理位置的对应关系,要求对于一个给定IP,可以快速知道与之相关的位置信息,一个IP可能落在多个IP区间内。

遍历比较当然是一种可行的方案,如果只是偶尔查一条,就算是百万量级其实是没所谓的。而且实现也比较简单,比如只要对左区间排序,再把目标IP从数组上从前往后扫过去,直到找到自己在有序序列上的位置,就可以统计出在哪些区间内了,但是QPS什么的肯定就低的毫无悬念了,

可能是觉得这个方案太低级,面试的时候被我直接跳过了…

然后我首先想到了以前A题的时候解过的一类求点和多少条平行线段重叠的问题,所以自然想到可以用线段树去解。和现在这个其实是一个问题。

于是我把我想的和面试官说了下,我说看样子应该可以用线段树来解决这个问题。但对面问我怎么构造线段树,我一时又有点晕,自己想了几种方案都有问题,最后作罢,只好说有些细节没想明白。

归根结底还是这种数据结构以前也印象不深,又太久没用给忘的差不多了…其实既然想到了线段树,甚至都不需要做什么复杂的改造,简直是直接照搬过来就解决了。

因为IPv4的地址范围是刚好可以用4个字节存储的,刚好对应于uint32的数值空间(也就是说每个IP都有唯一uint32对应,倒是省了Hash这一步了)。

于是只要对0,MAX_UINT32区间进行多级二分处理,这样我们就有了一颗MAX_UINT32个节点的满二叉树了(同时也是所谓的线段树)。现在看看如何使用这个数据结构解决IP问题。

初始化地址库:
对于每一个IP段,从ROOT(0,MAX_UINT32)开始,依次沿路径向下,依次比较IP段和节点之间的关系,会有如下三种情况:

  1. IP段位于节点左半段
  2. IP段位于节点右半段
  3. IP段同时属于左右半段

对于第1种,我们把IP段下方到左子节点继续比较,同理第二种放到右子节点,第三种则直接放到当前节点上(弄个列表塞进去)。

这样一来,当我们需要查询一个IP被哪些IP段覆盖的时候,只需要先沿线段树向下,找到一个能完全包含这个IP的最小区间,然后重新往上爬,把路上遇到的每个节点上存的地址段都拿出来,这些便全是覆盖了这个IP的地址段了。

虽然已经是个log(n)级的优质算法,但实现上还有些细节问题要考虑下。比如说大量节点导致内存浪费啦,每个节点上的列表如何实现啦之类的。

简单想了下,其实作为IP段查询这种需求,完全没必要把线段的粒度细化到1,损失几个精度对内存那都是2^n级的节约。虽然具体定到什么精度还要看根据数据特点而定,但只需要讨论下这种损失精度的情况下如何处理问题就可以了。

比如说我们把精度定为16,那么叶节点就是类似[0,15],[16,31]…这种。那么对于粒度更小的IP段,比如(0.0.0.0-0.0.0.5),我们反正就都先往[0,15]的节点里塞。

但因为数据这样表示,对于一个给定IP,这个IP向下找到的叶节点上的IP段就未必都是覆盖了这个IP的IP段了,所以对于叶节点我们需要有特殊的判断方法——遍历比较一遍。之后就一切如旧。

采用这种方式,极端情况下在叶节点处应该要比较128(16*16再去掉一半无效值)次左右。再加上从ROOT到叶节点需要比较20多次,最差情况是150多次比较得到结果。将精度提高到8,最差情况改善到50多次。

而对于各节点上IP段列表的表示,只要挂个链表Head指针就可以了,并不会构成太大负担。

算法到这里就结束了。

但我一直在想这种问题除了IP168这种网站可能会用之外难道还会有其它什么用处嘛?刚好,今天在工地看到一篇讲“接入层调度方案”的文章发现正是产生了这种需求。

看起来高大上的标题,其实是人家觉得把客户端连服务器的IP选择交给DNS去做,但DNS不够聪明,所以自己搞套服务器来根据客户IP返回最优的svrIP,这种情况下就需要对IP做些识别了,正好用上。

其实再多想想,这和以前接触的那个游戏场景AOI(对象视野)管理的QuadTree何其相似,只不过是从二维降成一维而已。

反过来,这个需求我们用游戏化的角度来理解IP区间问题:

一条路上有许多怪物,每个怪物有自己的视野范围(左边界,右边界),问,当一个玩家在这条路的某处出现时,会引起多少只怪物的注意?

Contents