Разбор решения занявшего второе (пока что) место в конкурсе Hola по программированию почтовых фильтров на JavaScript

[zBit]

Интересный подход.
В моём бенчмарке с исходными данными от организаторов вы заняли 4-ое место (https://github.com/zbitname/hola_nodejs_challenge). Но при запуске от раза к разу, как выяснилось позже, места немного смещались. Я помню, что ваше решение в некоторых «раундах» на моих тестах было на 2-ом и 3-ом месте, но бывало и ниже.
Тем не менее, получилось очень достойное по производительности решение, несмотря на нестабильность времени выполнения решений ваше держится в первой 10-ке стабильно, чаще даже в первой 5-ке. Хорошо, что вы решили написать об этом статью, т.к. пытаться понять суть того как работает алгоритм по коду у подавляющего большинства участников очень сложно, надо потратить много времени.

организовывать соревнования в разных 'весовых категориях'.

Вы тут имеете ввиду разный объём входных данных?

[tymofey]

Вы тут имеете ввиду разный объём входных данных?

Именно. И неплохо было бы заранее их (объёмы) объявлять, вместе с остальными правилами конкурса.

[zBit]

Согласен, иначе игра в рулетку получается. И не пришлось бы подгонять тестовые данные под объём на котором у всех скрипт отработает и не свалится. И недовольных было бы меньше. А ещё лучше автоматизировать тестирование и выводить результаты онлайн, чтобы появилось больше мотивации соревноваться, как это было сделано с конкурсом по big data от mailru. Сделал скрипт — загрузил его на их сервак, узнал проходит ли тест на корректность твоё решение, сравнил свой результат с другими участниками. Это будет предварительная оценка. А в конце конкурса перед объявлением победителей сделать тоже самое, только ещё раз и с бОльшим количеством итераций и раундов, чтобы результаты были по-объективнее.

В общем, для организаторов теперь есть куча идей по тому как сделать в следующий раз всё удобнее.

[OLS]

В ходе прочтения обсуждений тестовых наборов мне пришла в голову следующая формула выбора тестов:
каждый участник, направивший свое решение, имеет право направить 1 или 2 теста. Тесты анонимизируются и размещаются в общем хранилище. Затем каждый участник имеет право проголосовать против, скажем, 50% тестов или против например 10. После голосования 25% тестов, набравшие самое большое количество голосов «против», удаляются из пула, а всем остальным присваиваются равные веса. С количественными параметрам схемы конечно можно «поиграть». Например, для ускорения тестирования наоборот оставить только 10% тестов, набравших меньше всего голосов «против».

[Methos]

Вам работу то предложили или нет?

[tymofey]

Нет)

[Methos]

Это намекает о том, что это голимый пиар Hola.

[xytop]

Я пробовал делать так:

1. оптимизировал все фильтры, убирал повторяющиеся * и?
2. затем делал граф/дерево как-то так:

var graph = {};
function addFilterToGraph(pattern, action) {
    var g = graph;
    for(var i = 0; i < pattern.length; i++) {
        if( !g[ pattern[i] ] ) {
            g[ pattern[i] ] = { action: [] };
        }
        g = g[ pattern[i] ];
    }
    g[ 'action' ].push( action );
}

Код неточный, пишу по памяти. Такое добавление проходило почти мгновенно.
В конечных точках паттернов оседали actions.

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

Теоретически это должно было сильно сократить количество проверок и ускорить алгоритм, так как мы не проверяем начальные символы паттернов снова а движемся в направлении листьев дерева/графа. Но сожалению это по какой-то причине работало в два раза медленнее решения с самописным match, который в итоге и послал на конкурс. На моих тестах этот match минимум в 3 раза по скорости опережал скомпилированный regex, я удивляюсь как здесь у некоторых ребят из конкурса регулярки оказываются быстрее моего решения…

[tymofey]

1) Убирать повторяющиеся '?' не корректно.
2,3) Если я правильно понимаю, ваш is_match при встрече '*' начинает перебирать все комбинации суффиксов строки и паттерна и сопоставлять их, в структуру дерева же эта звёздочка не кодируется. У меня же звездочки закодированы в структуру дерева в виде реккурентных связей (так что это уже не дерево, а граф в общем виде) NFA. После детерминизации время прохода по DFA пропорционально длине строки и не зависит от наличия звездочек.

[xytop]

1) — да, с дуру так написал, не убирал их конечно.
А по поводу is_match, да, много рекурсивных вызовов на один паттерн, зависит от его сложности. Мне кажется, это вариант NFA.
Интересно увидеть графическую развертку DFA для для паттерна со звездочкой/ами. Там тоже должны быть циклы/рекурсии где-то внутри по идее.