如何及时搜索大型IP地址数据库？
我有一个CSV文件是这样读的：
with open(r"file.csv", 'rb') as f:
reader = csv.reader(f)
c = list(reader)这个操作产生了大约22000个其他列表的一个列表。格式如下：
[['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)在IP对象的主列表中转换列表的第一个元素。
- 如果我的字符串位于CSV网络中，则打印整个列表(CSV_inside_list)。
- 做这个数量的IP来比较*数据库的大小，目前22K =巨大的时间消耗。
我对你的要求是:我怎样才能加快速度？我不能简单地执行"if my_ip in csv_database"，因为我需要它们成为IPNetwork对象，因此，如果遇到10.0.0.0/24，则例如10.0.0.1匹配，因为该IP位于网络范围内。
回答 1
Stack Overflow用户
发布于 2015-04-28 16:26:40
目前，在检查it之前，您正在将所有网络加载到内存中，但您并不需要这样做，您只需遍历您的阅读器，而不是将其转换为列表。
相反，我将加载所有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使用二进制搜索搜索给定值的排序列表，并返回索引，在该索引中必须插入值以维护列表的排序。bisect_left和bisect_right之间的区别是，该值已经在列表中(一次或多次)，bisect_left将返回第一次匹配的索引，bisect_right将返回最后+ 1的索引。
所以在这种情况下：
first_idx = bisect_left(sorted_ips, first)将从大于或等于IPAddress的sorted_ips返回第一个first的索引，并且
last_idx = bisect_right(sorted_ips, last, first_idx)返回上一次IPAddress小于或等于last之后的索引。我们知道first <= last，所以fist_idx必须是<= last_idx，所以第二次搜索的下界可以限制在first_idx。
这意味着片sorted_ips[first_idx:last_idx]包含来自列表的带有first <= ip <= last的所有IP。如果列表中没有地址相等或介于first和last之间，则这两个索引将是相同的，返回一个空列表。
由于二进制搜索的性能最差的是O(log(n))，这将大大加快查找列表中哪些if位于网络中，然后检查所有if的所有网络，特别是如果要检查的if列表非常大。
https://stackoverflow.com/questions/29922824
复制相似问题
腾讯云开发者
