DjangoBB LoFi version

Начало » Python для экспертов » сравнение ip адресов

dem

Июль 3, 2007 16:50:10

Нужно работать с большими списками ip адрессов UA-AIX ~ 1900 диапазонов.

выборка в стиле:

“ есть ip в списке этих диапазонов - или нет? ”

плюс есть требование по производительности решения.

Пока смотрю на IPy, но вдруг комрады подскажут чего? По сути задача сводится к поиску в бинарном массиве.

Андрей Светлов

Июль 3, 2007 17:07:27

А какие рамки по производительности?
Мерял? Не хватало?
По моему 2000 диапазонов отстрелятся почти мгновенно - не миллион же.
IPy - вполне приличная вещь. Есть еще iplib. Дело вкуса

dem

Июль 3, 2007 18:14:57

IPy не умеет сравнивать диапазоны.
а в таком виде и так 2000 диапазонов… вообще не весело и не пролетает!

при пересчете статистики с NetFlow, вы представляете сколько таких сравнений может быть в цикле? Но в корне будет именно эта операция, а значит ее нужно максимально оптимизировать.

Я вот думаю перегонять весь список диапазонов в сортированный спискок бинарных ip.
И за тем с ним сравнивать опять таки бинарный ип…. Но стоит ли овчинка?

Андрей Светлов

Июль 3, 2007 18:49:33

Если серьезно повышать скорость - следует делать дерево. Только лучше не совсем бинарное. Обычно в диапазонах первые три байта - целые (в смысле маска 255.255.255.ххх). Начало можно находить быстро (в три приема будет оптимальней, чем большой сортированный список), а хвост уже побитно смотреть. Легко перейти к более общему виду - учесть маски 255.255.ххх.ххх, 255.ххх.ххх.ххх и т.д.
Простой bisort по большому списку будет, думаю, медленней.
Еще можно это все на плюсах сделать - поиск имеет все шансы ускориться.

Честно говоря, не помню, как устроены IPy и iplib - может, что-то такое в них и есть.
Я такую реализацию видел где-то на плюсах. Где - уже не вспомню.

dem

Июль 3, 2007 18:59:10

Андрей Светлов
Если серьезно повышать скорость - следует делать дерево. Только лучше не совсем бинарное. Обычно в диапазонах первые три байта - целые (в смысле маска 255.255.255.ххх). Начало можно находить быстро (в три приема будет оптимальней, чем большой сортированный список), а хвост уже побитно смотреть. Легко перейти к более общему виду - учесть маски 255.255.ххх.ххх, 255.ххх.ххх.ххх и т.д.
Простой bisort по большому списку будет, думаю, медленней.
Еще можно это все на плюсах сделать - поиск имеет все шансы ускориться.

Честно говоря, не помню, как устроены IPy и iplib - может, что-то такое в них и есть.
Я такую реализацию видел где-то на плюсах. Где - уже не вспомню.

Наверное прийдется вспоминать С. Либо юзать inet_type in PostgreSQL. Кстати там эта функция отлично реализована.
т/е выражения вида 10.0.0.0/24 >> 10.0.0.54 выдает True, но с переносимостью сами понимаете…

Андрей Светлов

Июль 3, 2007 19:18:22

И все таки советую собрать быстро прототип на какой-нибудь готовой либе.
Начальству показать и т.д.
А потом можно будет долго и весело поиск ускорять.

shiza

Июль 3, 2007 22:06:47

Я так поступал:
Преобразование IP из строки в целое:

IpInt = struct.unpack('!L',socket.inet_aton(IpStr))[0]

Преобразование IP из целого в строку:

IpStr = socket.inet_ntoa(struct.pack('!L', IpInt)

Оба используемых модуля стандратные, и сишные. Поетому преобразование - довольно быстрое ( на моей машине 10000 преобразований - за 0.01 сек).

Преобразование - взаимооднозначное. Скорость сравнение интов - думаю рулит, по сравнению со всеми прочими.
Инты пожно сравнивать напрямую и на больше, меньше:

print struct.unpack('!L',socket.inet_aton('0.0.0.0'))[0]
print struct.unpack('!L',socket.inet_aton('192.168.0.0'))[0]
print struct.unpack('!L',socket.inet_aton('192.168.0.1'))[0]
print struct.unpack('!L',socket.inet_aton('255.255.255.255'))[0]
--------------------------------------------------
0
3232235520
3232235521
4294967295

shiza

Июль 3, 2007 22:10:37

Упс. Сори. Только сейчас братил внимание на то что нужно с диапазонами.

shiza

Окт. 22, 2008 04:20:34

http://code.google.com/p/ipaddr-py/