Что-ж это было-то
2010-10-21 12:45![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ufmНу ответ на это очень простой – это древовидное представление 192.168.2.1. То, что это дерево, угадал Тоботрас – на то он и великий. А уж то, что кому-то не лень будет ветки считать я и не расчитываю. :)
Я тут просто классический велосипед реализовываю – попадание адреса в список масок (да-да, стандартная задача: локальное/мир/всё остальное).
Originally published at U.F.M's Homepage. You can comment here or there.
(no subject)
Date: 2010-10-21 11:32 (UTC)То, что это дерево, было очевидно всем, кмк. Кстати, что-то мне подсказывает (лень разбираться подробнее), что ты не учел, что маски не бывают дырявыми. Они всегда /хх.
(no subject)
Date: 2010-10-21 11:36 (UTC)(no subject)
Date: 2010-10-21 11:42 (UTC)(no subject)
Date: 2010-10-21 11:54 (UTC)0.0.0.0/32
[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[nil,nil],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]],[]]
(no subject)
Date: 2010-10-21 12:28 (UTC)Просто с функциональным программированием поиграть?
(no subject)
Date: 2010-10-21 12:40 (UTC)2. Юра, я пишу на ерланге.
(no subject)
Date: 2010-10-21 13:33 (UTC)2. Ужас. %)
(no subject)
Date: 2010-10-21 13:34 (UTC)(no subject)
Date: 2010-10-21 14:21 (UTC)(no subject)
Date: 2010-10-21 15:03 (UTC)Я храню всю таблицу масок в виде дерева и одним процессом получаю попадает ли адрес в этот список масок или нет. И вычисление попадает адрес или нет происходит максимум за 23 выборки из дерева. Для любого числа масок в списке.
Еще раз - у меня нет не то что бы логарифмической зависимости времени проверки от размера таблицы масок, у меня нет даже линейной.
(no subject)
Date: 2010-10-21 16:05 (UTC)1. Процессы запускает эрланг, не ты вручную, конечно. http://ru.wikipedia.org/wiki/Erlang#.D0.A0.D0.B0.D0.B1.D0.BE.D1.82.D0.B0_.D1.81_.D0.BF.D1.80.D0.BE.D1.86.D0.B5.D1.81.D1.81.D0.B0.D0.BC.D0.B8
2. Чудес не бывает, если тебе надо работать с 50000 роутов, то построить дерево стоит не менее N*log(N), а поиск по нему - log(N). И от инструмента это никак не зависит (функциональный и процедурный языки функционально эквивалентны).
3. Логарифмическая зависимость намного лучше линейной, двоичный логарифм тысячи - около 10, а не тысяча.
(no subject)
Date: 2010-10-21 16:15 (UTC)1. Ты мне присылаешь сылку на википедию на язык, на котором я пишу уже достаточно давно, т.е. как-бы всё таки знаю что там и как.
2. Время построения дерева меня не интересует, оно обновляется раз в час.
3. Да пох.
Юр, тебе какой раз сказать, что сравнение адреса с маской у меня занимает максимум 23 выборки из дерева вне зависимости размера этого дерева? Ну, т.е., ты можешь меня попытатся поубеждать, но я боюсь у тебя херово получится - у меня как-бы исходники перед глазами.
(no subject)
Date: 2010-10-21 16:33 (UTC)(no subject)
Date: 2010-10-21 16:47 (UTC)Юр, о чем мы спорим?
(no subject)
Date: 2010-10-21 16:51 (UTC)Я просто прикалываюсь, зачем выбирать такой экзотический инструмент для такой задачи. :) Если б ты ESB на кластере городил - другое дело.
(no subject)
Date: 2010-10-21 16:54 (UTC)(no subject)
Date: 2010-10-21 16:37 (UTC)1. Эту фишку ты не заценил, похоже. Эрланг приколен именно тем, что он делает параллелизм без мутексов и семафоров, причем без помощи операционки.
2. Как знаешь, от этого трудоемкость не меняется.
3. Не, логарифм лучше. :-P
(no subject)
Date: 2010-10-21 16:53 (UTC)2. Трудоёмкость построения дерева, кстати, - теже самые максимальные 24 выборки на маску. Но еще раз - дерево масок строится раз в час. Очень быстро строится. Очень. Ну т.е. получение из интенета файла со списком масок занимает на не один десятичный порядок больше времени.
3. Нет. Потому что мой вариант имеет фиксированное и предсказуемое время работы, не зависящее от размеров дерева (т.е. не зависяще еот количества масок).
(no subject)
Date: 2010-10-21 17:32 (UTC)2. OMG. N*Log(N) или N*24, как больше нравится. N - количество роутов.
3. При построенном дереве цикл на 24 итерации на С не напишешь? Не верю. А дерево строится обычной сортировкой.
(no subject)
Date: 2010-10-21 17:44 (UTC)(no subject)
Date: 2010-10-21 17:55 (UTC)http://rsdn.ru/article/erlang/GettingStartedWithErlang.xml
(no subject)
Date: 2010-10-21 18:02 (UTC)