如何及時搜索大型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列表非常大。