Comments | nponeccop: RWA Contest

nponeccop

RWA Contest

Oct 26, 2011 15:47

Тут по моему старому проекту возникла задачка: сделать фильтрацию по диапазонам IP-адресов. Буду делать quick and dirty-реализацию на си с классами, если кто возжелает, может реализовать на своём любимом языке а потом сравнимЗадача такова: есть ASCIIZ-строка с IP-адресом, надо вернуть true, если этот адрес попадает в один из диапазонов, ( Read more... )

fp, programming

Comments 86

deni_ok October 26 2011, 12:58:10 UTC

Хорошая, студентам подкину.

anonymous October 26 2011, 13:02:48 UTC

Эх, реализовано такое уже в libgeoip, простой битовый trie.

(The comment has been removed)

nponeccop October 26 2011, 16:04:51 UTC

Не, 512 мбайт у нас нету. 1 ядро Xeon Core2, детальнее пока не скажу.

w00dy October 28 2011, 09:12:26 UTC

А сколько есть? Как вариант нарезать в корзинки по /8. Итого 256 корзинок, в каждой хранить startIp, endIp (для быстрого отсечения) и массив флагов up to 2MB size. Можно ещё раздробить, но тут информации о диапазонах бы побольше.

nponeccop October 28 2011, 14:28:17 UTC

50 мб есть

Thread 10

antilamer October 26 2011, 13:54:25 UTC

Binary search по списку границ, после устранения дублей и пересечений любым способом, думаю, будет быстрее всего, раз сотни.

smalgin October 26 2011, 14:31:45 UTC

ну или hashtables тоже можно.

antilamer October 26 2011, 14:35:43 UTC

Как?

smalgin October 26 2011, 14:43:13 UTC

Это я не выспался. Не Hashtables, конечно. Построить дерево поиска... ну в-общем, круг сделал и пришел туда же, куда и вы. Фигли париться с деревом, если бинарный поиск есть.

Эхм.

Thread 15

ximaera October 26 2011, 15:23:57 UTC

Т. е. IP-адреса указываются не целыми префиксами, а такими вот диапазонами? Если не секрет, в чём смысл такой задачи?

nponeccop October 26 2011, 15:50:34 UTC

смысла много разного.

1) для вычисления CIDR нужна отдельная тулза, а минимальный и максимальный IP можно определить по набору IP в логе визуально

2) пользователи не знают, что такое CIDR

3) фильтрация по CIDR не имеет физического смысла

ximaera October 26 2011, 15:55:26 UTC

1) Ну так эту тулзу проще написать, чем ту тулзу, которую предлагается писать :-)

2) Пользователи чего?

3) А фильтрация по диапазонам адресов какой физический смысл имеет?

nponeccop October 26 2011, 16:11:38 UTC

1) надо либо написать CIDR-фильтр + UI, либо диапазонный фильтр. Не уверен, что битовый trie проще сортированного массива, но даже если проще - то всё равно UI надо деплоить и документировать. Сейчас всё сделано the unix way - ноутпад и вперёд.

2) пользователи системы, частью которой этот фильтр является

3) фильтрация по диапазонам имеет физический смысл в случае если хостер выделил некоему субъекту 17 адресов, идущих подряд, без организации в отдельную подсеть

Thread 19