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

(Ответить) (Thread)

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

(Ответить) (Thread)

А какие ограничения? Тупо сделать 512Мб массив битовых флагов, заполнить битом 1 диапазоны, и быстрее уже ничего не может быть. Разве что за счёт локальности памяти и кэша процессора -- на каком мерять собираются?

(Ответить) (Thread)

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

(Ответить) (Parent) (Thread) (Развернуть)

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

(Ответить) (Thread)

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

(Ответить) (Parent) (Thread) (Развернуть)

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

(Ответить) (Thread)

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

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

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

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

(Ответить) (Parent) (Thread) (Развернуть)

У нас нечто подобное забыдлокоджено "в лоб".
Масив пар лонгов "старт, енд".
А потом приводим искомый адрес тоже в лонг, и тупым перебором и сравнением по этому масиву. Для пар сотен запесей работает заебца, как по мне.

(Ответить) (Thread)

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

Один из текущих IP-фильтров разросся до 128к индивидуальных айпишников, с этим тоже такое может произойти, т.е. стараемся писать масштабируемо, если это не требует значительных работ. Случай с линейным vs бинарным поиском - как раз то.

(Ответить) (Parent) (Thread)

Обычно для range lookup используются multiway range trees и segment trees. Для пересекающихся диапазонов можно сначала сделать "нормализацию".

(Ответить) (Thread)

у нас не "обычно":

1) нет обновлений
2) нет префиксов
3) нет задачи искать самый длинный префикс

В топку.

(Ответить) (Parent) (Thread)

Я не понял, как потом сравнивать будем.

(Ответить) (Thread)

Псевдокод:

sub find(ip_str)
{
   ip_uint32 = ip2int(ip_str)
   forall (entry in config)
   {
      if ip_uint32 >= entry.start && ip.uint32 <= entry.end
         return true
   }
   return false
}

Идея должна быть понятна. Алгоритм, разумеется, должен быть быстрее линейного.

(Ответить) (Parent) (Thread) (Развернуть)

Навскидку, то что за полчаса написалось на эрланге.

http://ubuntuone.com/4jM6BSoxbUrRhipSCBGLni

А что мерить то?

(Ответить) (Thread)

Вариант номер 2 - дерево (первый вариант был через hashtable).
http://ubuntuone.com/4pHqBhfOJvUnoraop5uJYx (http://ubuntuone.com/4pHqBhfOJvUnoraop5uJYx)

Работает так:

F = iptree:read("RU_ipranges.txt").

Естественно со своим именем файла. Результат - функция для проверки.
Типа

3> F = iptree:read("RU_ipranges.txt").

4> F("192.168.1.1").
not_found
5> F("46.28.130.1").
found

(Ответить) (Thread)

Надо срочно писать ответ на node.js :)

(Ответить) (Parent) (Thread)

User grundik referenced to your post from No title saying: [...] http://nponeccop.livejournal.com/225261.html [...]

(Ответить) (Thread)

Не указана важная деталь — реакция программы на ошибки.

(Ответить) (Thread)

Это специально сделано. Всё неспецифицированное можно делать как угодно.

(Ответить) (Parent) (Thread)

User thesz referenced to your post from Попробовал задачку nponeccop. saying: [...] Задачка [...]

(Ответить) (Thread)

User justy_tylor referenced to your post from Пятничное трололо saying: [...] Пример кода для http://nponeccop.livejournal.com/225261.html [...]

(Ответить) (Thread)

CL: http://love5an.livejournal.com/369688.html

(Ответить) (Thread)

User inv2004 referenced to your post from RWA Contest saying: [...] насочинял для этой [...]

(Ответить) (Thread)

Выше thesz уже спрашивал - важно ли находить сам диапазон, в который попал IP? Иначе можно обойтись 3-мя изначально нулевыми матрицами a,b,c размера 256x256. Если есть адрес 100.101.102.103, то a[100,101]=1, b[101,102]=1, c[102,103]=1. И так для каждого IP из диапазонов в процессе прочтения файла (долго, что делать, но зато искать проще). Поиск как строить имхо очевидно и должно получиться достаточно быстро. Матрицы можно размотать в массивы стандартным образом, конечно.

//EO

(Ответить) (Thread)

Сам диапазон находить не нужно

(Ответить) (Parent) (Thread)

А у количества данных какие порядки?
Сколько диапазонов?
Сколько IP- адресов?

(Ответить) (Thread)

IP-адресов - от тысяч до миллиарда. Причём из-за дурацкой архитектуры распараллеливания нельзя проверять адреса пачками (т.е. передавать в проверялку можно только по одному).

Диапазонов - единицы тысяч.

(Ответить) (Parent) (Thread) (Развернуть)

User gliv referenced to your post from решение задачи про фильтрацию IP-адресов на хаскеле saying: [...] Разобрался с задачей [...]

(Ответить) (Thread)

Ищу всё за чуть больше секунды:

http://inv2004.livejournal.com/144272.html

Всё: 10^6 ip адресов на 7000 диапазонов.

(Ответить) (Thread)

Чуть больше полусекунды.

Исходник тут: http://dl.dropbox.com/u/34917039/ip.k

m:0N,{1+|/x#iph}'1+!#ipl
f:{x<m@ipl _bin x}

(Ответить) (Parent) (Thread) (Развернуть)