判断 ip 是否在一个超大 ip 集中（识别国内 ip）

原文地址： https://www.ikaze.cn/article/65

前几天发帖/t/785801讨论匹配大量 ip 的方法，经过几天的思考，把最终使用的方法分享给大家。

1. 通过 ip 位置数据库

比较有名的服务商有：ipip（付费）， maxmind （付费），纯真 （免费）。

但在这个应用场景下，我们并不需要具体的位置信息，类似的方案会浪费不必要的内存因此放弃。

2. 利用 ip 的连续性

后面两个方法有个前提：ip 地址列表中大部分是连续的。

这里我们已有了国内 ip 地址列表（已有开源的库，很好找，另外我用的这个库已经把 ip 合并为了 CIDR 格式的地址）。

我们先通过二进制把 ip 转为可直接比较的数字，再把连续的 ip 变为 (start_ip, end_ip) 这样的集合，就可以利用二分法快速查找了。

import ipcalc

class ChinaIp:
    def __init__(self):
        self.data = []

    def load(self, cidr_file='data/china_ip_list.txt'):
        with open(cidr_file, 'r')as f:
            for s in f.readlines():
                self.add(s.strip())

    def add(self, cidr):
        n = ipcalc.Network(cidr)
        self.data.append((n.host_first().ip, n.host_last().ip))

    def search(self, ip):

        l = 0
        r = len(self.data) - 1
        while l <= r:
            mid = (l + r) // 2
            if self.data[mid][0] <= ip <= self.data[mid][1]:
                return True
            elif self.data[mid][0] > ip:
                r = mid - 1
            elif self.data[mid][1] < ip:
                l = mid + 1
            else:
                return False
        return False

    def __contains__(self, item):
        ip = ipcalc.IP(item).ip
        return self.search(ip)
        
china_ip = ChinaIp()
china_ip.load()
print('223.70.163.83' in china_ip)

3. 利用 CIDR 的特性

CIDR 是形如 x.x.x.x/n 这样的地址，它表示一组网络地址相同的 ip，其中 n 表示前 n 位作为网络地址。

根据 CIDR 的特性，我们可以得到这样的结论：同一 CIDR 下的 ip，其网络地址是相同的。

因此我们可以把所有国内 cidr 地址的网络地址取出，放字典；对于一个 ip，尝试可能的网络地址（即 n ），看其是否在字典中。

import ipcalc

class ChinaIp(object):
    def __init__(self):
        self.data = {}


    def load(self, cidr_files='data/china_ip_list.txt'):
        with open(cidr_files, 'r')as f:
            cidr_list = f.readlines()

        for cidr in cidr_list:
            self.insert(cidr.strip())

    def insert(self, cidr):
        network = ipcalc.Network(cidr)
        self.data[str(network.netmask())]=True

    def search(self, netmask: str) -> bool:

        for i in netmask.split('.'):
            node = node.children.get(i, None)
            if node is None:
                return False
            if node.is_end:
                return True
        return False

    def __contains__(self, ip):
        for i in range(1,33):
            if self.search(str(ipcalc.Network(f'{ip}/{i}').netmask())):
                return True
        return False
        
china_ip = ChinaIp()
china_ip.load()
print('223.70.163.83' in china_ip)

这个算法看起来没啥毛病，但实际测试中速度比第二种慢了很多，耗时的地方在比较时必须循环所有 n，而二分法可以快速的排除不可能的部分。

对于这种情况，有两种优化方法：

1. 随机 n 的列表

class ChinaIp(object):

    ...
    
    def __contains__(self, ip):
        l = list(range(1, 33))
        random.shuffle(l)
        for i in l:
            if self.search(str(ipcalc.Network(f'{ip}/{i}').netmask())):
                return True
        return False

这种方法在测试中，时间减少了一半多。

2. 排除不会出现的 n

class ChinaIp(object):
    def __init__(self):
        ...
        self.mask_list = []
    ...

    def insert(self, cidr):
        network = ipcalc.Network(cidr)
        self.data[str(network.netmask())] = True
        self.mask_set.add(network.mask)

    def __contains__(self, ip):

        for i in self.mask_set:
            netmask = str(ipcalc.Network(f'{ip}/{i}').netmask())
            if netmask in self.data:
                return True
        return False

这样优化后速度和第二种持平，不过实际应用中还需要根据 ip 列表的情况来判断需要用哪种。

_