Python-сообщество

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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)

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

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