Уведомления

Jabber-конференция сообщества: pythonua@conference.jabber.ru

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

dem
От:
Зарегистрирован: 2006-06-02
Сообщения: 44
Репутация: +  0  -
Профиль   Отправить e-mail  

сравнение ip адресов

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

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

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

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

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



Офлайн

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

Андрей Светлов
От:
Зарегистрирован: 2007-05-15
Сообщения: 3137
Репутация: +  14  -
Профиль   Адрес электронной почты  

сравнение ip адресов

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



Офлайн

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

dem
От:
Зарегистрирован: 2006-06-02
Сообщения: 44
Репутация: +  0  -
Профиль   Отправить e-mail  

сравнение ip адресов

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

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


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



Отредактировано (Июль 3, 2007 18:42:00)

Офлайн

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

Андрей Светлов
От:
Зарегистрирован: 2007-05-15
Сообщения: 3137
Репутация: +  14  -
Профиль   Адрес электронной почты  

сравнение ip адресов

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

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



Отредактировано (Июль 3, 2007 18:52:27)

Офлайн

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

dem
От:
Зарегистрирован: 2006-06-02
Сообщения: 44
Репутация: +  0  -
Профиль   Отправить e-mail  

сравнение ip адресов

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

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



Офлайн

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

Андрей Светлов
От:
Зарегистрирован: 2007-05-15
Сообщения: 3137
Репутация: +  14  -
Профиль   Адрес электронной почты  

сравнение ip адресов

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



Офлайн

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

shiza
От:
Зарегистрирован: 2007-07-03
Сообщения: 1073
Репутация: +  0  -
Профиль   Отправить e-mail  

сравнение ip адресов

Я так поступал:
Преобразование 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



Отредактировано (Июль 3, 2007 22:07:20)

Офлайн

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

shiza
От:
Зарегистрирован: 2007-07-03
Сообщения: 1073
Репутация: +  0  -
Профиль   Отправить e-mail  

сравнение ip адресов

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



Офлайн

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

shiza
От:
Зарегистрирован: 2007-07-03
Сообщения: 1073
Репутация: +  0  -
Профиль   Отправить e-mail  

сравнение ip адресов

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version