Матчасть по маршрутизации

Цитируем shimon

согласно набору правил, формирующемуся динамически

можно подробнее?

Ещё можно(?, нужна доп. информация на счёт ящика) кэшировать ответы от функций f(s,d).

> согласно набору правил, формирующемуся динамически

Это означает, что правила можно добавлять и удалять прямо в рантайме, вручную либо алгоритмически. Например, если Вася Пупкин уже сотый раз за день пишет Жириновскому о том, как тот его заколебал, вставляется правило отправлять письма от Васи Пупкина к Жириновскому через почтовый индекс 666, где письма жгут не глядя, прямо в мешках.

И для этого конвейер не надо даже ставить на паузу.

>>набору правил, формирующемуся динамически, где каждое правило — это функция f(s, d) от адресов отправителя и получателя, возвращающая нужный индекс

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

> Ещё можно(?, нужна доп. информация на счёт ящика) кэшировать ответы от функций f(s,d).

Можно кешировать, но тогда расчет эффективности порядка правил должен еще и учитывать кеш-попадания и кеш-промахи. Становится немножко нетривиально.

Что ли почитать ядро линакса на предмет того, как роутятся пакеты.

> Точнее сказать, что набор, это множество подфункций исходной функции, полученных сужением исходной функции на неперекрывающиеся подмножества области определения.

Можно и так сказать. Факт тот, что количественно-качественный состав этих неперекрывающихся множеств может изменяться в зависимости от многих факторов, самый весомый — желание левой пятки владельца конвейера.

Хотя тут неперекрываемость несущественна, наоборот, хорошо если будет дублироваться.

Считается, что порядок правил не имеет значения.

Странно, должен иметь. В нем и состоит залог улучшения. Правила ведь обрабатываются последовательно. Можно накопить статистику и посмотреть распределение номера шага, на котором происходит окончательное принятие решения. Если этот номер распределен по геометрическому распределению (схема Бернулли), то что-то улучшить вряд ли получится. Если наблюдается отклонение от геометрического распределения, то имеет смысл переставить порядок обработки правил.

Но это верно для некого устаканившегося неизменного набора правил и для допущения одинаковой вероятности письма попасть под то или иное правило.

Если же подключается пятка, то тут ухватиться за что бы то ни было непросто.

> Странно, должен иметь.

В этом смысле — да. Я имел в виду то, что в каком порядке правила не применишь, одной паре (s, d) должен всегда соответствовать один индекс.

> Если же подключается пятка, то тут ухватиться за что бы то ни было непросто.

Именно поэтому — эмпирический способ: каждые N писем выталкиваем самые частоиспользуемые функции вверх.

Что ли почитать ядро линакса на предмет того, как роутятся пакеты.

В ядре такой задачи не стоит, там либо ~fifo, либо как указано в статических правилах.

ИМХО, самое простое, переставлять сработавшее правило в начало списка, каждый раз. Потому что, если у вас упорядочивания списка будет достаточно часто, а правил будет много, то сработавших правил будет не много, а сортировать весь список.

Относительно кеширования, непонятно, как часто у вас повторяется пара (s,d), в случае маршрутизации, там вполне ожидаемо, что если прошёл один пакет от a к b, то скоро последуют и другие.

> ИМХО, самое простое, переставлять сработавшее правило в начало списка, каждый раз.

Если переставлять одно правило по накладным расходам так же, как сотню правил, то лучше переставить сотню.

>Если переставлять одно правило по накладным расходам так же, как сотню правил

Мда, подробности из вас нужно тащить клещами :)

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

Вобще, вы бы определились, как часто могут быть повторы (s, d), что более затратно --- проверка правила или его перестановка и насколько.

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

Так как это будет Python, то там структура чуть-чуть сложнее даже двусвязного списка, хотя точных подробностей я не знаю. В любом случае, делать иной тип списка — только когда все заработает и когда профайлер скажет, что все тормоза именно в перестановках.

Профайлер, ИМХО, нужно смотреть на обработке данных, близких к реальным. И опять мы возвращаемся к вопросу, о вероятности того, что нескольно подряд идущих писем подходящих под одно правило.

Наверное, можно ещё для каждого письма определять на каком правиле по счёту оно срабтало и определять среднее для последних 10 и 100 писем. И уже на этом основании сортировать список.