Как быстро найти большую базу данных IP-адресов?

Question

У меня есть файл CSV читается так:

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

Эта операция производится 1 список около 22000 другого списка. Формат:

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

Это база данных, содержащая только IP-сети, VLAN, описание и т.д. Я сделал скрипт, чтобы проверить наличие произвольного ввода в базу данных. Для каждой сети, которую мне нужно проверить в базе данных, мне нужно сделать следующее:

• Преобразование моей строки в объект IPNetwork (я использую модуль netaddr).
• Для каждого списка в дампе CSV преобразуйте первый элемент списка внутри основного списка в IP-объект с помощью IPNetwork (CSV_inside_list [0]).
• Если моя строка находится в сети CSV, распечатайте весь список (CSV_inside_list).
• Сделайте это [количество IP-адресов для сравнения] * [размер базы данных, в настоящее время 22K] = потребление ОГРОМНОГО ВРЕМЕНИ.

Моя просьба: как я могу ускорить это? Я не могу просто «if my_ip в csv_database», потому что мне нужно, чтобы они были объектами IPNetwork, поэтому, например, 10.0.0.1 совпадают, если столкнулись с 10.0.0.0/24, потому что этот IP-адрес находится в сетевом диапазоне.

Answer 1

В настоящее время вы загружаете все сети в память, прежде чем проверять IP-адреса, но вам действительно не нужно это делать, вы можете просто перебирать ваш читатель вместо того, чтобы преобразовывать его в список.

Вместо этого я бы загрузил все IP-адреса, чтобы их проверить в списке и отсортировать. Затем можно использовать bisect, чтобы получить все IP-адреса из списка, которые находятся в одной сети в логарифмическом времени, поэтому вместо O(m*n) у вас будет O(m*log(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] 

* Отказ от ответственности: нет никакой гарантии правильности

Edit: небольшая оптимизация: так как индекс первого адреса вычисляется первым, он может быть использован для ограничить нижний предел при поиске последнего индекса:

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) 

возвращает индекс первого 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] содержит все IP-адреса из списка: first <= ip <= last. Если ни один из адресов в списке не равен или между first и last, оба индекса будут одинаковыми, возвращая пустой список.

Поскольку бинарный поиск имеет наихудший показатель производительности O(log(n)), это будет значительно быстрее, чтобы найти, какие IP-адреса из списка находятся в сети, а затем проверить все сети для всех IP-адресов, особенно если список IP-адресов для проверки очень большой ,