判断ip是否在一个超大ip集中（识别国内ip） |五十风的个人博客

新需求需要通过ip展示不同语言，由于ip很多，因此字典并不适用，下面给出几个方法。

1. 通过ip位置数据库

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

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

2. 利用ip的连续性

后面两个方法有个前提：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 __contains__(self, ip):
        for i in range(1,33):
            netmask=str(ipcalc.Network(f'{ip}/{i}').netmask())
            if netmask in self.data:
                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:
            netmask=str(ipcalc.Network(f'{ip}/{i}').netmask())
            if netmask in self.data:
                return True
        return False

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

2. 排除不会出现的n

class ChinaIp(object):
    def __init__(self):
        ...
        self.mask_set = set()
    ...

    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列表的情况来判断需要用哪种。