如何及时搜索大型IP地址数据库？

Question

我正在读这样一个CSV文件：

with open(r"file.csv", 'rb') as f: 
    reader = csv.reader(f) 
    c = list(reader) 

此操作产生约22000其他列表1个清单。其格式为：

[['10.0.0.0/24', 'random bla', 'vlan=22'], ['20.0.0.0/20', 'random bla 2', vlan=354] ...x22000] 

这是仅包含网络，VLAN，描述等我做了一个脚本来检查在数据库中的任意的输入的存在的IP数据库。对于需要在数据库中检查的每个网络，我需要执行以下操作：

• 在IPNetwork对象（我正在使用netaddr模块）中转换我的字符串。
• 对于CSV转储中的每个列表，使用IPNetwork（CSV_inside_list [0]）将列表中的第一个元素转换为IP对象的主列表。
• 如果我的字符串在CSV网络中，则打印整个列表（CSV_inside_list）。
• 做这[[比较的IP数量] * [数据库的大小，目前22K] =巨大的时间消耗。

我的要求是：我怎么能加快速度？我不能简单地做“如果my_ip在csv_database中”，因为我需要它们是IPNetwork对象，所以例如10.0.0.1匹配10.0.0.0/24时会匹配，因为该IP在网络范围内。

Answer 1

目前，您在检查IP之前将所有网络加载到内存中，但您并不需要这样做，只需遍历读取器而不是将其转换为列表即可。

相反，我会加载所有的IP地址来检查列表并对它们进行排序。然后，可以使用bisect从对象时间内的单个网络中的列表中获取所有IP，因此，您将拥有O(m*log(n))而不是O(m*n)，并加上排序地址列表的成本。

应类似于此*：

from bisect import bisect_left, bisect_right 

def find_ips_in_network(network, sorted_ips): 
    first = netaddr.IPAddress(network.first) 
    last = netaddr.IPAddress(network.last) 
    first_idx = bisect_left(sorted_ips, first) 
    last_idx = bisect_right(sorted_ips, last) 
    return sorted_ips[first_idx:last_idx] 

sorted_ips = sorted(...) # load ips as sorted list of netaddr.IPAddress 
found_networks = dict() 
# or collections.defaultdict(list) if you want all networks 

with open(r"file.csv", 'rb') as f: 
    reader = csv.reader(f) 
    for row in reader: 
     network = netaddr.IPNetwork(row[0]) 
     for ip in find_ips_in_network(network, sorted_ips): 
      found_networks[ip] = row 
      # or found_networks[ip].append(row) if using defaultdict 

for ip in sorted_ips: 
    if ip in found_networks: 
     print ip, "found in:", found_networks[ip] 

*免责声明：正确性不能保证

编辑：小优化：由于第一地址的指数的平均值，它可以用来限制为最后一个索引搜索时下界：

last_idx = bisect_right(sorted_ips, last, first_index) 

说明：bisect_left和bisect_right使用binary search在已排序列表中搜索给定值，并返回必须插入值的索引以维护列表的排序。 bisect_left和bisect_right之间的差值是其中值已经在列表中的情况（一次或多次），bisect_left将返回第一次匹配的索引，bisect_right最后一次+1的索引。
因此，在这种情况下：

first_idx = bisect_left(sorted_ips, first) 

将从sorted_ips比first大于或等于返回第一个ip地址的索引，

last_idx = bisect_right(sorted_ips, last, first_idx) 

最后一个ip地址后返回索引一个小或等于last。 我们知道first <= last，因此fist_idx必须是<= last_idx，因此第二个搜索的下限可以限制在first_idx。

这意味着片段sorted_ips[first_idx:last_idx]包含列表中的所有IP，first <= ip <= last。如果列表中没有地址相等，或者first和last之间的地址相同，则两个索引将相同，返回空列表。

由于二进制搜索的最差情况下性能为O(log(n))，因此查找列表中的哪些IP位于网络中，然后检查所有IP的所有网络，特别是如果要检查的IP列表非常大。