Как эффективно проверить, принадлежит ли данный IP-адрес IP-подсети в Python?

У меня есть набор из примерно 200 000 IP-адресов и 10 000 подсетей вида (1.1.1.1/24). Для каждого IP-адреса мне нужно проверить, принадлежит ли он одной из этих подсетей, но, поскольку это такой большой набор данных, и у меня меньше вычислительных мощностей, мне нужна эффективная реализация для этого.

При поиске я нашел один метод (https://stackoverflow.com/a/820124/7995937):

from netaddr import IPNetwork, IPAddress
if IPAddress("192.168.0.1") in IPNetwork("192.168.0.0/24"):
     print "Yay!"

Но поскольку мне приходится перебирать 200 000 IP-адресов в цикле, а для каждого цикла адресов более 10 000 подсетей, я не уверен, что это эффективно. Мое первое сомнение: проверка «IPAddress () в IPNetwork ()» - это просто линейное сканирование или это каким-то образом оптимизировано?

Другое решение, которое я придумал, заключалось в том, чтобы составить список со всеми IP-адресами, содержащимися в IP-подсетях (что составляет около 13000000 IP-адресов без дубликатов), а затем отсортировать его. Если я это сделаю, то в моем цикле из 200 000 IP-адресов мне нужно будет только выполнить двоичный поиск для каждого IP-адреса по большему набору IP-адресов.

for ipMasked in ipsubnets:  # Here ipsubnets is the list of all subnets
        setUnmaskedIPs = [str(ip) for ip in IPNetwork(ipMasked)]
        ip_list = ip_list + setUnmaskedIPs
ip_list = list(set(ip_list))  # To eliminate duplicates
ip_list.sort()

Затем я мог бы просто выполнить двоичный поиск следующим образом:

for ip in myIPList:  # myIPList is the list of 200,000 IPs
    if bin_search(ip,ip_list):
        print('The ip is present')

Этот метод более эффективен, чем другой? Или есть другой более эффективный способ выполнить эту задачу?


python performance ip cidr
person Arjun Balgovind    schedule 30.05.2017    source источник
comment
Как уже говорилось, быстрее всего использовать наборы. Другая тема по этому поводу: stackoverflow.com/questions/5993621/   -  person Łukasz Szczesiak    schedule 30.05.2017
comment
Превратить строку IPv4 в 32-битное int тривиально, поэтому, если бы мне пришлось создать такую ​​библиотеку, я бы, вероятно, использовал внутри себя целые числа и бинарные операторы, что было бы довольно эффективно. Как всегда, вы должны сначала измерить, есть ли действительно проблема с производительностью.   -  person polku    schedule 30.05.2017

Ответы (3)


arrow_upward
0
arrow_downward

Итак, сортировка занимает O (nlogn), в случае 13000000 вы в конечном итоге выполняете O (13000000log (13000000)). Затем вы перебираете 200000 IP и выполняете двоичный поиск O (logn) в этом отсортированном списке на 13000000. Я искренне сомневаюсь, что это лучшее решение. Я предлагаю вам использовать карту

from netaddr import IPNetwork, IPAddress
l_ip_address = map(IPAddress, list_of_ip_address)
l_ip_subnet = map(IPNetwork, list_of_subnets)

if any(x in y for x in l_ip_address for y in l_ip_subnet):
    print "FOUND"
person Ishan Bhatt    schedule 30.05.2017
comment
Можете ли вы уточнить, что именно делает карта? И как это улучшить сложность, если мы перебираем x in l_ip_address и y in l_ip_subnet? - person Arjun Balgovind; 31.05.2017
comment
map создает другой список типа IPAddress из списка строки IP-адресов. Таким образом, это избавляет вас от преобразования строки в IPAddress каждый раз в цикле. - person Ishan Bhatt; 31.05.2017

arrow_upward
0
arrow_downward

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

ip_list = list(set(ip_list))

просто сделать:

ip_set = set(ip_list)

а затем другая часть вашего кода станет:

for ip in myIPList:  # myIPList is the list of 200,000 IPs
    if ip in ip_set:
        print('The ip is present')

Изменить: и чтобы сделать вещи немного более эффективными с точки зрения памяти, вы также можете пропустить создание промежуточного списка:

ip_set = set()
for ipMasked in ipsubnets: 
    ip_set.update([str(ip) for ip in IPNetwork(ipMasked)])
person Błotosmętek    schedule 30.05.2017

arrow_upward
0
arrow_downward

Ваш IP-адрес в подсети, если N ведущих битов этого адреса совпадают с N ведущими битами одной из N-разрядных подсетей. Итак, начнем с составления списка пустых наборов. Кодируйте каждую подсеть как 32-битное целое число с замаскированными конечными битами. Например, 1.2.3.4/23 равно (0x01020304 & 0xfffffe00) равно 0x01020200. Добавьте этот номер к 23-му набору в списке, то есть subnets[23]. Продолжить для всех подсетей.

Чтобы узнать, находится ли IP-адрес в ваших подсетях, закодируйте IP-адрес так же, как 32-битное число ipaddr, а затем (что-то вроде непроверенного кода)

for N in range( 32, 0, -1)
    mask = ( 0xffffffff >> (32-N) ) << (32-N)
    if (ipaddr & mask) in subnets[N] :
        # have found ipaddr in one of our subnets
        break # or do whatever...
else
    # have not found  ipaddr

Поиск числа в наборе в худшем случае O (log N), где N - количество элементов в наборе. Этот код делает это не более 32 раз для худшего случая IP-адреса, которого нет в наборах подсетей. Если ожидается, что большинство адресов будет присутствовать, есть оптимизация, чтобы сначала протестировать наборы с наибольшим количеством элементов. Это может быть

for N in ( 24, 16, 8, 29, 23, 28, 27, 26, 25, 22, 15, 21 ... )

или вы можете вычислить оптимальную последовательность во время выполнения.

person nigel222    schedule 30.05.2017