Comments 10
Интересный подход.
В моём бенчмарке с исходными данными от организаторов вы заняли 4-ое место (https://github.com/zbitname/hola_nodejs_challenge). Но при запуске от раза к разу, как выяснилось позже, места немного смещались. Я помню, что ваше решение в некоторых «раундах» на моих тестах было на 2-ом и 3-ом месте, но бывало и ниже.
Тем не менее, получилось очень достойное по производительности решение, несмотря на нестабильность времени выполнения решений ваше держится в первой 10-ке стабильно, чаще даже в первой 5-ке. Хорошо, что вы решили написать об этом статью, т.к. пытаться понять суть того как работает алгоритм по коду у подавляющего большинства участников очень сложно, надо потратить много времени.
В моём бенчмарке с исходными данными от организаторов вы заняли 4-ое место (https://github.com/zbitname/hola_nodejs_challenge). Но при запуске от раза к разу, как выяснилось позже, места немного смещались. Я помню, что ваше решение в некоторых «раундах» на моих тестах было на 2-ом и 3-ом месте, но бывало и ниже.
Тем не менее, получилось очень достойное по производительности решение, несмотря на нестабильность времени выполнения решений ваше держится в первой 10-ке стабильно, чаще даже в первой 5-ке. Хорошо, что вы решили написать об этом статью, т.к. пытаться понять суть того как работает алгоритм по коду у подавляющего большинства участников очень сложно, надо потратить много времени.
организовывать соревнования в разных 'весовых категориях'.Вы тут имеете ввиду разный объём входных данных?
+1
Вы тут имеете ввиду разный объём входных данных?
Именно. И неплохо было бы заранее их (объёмы) объявлять, вместе с остальными правилами конкурса.
0
Согласен, иначе игра в рулетку получается. И не пришлось бы подгонять тестовые данные под объём на котором у всех скрипт отработает и не свалится. И недовольных было бы меньше. А ещё лучше автоматизировать тестирование и выводить результаты онлайн, чтобы появилось больше мотивации соревноваться, как это было сделано с конкурсом по big data от mailru. Сделал скрипт — загрузил его на их сервак, узнал проходит ли тест на корректность твоё решение, сравнил свой результат с другими участниками. Это будет предварительная оценка. А в конце конкурса перед объявлением победителей сделать тоже самое, только ещё раз и с бОльшим количеством итераций и раундов, чтобы результаты были по-объективнее.
В общем, для организаторов теперь есть куча идей по тому как сделать в следующий раз всё удобнее.
В общем, для организаторов теперь есть куча идей по тому как сделать в следующий раз всё удобнее.
0
В ходе прочтения обсуждений тестовых наборов мне пришла в голову следующая формула выбора тестов:
каждый участник, направивший свое решение, имеет право направить 1 или 2 теста. Тесты анонимизируются и размещаются в общем хранилище. Затем каждый участник имеет право проголосовать против, скажем, 50% тестов или против например 10. После голосования 25% тестов, набравшие самое большое количество голосов «против», удаляются из пула, а всем остальным присваиваются равные веса. С количественными параметрам схемы конечно можно «поиграть». Например, для ускорения тестирования наоборот оставить только 10% тестов, набравших меньше всего голосов «против».
каждый участник, направивший свое решение, имеет право направить 1 или 2 теста. Тесты анонимизируются и размещаются в общем хранилище. Затем каждый участник имеет право проголосовать против, скажем, 50% тестов или против например 10. После голосования 25% тестов, набравшие самое большое количество голосов «против», удаляются из пула, а всем остальным присваиваются равные веса. С количественными параметрам схемы конечно можно «поиграть». Например, для ускорения тестирования наоборот оставить только 10% тестов, набравших меньше всего голосов «против».
0
Вам работу то предложили или нет?
+2
Я пробовал делать так:
1. оптимизировал все фильтры, убирал повторяющиеся * и?
2. затем делал граф/дерево как-то так:
Код неточный, пишу по памяти. Такое добавление проходило почти мгновенно.
В конечных точках паттернов оседали actions.
3. Потом для каждого сообщения проходил рекурсивно по его символам через полученный граф во втором пункте, используя алгоритм похожий на is_match отсюда, но переделанный для прохода по графу.
Теоретически это должно было сильно сократить количество проверок и ускорить алгоритм, так как мы не проверяем начальные символы паттернов снова а движемся в направлении листьев дерева/графа. Но сожалению это по какой-то причине работало в два раза медленнее решения с самописным match, который в итоге и послал на конкурс. На моих тестах этот match минимум в 3 раза по скорости опережал скомпилированный regex, я удивляюсь как здесь у некоторых ребят из конкурса регулярки оказываются быстрее моего решения…
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, я удивляюсь как здесь у некоторых ребят из конкурса регулярки оказываются быстрее моего решения…
0
1) Убирать повторяющиеся
2,3) Если я правильно понимаю, ваш
'?'
не корректно.2,3) Если я правильно понимаю, ваш
is_match
при встрече '*'
начинает перебирать все комбинации суффиксов строки и паттерна и сопоставлять их, в структуру дерева же эта звёздочка не кодируется. У меня же звездочки закодированы в структуру дерева в виде реккурентных связей (так что это уже не дерево, а граф в общем виде) NFA. После детерминизации время прохода по DFA пропорционально длине строки и не зависит от наличия звездочек.0
1) — да, с дуру так написал, не убирал их конечно.
А по поводу is_match, да, много рекурсивных вызовов на один паттерн, зависит от его сложности. Мне кажется, это вариант NFA.
Интересно увидеть графическую развертку DFA для для паттерна со звездочкой/ами. Там тоже должны быть циклы/рекурсии где-то внутри по идее.
А по поводу is_match, да, много рекурсивных вызовов на один паттерн, зависит от его сложности. Мне кажется, это вариант NFA.
Интересно увидеть графическую развертку DFA для для паттерна со звездочкой/ами. Там тоже должны быть циклы/рекурсии где-то внутри по идее.
0
Sign up to leave a comment.
Разбор решения занявшего второе (пока что) место в конкурсе Hola по программированию почтовых фильтров на JavaScript