Спасибо всем участникам нашего последнего конкурса по программированию!
Мы получили 408 решений от 237 различных участников (в конкурсе участвует только одно, последнее из решений от каждого участника, и мы публикуем именно последние варианты). Кроме того, 7 решений было отправлено нам либо после окончания срока приёма работ, либо сотрудниками Hola, и мы рассмотрели их вне конкурса.
64 решения, или 16% от общего числа, были отправлены в течение последних суток до окончания срока. Из них 15 были отправлены в течение последнего часа, а самое последнее «проскочило» за 34 секунды до дедлайна.
Тесты на корректность прошли 114 программ, что составляет 48% от числа протестированных.
Самое короткое решение уместилось ровно в 666 байт, а самое длинное растянулось на 90274 байт.
Один из участников был дисквалифицирован за попытку обмануть тестовую систему. Забавно, что его результат всё равно уступил честному результату победителя конкурса.
Двое участников разделили второе место, так как производительность их решений оказалась одинаковой в пределах точности измерения. В связи с этим мы увеличили призовой фонд на $500 и наградили каждого из них призом по $750.
Поздравляем победителей:
- Денис Крешихин — приз 1500 USD.
- Илья Макаров и Юрий Килочек — призы по 750 USD.
- Сергей Голуб — приз 500 USD.
Дополнительно мы решили наградить автора самого короткого корректного решения. Специальный приз в 350 USD получает Надав Ивги.
Полная таблица результатов и подробности о тестировании — в репозитории на GitHub.
Мы постараемся учесть многочисленные замечания участников при подготовке следующего конкурса.
Комментарии (119)
KingOfNothing
08.01.2016 18:28+2Очень интересно читать решения других участников. Например, я тоже копал в сторону nfa/dfa, но мои тесты показали, что регулярки работают быстрее. Как оказалось нет :-) Спасибо за конкурс!
Было бы интересно услышать комментарии от победителей о своих решениях и процессе разработки. Еще было бы интересно узнать, кто сколько времени посвятил конкурсу.
Alex_At_Net
08.01.2016 18:40Очень интересно было бы почитать разбор решения Дениса и как оно такое получилось — выглядит необычно.
feldgendler
08.01.2016 18:43+3Я предложил бы всем победителям написать немного о том, как решали задачу.
zBit
08.01.2016 21:04-1Какой-то странный тест производительности.
Мы с коллегами тоже участвовали в конкурсе, у нас свои методы тестирования производительности, как нам кажется, более объективные cloud.mail.ru/public/CZJu/iunQzxYW6 (bash скрипты), и у нас предложенные в конкурсном репозитории решения показали совсем другие цифры.feldgendler
08.01.2016 21:43Можете показать код, которым генерировали тестовый набор данных, или рассказать методику?
zBit
08.01.2016 21:48-1Взяты из открытых источников. Не в этом суть. Вы свой тестовый набор данных подставьте, посмотрите разницу, это если интересно :) Я не намекаю, что должен быть в тройке призёров, я только лишь хочу сказать, что методика измерения производительности может сильно влиять на результат. В случае с bash скриптами на 100% исключается оптимизация движком, правда появляется время загрузки тестовых данных, но это время у всех будет примерно одинаковым и на большом количестве выборок можно посчитать avg и судить по нему.
feldgendler
08.01.2016 21:51Наш набор, а также код, которым он сгенерирован, находится в директории tests в репозитории.
zBit
08.01.2016 22:21-1К сожалению, нет возможности сейчас откорректировать свой вариант бенчмарка и добавить в него ваш набор тестовых данных… Поэтому предложил это сделать вам. Там изменять надо всего ничего, одну или 2 строчки, ну и файлы с данными рядом положить.
feldgendler
08.01.2016 23:22Я не сомневаюсь, что расстановка лидеров от этого изменится. Я хочу понять, почему Вы считаете свой набор более справедливым.
zBit
08.01.2016 23:24-1Да не в наборе тестовых данных дело, а в методике тестирования. Прошу прощения, если написал так, что вы подумали, что я жалуюсь на набор тестовых данных.
feldgendler
08.01.2016 21:51Что такое «оптимизация движком»?
zBit
08.01.2016 22:02-3Неплохой троллинг :)
Если это, таки, был не троллингНу самый простой способ узнать про оптимизацию V8 — погуглить.
В процессе выполения скрипта движок V8 умеет определять какие функции можно оптимизировать, вывести их выполнение на более низкий уровень, что увеличивает скорость выполнения этих функций в разы.feldgendler
08.01.2016 22:06Это был не троллинг. Я просто само выражение не понял. Что V8 оптимизирует, я, конечно, знаю, но почему Вы считаете, что это надо исключить? Какой будет движок, было объявлено заранее.
zBit
08.01.2016 22:19-2Вы запускаете фильтр 10 раз с одними и теми же тестовыми данными. Вы думаете в реальной ситуации вам шлют по 10 раз одно и то же письмо всегда? Я тоже считаю, что нет. Поэтому, думаю, что нужно было исключить оптимизацию V8 между запусками фильтра по одному и тому же набору данных. Если бы это было 10 запусков фильтра по разным наборам данных, то всё нормально.
Каждая итерация теста производительности у нас ассоциируется с временем жизни почтового ящика. У вас этот почтовый ящик проживает 10 одинаковых жизней.
Это исключит не только оптимизацию движком, но и кеш внутри самого фильтра. Например, я все регулярки кеширую и при повторном использовании фильтра с тем же набором тестовых данных он отработать немного быстрее, т.к. всё что нужно уже будет в кеше, что тоже считаю не очень честным решением, т.к. именно такой подход к тестированию как у вас позволяет немножечко читерить и уже не важно на сколько хорош твой алгоритм с теоретической точки зрения, а важно угадал ты или нет с тем как будут проводить тестирование.feldgendler
08.01.2016 23:18+1Мы запускаем каждый проход в новой виртуальной машине, поэтому кэширование в тестируемом коде исключено. При этом оптимизация V8 действительно может влиять на следующие проходы, но в реальности так было бы — код запускался бы многократно без перекомпиляции. На оптимизацию V8 не могли бы повлиять конкретные данные, а только их статистическое распределение, которое в реальной ситуации вполне могло бы быть неизменным от раза к разу.
zBit
09.01.2016 00:25-1Хорошо, я и не спорю, хочу только мысль свою донести.
Случайно ссылкой ошибся выше. Сейчас добрался до компа, обновил всё, добавил ваш тестовый набор данных, запустил bash-скрипт.
Итог$ ./run4.bash ./submissions/Sergey\ Golub/filter.js AVG = .78901676 BEST = .771083600 $ ./run4.bash ./submissions/Yuri\ Kilochek/filter.js AVG = .76020389 BEST = .735113200 $ ./run4.bash ./submissions/Ilya\ Makarov/filter-with-memo.js AVG = .85580227 BEST = .820365600 $ ./run4.bash ./submissions/Denis\ Kreshikhin/kreshikhin-filter.js AVG = .82748225 BEST = .812334200
Проверил только призёров и результат уже другой, тот кто на втором месте оказался на первом. Если интересно, то могу моим способом всех остальных тоже проверить и выложить результат, мне не сложно. Но тут время зависит ещё от некоторых факторов, загруженность процессора и прочее, т.к. выполнял на своём ноуте из под рут-системы. Думаю, что на выделенной виртуалке на свободном новеньком серваке результаты будут более показательыми.feldgendler
09.01.2016 01:28+1Я попробовал делать как-то вроде этого, всё равно разброс между запусками одной и той же программы шире, чем зазор между лидерами. Это означает, что мы получили много хороших решений.
AKashta
09.01.2016 12:47+1То есть вы считаете, что разница между вашим подходом (запуск в песочнице vm) и обычным запуском (require модуля и вызов функции) укладывается в статистическую погрешность? Можете объяснить, почему некоторые решения при вашем методе запуска работают в несколько раз медленнее? Уверен, что мое решение не единственное такое. Интересно было бы посчитать альтернативную таблицу результатов для всех участников, прошедших тест на корректность.
feldgendler
09.01.2016 18:14Нет, запуск в VM и без сильно различается. Но мы тестировали всех в одинаковых условиях.
Temmokan
09.01.2016 17:32+2Возможно, следующий раз имеет смысл публиковать также инструменты, которыми всё тестируются — коль скоро разные способы существенно влияют на результат. Чтобы участники могли не только проверить годность на эталонном варианте, но и измерить производительность разных подходов эталонным скриптом.
По мне, «в новой виртуальной машине» должно означать, что параметры производительности этой машины, с точностью до ошибки эксперимента, ровно те же (и это можно как-то проверить при тестировании).
В любом случае было интересно.feldgendler
09.01.2016 18:23+3Обдумываю мысль в следующий раз использовать реальную виртуальную машину наподобие QEMU, раз «виртуалки» Node.js вносят такие сильные искажения.
Temmokan
09.01.2016 19:13Так было бы лучше. Свои варианты я тестировал на KVM-ной виртуалке (для чистоты эксперимента, хост-машина также перегружалась перед очередным массивом проверок), и, судя по итогам конкурса, итоги моих тестов дали бы иной результат.
При точном знании способов проверки будет проще создавать правильным образом оптимизированный код.
Спасибо!Temmokan
10.01.2016 19:54Для авторов минусов: в моих тестах мои решения не попали магическим образом на первые места. :)
Кстати, обсуждения по итогам не менее интересные по количеству идей и предложений, нежели перед началом.
Надеюсь, организаторы конкурса найдут дебатах что-нибудь полезное. ну, и не только организаторы.
zBit
09.01.2016 19:16Кстати, когда вы писали про виртуальную машину в условиях конкурса, я подумал о нормальной виртуальной машине, а не о модуле vm… Думаю, что с этим лоханулся не я один…
Methos
08.01.2016 21:09Решение должно быть на чистом JS. Если Вы предпочитаете CoffeeScript или подобные языки, необходимо оттранслировать решение в JS перед отправкой.
Почему нет чистого js-кода от Nadav Ivgi? github.com/hola/challenge_mail_filter/tree/master/submissions/Nadav%20Ivgi
И почему вы посчитали 666 байт не чистого js-кода?zBit
08.01.2016 21:11Да нет, вроде чистый JS. Только уж слишком топорное решение. Никакой алгоритмической ценности нет.
feldgendler
08.01.2016 21:41+1github.com/hola/challenge_mail_filter/blob/master/submissions/Nadav%20Ivgi/filter.js — это чистый JS, в смысле, что не CoffeeScript или подобное.
vermilion1
08.01.2016 22:20+3Fat arrow, она же => является частью ECMAScript 2015
feldgendler
08.01.2016 23:20Теперь понимаю, что Вы поняли «чистый JS» как чистоту стандарта. Такой вариант прочтения не приходил нам в голову до сих пор, иначе мы внесли бы в текст уточнение. Жаль, что так получилось.
Methos
09.01.2016 16:37Ах да, читал про это некоторое время назад.
По сути, это замена function(), просто более красивее и чище.
Ерунда, можно пренебречь.
AKashta
08.01.2016 22:45+1Не могли бы вы опублировать скрипты для тестов производительности? На моей машине (i5-650 3.2 GHz, win7) получаются совсем другие результаты:
- Denis Kreshikhin — 421
- Ilya Makarov — 468
- Yuri Kilochek — 327
- Sergey Golub — 359
- Andrew Kashta — 359
Прогнал примитивный скрипт по 10 раз для каждого и выбрал лучшие результаты:
var filter = require('./submissions/Denis Kreshikhin/kreshikhin-filter'); //var filter = require('./submissions/Ilya Makarov/filter-with-memo'); //var filter = require('./submissions/Yuri Kilochek/filter'); //var filter = require('./submissions/Sergey Golub/filter'); //var filter = require('./submissions/Andrew Kashta/filter'); var input = require('./tests/large_input.json'); var start = new Date(); var result = filter.filter(input.messages, input.rules); console.log('elapsed: ' + (new Date() - start).toFixed());
Кто-нибудь может погонять у себя скрипт? Интересны результаты в различных средах исполнения.zBit
08.01.2016 23:09-1Есть разница между 32-х и 64-х битными версиями. Возможно это ваш случай.
AKashta
08.01.2016 23:26Проверил и там, и там. У меня на node x64 все решения получаются немного медленнее, но кардинальной разницы нет. Возможно, дело в ОС.
AKashta
09.01.2016 00:33Отвечу сам себе. Дело не в битности и не в ОС, а в способе запуска тестов. Организаторы запускают через vm, для моей реализации это почему-то оказалось критично. Безхитростный запуск отрабатывает в 2.5 раза быстрее чем через tests/test.js.
deniskreshikhin
09.01.2016 00:51Да, судя по всему v8 не производит какие-то оптимизации, когда код выполняется не в текущем контексте, а require же использует текущий контекст. Вроде даже для текущего контекста резервируются отдельные регистры.
Т.е. разница в методах выполнения script.runInContext или script.runInThisContext.
В общем-то это косвенно можно было понять по комментарию habrahabr.ru/company/hola/blog/270847/#comment_8657097, что выполнятся будет на vm и очевидно не в runInThisContext
Для меня на самом деле это было неожиданностью, такое поведение v8.AKashta
09.01.2016 01:44Проверил, действительно, если переделать тест на использование runInThisContext вместо runInContext, начинает работать в 3 раза быстрее. Понять бы еще, что именно так тормозит в не текущем контексте
Antelle
09.01.2016 20:10+1Тормозит доступ к global (как, соответственно, и вызов любой функции из глобального пространства). Простой пример:
'use strict'; var code = 'function f() { }; for (var v = 0; v < 10000000; v++) { f(); }'; console.time('local'); eval(code); console.timeEnd('local'); var vm = require('vm'); var context = vm.createContext(); console.time('vm'); vm.runInContext(code, context); console.timeEnd('vm');
local: 88.315ms
vm: 12191.585ms
Если заменить на IEFE — выполняется за одинаковое время:
var code = '(function() { function f() { }; for (var v = 0; v < 10000000; v++) { f(); } })()';
Если у Roman Pletnev check засунуть внутрь filter, его код быстрее.
(если что, я ни с кем не аффилирован и в конкурсе не участвовал)zBit
09.01.2016 21:18Думаю, что это серьёзный повод пересмотреть результаты. Заодно и методику замера изменить. И запускать по 10 итераций на каждое решение и запустить так все решения 10 раз. В итоге будет по 10 лучших результатов на каждое решение и из них выбрать лучшее. Так будет справдливее! А то я сейчас тесты гоняю и время от времени некоторые тесты на 30-40% быстрее начинают работать, а некоторые наоборот медленнее… И всё это на одном и том же наборе данных (на том, что предложено организаторами конкурса).
И самое оригинальное решение надо тоже пересмотреть, как мне кажется, оно никапли не оригинальное, оно слишком простое и просто маленькое по размеру, но никак не оригинальное. Но последнее это моя субъективная точка зрения.feldgendler
09.01.2016 21:37Как и в прошлом конкурсе, мы сделаем выводы на следующий раз, но пересматривать результаты не будем.
Мы не утверждали, что то решение — самое оригинальное. Специальный приз присуждается по нашему субъективному усмотрению. Например, в одном из конкурсов его получил самый младший участник.Antelle
09.01.2016 22:02+1Раз уж вы хотите оптимизацию под дивжок (а не под весь зоопарк js vm) — по идее, надо выкладывать и конфиг движка, который будет использоваться (например, внутри vm или нет, под какой архитектурой, os, с какими ключами будет запускаться — производительность операций от этого может меняться). А то, получается, рассчитывали на одно, увидели другое. Это как, к примеру, инлайнинг отключить в компиляторе. Я бы выкладывал тестовый код и конфиг, естественно, без датасета (возможно ещё без проверки валидности).
batya15
08.01.2016 23:15-1Typealias Nonmutating 563
Dmitry Rybin 920
i5-3230M@2.6GHz/win7(64)/node-5.3.0/
Несколько раз прогнал
vermilion1
08.01.2016 23:18+11. git clone github.com/hola/challenge_mail_filter.git
2. cd challenge_mail_filter
3. node --expose-gc tests/test.js submissions/*****/*****.js
Vitalik
08.01.2016 23:43+6Прежде всего, спасибо организаторам за интересный конкурс!
Мое последнее отправленное решение, к сожалению, даже не прошло тесты на корректность из-за незамеченного вовремя бага в коде, ответственном за мемоизацию (наложились друг на дружку три моих ошибки: одна пропущенная проверка в коде, из-за чего на определенных данных запоминались не те правила, которые следовало запомнить + слабое место в моих тестах на корректность, в которых отсутствовали те самые правила, на которых проявлял себя баг + отправка решения за 20 минут до дедлайна, когда уже не было времени перепроверить всё вдоль и поперек). Тем не менее, алгоритм получился не совсем уж провальным: на бенчмарке, предоставленном организаторами, мое решение примерно вдвое медленее победителя, а на моем бенчмарке, который меряет только время выполнения функции filter(...), алгоритм работает примерно в 1,5-2 раза быстрее решения победителя (на тех же тестовых данных, которые использовались организаторами). То есть сам алгоритм, в принципе, неплох, поэтому я рискну о нем рассказать.
Вместо регулярок я использовал дерево, в котором каждому узлу соответствует определенный символ из одного или нескольких [имеющих общее начало] фильтров. Дочерние элементы узлов хранятся в массивах, а код следующего символа в анализируемом адресе служит индексом в таком массиве, что позволяет находить подходящий следующий узел за минимальное время, а на сравнение адреса с большинством неподходящих фильтров время не тратится вовсе. Решение на основе дерева оказалось [на использованных мной тестовых наборах и на моем бенчмарке] примерно в 12-14 раз быстрее «тупого» решения с регулярками, а если вычесть «неизбежные» расходы, которые являются общими для обоих решений и считать только время сравнения строки с фильтрами, то прирост скорости достигал примерно 25 раз. Правда, я допускаю, что мое «тупое» решение с регэкспами тоже можно было бы оптимизировать и разрыв был бы меньшим, но все равно вариант с деревом, по-моему, намного быстрее. На тестовых данных организаторов + моем бенчмарке этот вариант (т.е. вообще без мемоизации) показывает примерно такое же время, как решение победителя. Но на бенчмарке организаторов он демонстрирует жуткий провал, несмотря на отсутствие сообщений «disabled optimization...», связанных с моими функциями. Поскольку в рамках этого конкурса я впервые попробовал поработать с Node.js, да и вообще с оптимизацией производительности кода на javascript, то подобная ситуация для меня пока является странной и непонятной.
Что касается мемоизации, то на нее у меня оставалось мало времени и некоторые идеи так и не были опробованы. Из того, что я попробовал, но мне не понравилось — запоминание списка правил для пары адресов from+to. На тех тестовых данных, которые я использовал для разработки, такая мемоизация показывала худшие результаты, чем раздельное сохранение списков подходящих правил для from- и to-адресов с последующим их пересечением. Возможно, я плохо продумал такой вариант мемоизации или просто тестовые данные были неподходящими для него, но в итоге я от этого отказался и сделал отдельную мемоизацию для каждого адреса, а не для пар адресов. Причем для мемоизации from и to я использовал разные подходы.
Тут стоит сделать шаг назад и рассмотреть способ формирования «финального результата». Перед разбором очередного «письма» я инициализировал буфер, в котором i-й байт соответствовал i-му правилу и мог иметь одно из 4 значений: 0 — это правило не подходит этому письму, 1 — правило подходит адресу from, но не to, 2 — наоборот, 3 — правило подходит обоим адресам и должно присутствовать в финальном результате. Во время обхода дерева, когда мы достигаем конца проверяемой строки (адреса), то берем хранящиеся в соответствующем узле дерева номера правил и увеличиваем значения соответствующих этим номерам байтов в буффере на 1 или 2 в зависимости от того, анализируем ли мы сейчас from- или to-адрес. Мы также обновляем «счетчик подходящих правил», когда очередной байт становится равным 3 (это нужно для последующей аллокации результирующего массива нужной длины). В самом начале анализа письма мы инициализируем все байты в буфере либо нолями, либо единичками (если правило имеет тривиальный from-паттерн (например, пропущенный), которому подходят любые from-адреса), либо двойками (если правило имеет тривиальный to-паттерн), либо тройками (если правилу подходят все письма). Затем этот буфер передается функции, которая сравнивает адрес to со всеми нетривиальными to-фильтрами (и увеличивает на 2 байты в буфере, соответствующие подошедшим фильтрам), затем то же самое проделывается с from-адресом и нетривиальными from-фильтрами, после чего у нас будет буфер, в котором все байты, соответствующие подошедшим правилам, будут равны 3. Дальше мы проходим по этому буферу от начала до конца и добавляем в результирующий массив все правила, для которых соответствующие байты равны 3.
Возвращаясь к мемоизации: при запоминании списка правил, подходящих to-адресу, я просто сохранял состояние буфера после сравнения адреса с нетривиальными to-паттернами. Для from-адресов такой подход не применим, т.к. они обрабатываются во вторую очередь и состояние буфера после их обработки зависит также от того, какой to-адрес анализировался перед этим. Поэтому для мемоизации from-правил приходилось отслеживать изменения в буфере (номера байтов, изменившихся при сравнении from-адреса с нетривиальными from-паттернами) и сохранять множество номеров изменившихся байтов. (В этом месте как раз и закрался ранее упомянутый баг — не влияющий на скорость, легко исправимый, но обнаруженный уже после дедлайна).
Поскольку мемоизация очень хороша для повторяющихся адресов, но предположительно очень плоха, например, для спама, то оставался вопрос «как нам по тестовым данным определить, включать для них мемоизацию или нет?». Довольно быстро пришло понимание того, что еще лучше не включать/выключать мемоизацию в целом, а делать ее выборочно: для одних адресов сохранять результаты их обработки, а для других — нет. С учетом нехватки времени, все сложные идеи отсеялись и осталась самая простая: почему бы не сохранять результаты обработки адресов, начиная, например, со второго или третьего их обнаружения? Тогда весь одноразовый спам пролетал бы мимо мемоизации и сопутствующих ей немалых расходов, а вся регулярная переписка быстро попадала бы в «кэш». Неэффективным такой подход был бы только на довольно специфических наборах данных (только спам, только повторяющаяся переписка, либо — самый неудобный случай — «все адреса встречаются по несколько раз, но не более того»), но нам-то обещали смесь спама с нормальной перепиской, а на таких данных выборочная мемоизация должна быть практически идеальной, не допуская провала ни на спам-подмножестве данных, ни на «нормальной переписке». Что и было зафиксировано при проверке производительности на разных наборах данных: на «максимально пригодных для мемоизации» результаты были почти на уровне «всегда включенной мемоизации», на «максимально непригодных» — ощутимо (на треть) уступали версии без мемоизации, но зато в разы превосходили версию с безусловной мемоизацией, а на смешанном наборе «спам + нормальная переписка» показали самый лучший результат из всех опробованных вариантов. Поэтому эта версия и была отправлена организаторам как финальная. К сожалению, с незамеченным багом :(
В общем, это было интересное интеллектуальное упражнение. Оно подтолкнуло к тому, чтобы наконец-то пощупать Node.js, лишний раз напомнило о том, как важно хорошо продуманное тестирование и почему не стоит затягивать работу до дедлайна :) А также поставило перед вопросом «почему один и тот же код на одних и тех же данных, но при другом бенчмарке показывает такой провал в производительности без очевидных [во всяком случае мне, неопытному в этом деле] проблем с деоптимизацией?», с которым я попробую на досуге разобраться.
p.s. Поскольку в комментариях поднялfeldgendler
08.01.2016 23:55+2Большое спасибо за развёрнутый комментарий! Очень интересно. Жаль, что Ваше решение не прошло. Мы всё равно его обязательно почитаем.
К тому же, хотя денежные призы и ценные, здо?рово, что Вы цените саму возможность решить интересную задачу. Мы будем устраивать новые конкурсы и постараемся сделать так, чтобы таких случаев, когда хорошие решения не проходят из-за мелких ошибок, было поменьше.
rmaksim
09.01.2016 00:15+3хе, тоже не дотестил )))
провалился на test_glob(script, '?', ['.', '?', '*', 'z'], ['zz', '\\?']);
не ожидал в проверке на корректность одного '?' в правиле
но если исправить в одном месте, то все гут — было бы 35 место
в принципе доволен результатом )))
спасибо за конкурс !
rmaksim
09.01.2016 06:03+2хм
если бы #12 Pavel Gruba вставил бы самый простой кэш — его результат был бы на 1 месте
ну как же так забыть про кэш…
p.s. правда тестил на node v4.2.1, но думаю не сильно что-то измениться?
ivann
09.01.2016 13:52+2Может измениться. Например, из-за особенностей запуска тестов организаторам и, выиграли те, кто имел все объявления методом внутри функции filter. Сыграло роль как сработал компилятор и рантайм v8. Между 4.2 и 5.0 он может сильно различаться.
ionicman
09.01.2016 12:40+1Спасибо за отличный конкурс!
Очень понравилось лаконичностью решение Сергея Голуба. Ну и 1-2 места респект, господа. Очень было бы не плохо увидеть статью, где бы Вы рассказали про маски.
Сам я на 16 месте.
P.S. гн zBit Вы на каком месте? По нику не вижу Вас в табличке. Так, помериться просто :)ionicman
09.01.2016 13:06Опишу оптимизации, которые использовал, может кому интересно будет.
- Упаковка regexp-ов в массив правил
- Кэш по ключу «from + разделитель + to» — т.е. если встречается пара from/to, которая уже встречалась, то сразу отдаются подготовленные actions по данному ключу из массива кэша
- Т.к. для кэша надо считать ключ «from + разделитель + to», то можно и проверять сразу всю это строку за один раз одним regexp-ом вида «regexpFrom + разделитель + regexpTo»
zBit
09.01.2016 13:3719 место.
Прогнал все решения по своим тестам на корректность, которые были проверены по «эталонной реализации», получилось -19 человек из тех что заняли хоть какое-то место. Т.е. не у всех ещё «по-настоящему» корректно работает фильтр.
Сейчас сижу выбираю где виртуалку поднять, чтобы тест на производительность по моему бенчмарку прогнать с теми тестовыми данными, что были сгенерированы для конкурса организатором. Посмотрим что выйдет :)
ivann
09.01.2016 13:07+3Один из участников конкурса не имеет доступа к хабру и попросил меня опубликовать его письмо организаторам. В кратце: код проверки решения сам содержит ошибки. Привожу его письмо целиком.
First of all, let me congratulate you on the contest, it was extremely
well organized. This is the first time I have participated in a
programming challenge or used NodeJS, but even so I can see the level of
effort and experience that went into organizing the event.
At the same time, after reviewing your testing code, I would like to
point out that the correctness tests you have used are a bit naive. As a
result, the competition rankings as it stands now are incorrect.
I did not check all the submissions, but after looking at several of the
top performers, I was able to quickly find out that the following two do
not pass correctness tests corresponding to the contest rules:
4. fb5813a09c0f95242cb
6. Petr Shalkov
I think it is fair to expect many more submissions to have incorrectly
implemented algorithms. So, understanding that an incorrect algorithm
can perform much faster that a properly working one, I would ask you to
reevaluate the final rankings. For your convenience I am attaching the
correctness test suite I have used myself (the tests assume that the
module being tested is located in an 'app.js' file). These are the tests
that can be found at 'https://github.com/ToPal/HolaTests' along with my
own modifications.
I would also like to thank you for giving all of us the opportunity to
participate in this event, and push many of us to finally get or hands
wet with NodeJS. A big thank you!
Thanks,
Roman Pletnevfeldgendler
09.01.2016 18:18Роман прислал большую подборку тестов, за что ему спасибо. К счастью, призёры проходят все тесты.
ivann
09.01.2016 18:30Алексей, спасибо за ответ. Хотелось бы, чтобы вы также прокомментировали недостатки тестов на производительность, которые указали Роман и Алексей (zBit)
feldgendler
09.01.2016 21:39Учтём на будущее, что vm в Node.js вносит сильные искажения в замеры производительности. Рассмотрим возможность в следующий раз применять полноценную виртуальную машину наподобие QEMU.
ivann
09.01.2016 13:09+3Второе письмо об оценке производительности:
After looking at your performance testing code I have to say it is
flawed so much that the final rankings do not make any sense at all.
Particularly this code is the culprit:
vm.runInContext(id + '.res = ' + expr + '(' + id + '.messages, ' + id +
'.rules)',
Attached is my original submission that originally ranked quite badly
(27th place). As you can see, I did not change my algorithm one bit, all
I have done is simply moved all the function declarations inside the
exported filter function. If you run your original test.js benchmark,
you will see that in this form, my code now performs 5 times faster and
easily beats the original top performers!
Please, please, please, consider rerunning the original submissions
using a direct invocation of modules' filter functions:
require('./app.js').filter(messages, rules)
instead of using runInContext, as it is in no way correlated with the
real world performance of submitted algorithms.
Thanks,
Roman PletnevzBit
09.01.2016 15:06+1Минут 5 назад свой бенчмарк запустил, по 1 разу каждое решение, Roman Pletnev с лучшим результатом, причём с хорошим отрывом от второго места. Сейчас запустил тот же бенчмарк, только по 50 раз каждое решение и выбирается лучшее время. Использовал исходные данные из тех что были на конкурсе. Учитывая, что некоторые решения ну очень уж медленные — результат по всем конкурсантам будет часа через 2-3…
Запустил на виртуалке на DO (1 GB Memory / 30 GB Disk / NYC3 / Ubuntu 14.04 x64 vmlinuz-3.13.0-71-generic / nodejs v5.0.0-x64).
Постараюсь сегодня успеть опубликовать результаты своего тестирования на гитхабе.
zBit
09.01.2016 19:19+5Как обещал, альтернативные результаты конкурса.
github.com/zbitname/hola_nodejs_challenge
Заранее прошу не бить. Сделал это только лишь для того, чтобы показать на сколько сильно могут отличаться результаты в зависимости от методики тестирования.
OLS
10.01.2016 01:48Еще одни альтернативные результаты конкурса:
github.com/OLS-RU/challenge_mail_filter
Но уже на другом тестовом файле (с большим количеством записей и более сложными масками).
Мое субъективное мнение — на сложных тестах многие спорные моменты относительно методики тестирования, обсуждавшиеся в диалогах выше, перестают значимо влиять на результат, и он (результат) становится более точным отражением усилий участника, направленных на вопросы алгоритмической оптимизации.
В любом случае, отдельная признательность организаторам конкурса за прошедшее мероприятие, достаточно нетривиальное на сегодняшний день.
4dro
10.01.2016 22:46+1Сделал тупую ошибку — Stepan Pupkin/solA.js
function match(email, charPieces) { ... var maskLen = mask.length; ... if (email.length <= maskLen) { return false; } ...
Там очевидно нужно было использовать < вместо <=. Я как-то пропустил это при тестировании. А так бы был где-то посередине таблицы.
А вообще, надо было отправлять solB (regExp, а в случае отсутствия * — сравнение по charCodeAt()), которое на тестах организатора врывалось в 15 лучших. К сожалению, с моими тестовыми данными оно показывало время хуже, чем solA.OLS
11.01.2016 06:45-1А на моем тесте
github.com/OLS-RU/challenge_mail_filter
Ваше решение (solA, в случае исправления ошибки) было бы 10-ым с результатом 8,009 (тест на корректность был бы пройден).
Gromo
11.01.2016 12:04+3Идеальных конкурсов не бывает, но организаторы очень старались. Большое спасибо организаторам за конкурс, а участникам — за интересные решения. Критерии и способы оценки у всех разные, в данном конкурсе способы и результаты тестирования видны всем, а не являются «черным ящиком».
Лично мне понравилось решение Sergey Golub — при высокой скорости обработки такой код понятен с первого взгляда, и в дальнейшем его поддержка и доработка будет простой, что порой имеет большее значение, чем выигрыш в несколько мс.rmaksim
11.01.2016 13:19для интереса посмотрите ещё код Pavel Gruba
код практически такой же с первого взгляда +- пару мелочей
просто он магическим образом забыл про кэш (
но если добавить кэш — то из-за этой пары мелочей работает довольно быстро (у меня на тестах организатора получилось для него 1 место)
zBit
11.01.2016 13:09А самое оригинальное решение тоже будет пересмотрено? Чтобы не разбираться в чужом коде, может попросить людей прислать описания их алгоритмов человечьим языком?
feldgendler
11.01.2016 14:05В этот раз мы решили присудить специальный приз не за оригинальность, а за компактность кода.
zBit
11.01.2016 14:25А в условиях конкурса написали, что выберите самое оригинальное решение, а не компактное…
deniskreshikhin
11.01.2016 17:38Объявление: Мы решили пересмотреть итоги конкурса из-за серьёзных недостатков, обнаруженных в тестовой системе. Новые итоги будут через 1–2 дня.
Вот, интересно. А это на каком основании? Юридически, ваш пост habrahabr.ru/company/hola/blog/270847 является публичной офертой, и там указано что:
Победит тот, чей код будет самым быстрым при условии прохождения тестов на корректность.
Победители будут объявлены 8 января 2016.
Я как лицо крайней заинтересованно, хочу спросить вас, на каких юридических основаниях вы меняете уже объявленные результаты конкурса?
Вы можете сделать новый конкурс, но менять результаты этого — не можете. Т.к. участвуя в конкурсе, я согласился с вашей офертой, соответсвенно вы не можете менять ее условия без моего согласия, и одновременного согласия других участников.
Результаты объявленные 8 января — единственно предусмотренные по договору. Поэтому требую объяснений.
Вопрос 1500 долларов довольно серьезный, мне и к юристу не сложно обратиться по этому поводу.feldgendler
11.01.2016 17:49+1Мы неправильно определили, чей код самый быстрый. Не меняя заявленного критерия присуждения призов, мы исправляем ошибку в тестах на соответствие этим критериям.
deniskreshikhin
11.01.2016 17:58-4В вашей оферте про это ничего не сказано. Я сразу говорю — если вы поменяете результаты конкурса, мне придется обратиться в суд.
Договор надо исполнять. А в нем нет ни слово о том, что предусматриваются какие-то дополнительные прогоны и т.д., ни критерии тестирования, ни т.п. У вас было 2 недели фактически, что бы провести тестирования как надо, и определится к 8 января.
Хотите что-то поменять, создавайте альтернативный прогон, с призами или нет но эти результаты юридически вы не имеете права трогать.
Это моя принципиальная позиция.
zBit
11.01.2016 17:49+2Если вы уверены в том, что ваш алгоритм действительно быстрее всех, то вам не стоит беспокоиться о том, что кто-то может вас сместить с 1-го места.
Но вообще, по-честному, замеры были произведены некорректно, это объективная оценка и с ней согласились организаторы конкурса. Надо смириться с этим.deniskreshikhin
11.01.2016 18:05Честно это когда договор исполняеют обе стороны. Я свою часть выполнил честно, не мухлевал, отослал в срок, все как надо.
У организаторов было куча времени что бы все проанализировать и сделать тестирование как им хочется. Никто не тянул их «за руку». Если опубликовали результаты, то должны выполнять свои обещания.
В конечном итоге результат зависит не только от того runInContext/runInThisContext, а от количества фильтров/писем, разрядности процессора, способа сборки node.js, средней длины писем и сложности фильтров.
Т.е. элемент неожиданности заложен в сам конкурс, и я участвуя в нем учитывал это. А сейчас тестовые условия переделывается постфактум, без извещения других участников, а тем более объявленных победителей. Это прямое нарушение оферты.
Т.е. проблема в юридическом аспекте, а не в том чей алгоритм лучше.zBit
11.01.2016 18:28У организаторов было куча времени что бы все проанализировать и сделать тестирование как им хочется.
Да, у них было много времени (если учесть, что они по праздникам работают), но они этого почему-то не сделали.
Элемент неожиданности должен быть только в тестовых данных (количество условий, значения), а не в методах тестирования, иначе это не конкурс, а рулетка какая-то. Некорректный метод тестирования вносит слишком большую погрешность, согласитесь с этим. А теперь поймите людей у которых действительно интересные и эффективные решения практически на любых типах и размерах входных данных, а они почему-то занимают 50+ место, хотя реально должны входить в тройку победителей. И всё из-за того, что они и представить себе не могли, что тестирование будет проводиться именно так (проблема не в тестовых данных, а в том каким образом запускают эти тесты).deniskreshikhin
11.01.2016 18:43+1А теперь поймите людей у которых действительно интересные и эффективные решения практически на любых типах и размерах входных данных, а они почему-то занимают 50+ место, хотя реально должны входить в тройку победителей.
Такая же картина возникает и при разных данных:
Ваша версия:
1 0,556551560 Roman Pletnev
2 0,625574511 Evgeny Zeyler
0 0,641852671 Ecma Scripter Cheater
3 0,646645631 Denis Bezrukov
4 0,686985655 Yuri Kilochek
5 0,707077866 Andrew Kashta
6 0,708169293 Denis Kreshikhin
7 0,708502823 Sergey Golub
8 0,710200874 Black Knight
9 0,752503483 Vitalii Petrychuk
10 0,752972259 Max Brodin
Версия OSL:
1 Denis Bezrukov 4,441
2 Vladislav Nezhutin 5,336
3 Denis Kreshikhin 5,565
4 Yuri Kilochek 5,772
5 Nikolay Kuchumov 5,915
6 Andrey Pogoreltsev 6,569
7 Alexey Larkov 7,252
8 Evgeny Zeyler 7,703
9 R5t4nah6 7,888
10 Alexander Ilyin 8,493
11 Roman Pletnev 8,692
Официальная версия:
1 Denis Kreshikhin 282
2 Ilya Makarov 356
2 Yuri Kilochek 356
3 Sergey Golub 387
…
27 Roman Pletnev 817
…
84 Denis Bezrukov 4118
Т.е. у всех у кого алгоритмы сливаются при выполнении в другом контексте, так же успешно сливаются и при разных входных данных.
Поэтому, какой смысл в пересмотре?
Текущие победители, и не только мой алгоритм, хотя бы стабильно показывают приличный результат вне зависимости от входных данных. Причем как в абсолютном, так и в относительном измерении.zBit
11.01.2016 18:49В моей версии входные данные идентичные тем, что были в конкурсе, изменён лишь метод тестирования. Я писал об этом уже очень много раз, в описании репозитория об этом написано тоже.
deniskreshikhin
11.01.2016 18:53+1Раз можно поменять способ запуска, то почему нельзя поменять количество фильтров/писем?
Если версия Roman Pletnev хорошо ведет себя на 100 фильтрах, но плохо на 1000, то какой результат надо брать?zBit
11.01.2016 19:01-1Об изменении тестовых данных или их размеров никто речи не вёл, на сколько я вижу. Речь идёт о способе тестирования, способе запуска тестов.
deniskreshikhin
11.01.2016 19:15+2А почему можно менять способ запуска, а нельзя поменять количество фильтров?
О количестве фильтров вообще никаких данных не было. А вот о способе запуска были указания feldgendler:
Т.е. многие сетуют что писали и оптимизировали под запуск через require, ну вот в комментарии от представителя компании указано что запускаться будет без require.zBit
11.01.2016 19:26Вот одно из описаний сути проблемы: habrahabr.ru/company/hola/blog/274697/#comment_8730883
deniskreshikhin
11.01.2016 19:43+2Суть проблемы в том, что организаторы:
1. Не дают ни четкого описания окружения, ни количественных/качественных характеристик входных данных.
2. Не следят за своими словами, сначала говорят одно, потому делают другое.
3. Задним числом нарушают свои же обязательства.
Первая проблама да, неприятная, но она не противоречит правилам конкурса и порядку проведения. Так что это субъективное дело.
Вторая и третья проблема лежат в совершенно другой плоскости, в объективной, в юридической. Организатор конкурса опубликовал одни результаты, затем хочет их аннулировать. Сказал одно — сделал другое. Поменял правила задним числом. Выставил других дураками.
Это не просто сомнительный параметры запуска, это явное нарушение своих обязательств, нарушение интересов участников, которые имеют права, на то, что бы конкурс проходил по тем правилам которые были опубликованы в ноябре.
Т.е. если бы в ноябре было опубликованы, что организаторы конкурса могут по своей инициативе или инициативе некоторых участников аннулировать результаты даже после публикации, то я бы просто прошел мимо.
Вот и все. Что касается, что результаты должны соответствовать реальной жизни и т.д. В реальной жизни я бы просто написал модуль на C, и сделал пакет для npm и получил быстродействие на порядок выше чем лучшие из приведенных результатов.
mark_ablov
11.01.2016 19:48> 2. Не следят за своими словами, сначала говорят одно, потому делают другое.
> получил быстродействие на порядок выше чем лучшие из приведенных результатов.
ок. «на порядок» это как минимум 10x. сомнительно.deniskreshikhin
11.01.2016 20:02+1Не сомнительно, я переписывал решения на golang, получил быстродействие на порядок больше.
Причем мое решение даже при другом способе измерения не отсает более чем на 20-30% от других решений.
Я вообще планировал написать большую статью по этой теме, с разбором других результатов, и результатами прогона других решений на golang (я переписал некоторые решения 1 в 1).
Но сейчас понимают что это бессмысленно.
Получить хотя бы свои законные деньги. Какие уж там статьи.
deniskreshikhin
11.01.2016 18:47+1PS.
Но вопрос, не кто лучше, а в том что налицо нарушение договора. Это намного серьезнее, чем неаккуратное тестирование.
В плане методики тестирования никаких четких обязательств авторы конкурса на себя не брали.
А вот в плане дат, победителей и т.д. — все довольно четко, и сейчас мы видим как они собираются нарушить свои же обязательства.
mark_ablov
11.01.2016 19:37> является публичной офертой
С чего вы взяли? По статье 1057?
Дык легко опровергнется по «2. Публичный конкурс должен быть направлен на достижение каких-либо общественно полезных целей».deniskreshikhin
11.01.2016 19:58Публичный конкурс это вид публичной оферты, т.е. публичного предложения. Если организатор его опубликовал, а участник выполнил требования конкурса, то между ними устанавливаются соответствующие обязательства.
Там же кстати, в статье 1058:
1. Лицо, объявившее публичный конкурс, вправе изменить его условия или отменить конкурс только в течение первой половины установленного для представления работ срока.
…
4. Если при изменении условий конкурса или при его отмене были нарушены требования, указанные в пунктах 1 или 2 настоящей статьи, лицо, объявившее конкурс, должно выплатить награду тем, кто выполнил работу, удовлетворяющую указанным в объявлении условиям.
Статья 1059
1. Решение о выплате награды должно быть вынесено и сообщено участникам публичного конкурса в порядке и в сроки, которые установлены в объявлении о конкурсе.
…
В общем, организатор не имеет права менять даже дату публикации результатов, а уж тем более изменять какие-то параметры и публиковать новые результаты.mark_ablov
11.01.2016 20:13Ну я бы начал с того, что я не уверен что Хабр является СМИ (http://rkn.gov.ru/mass-communications/reestr/media/).
И вы почему-то проигнорировали п.2 ст 1057 о том, что конкурс должен быть направлен на достижение каких-либо общественно полезных целей. Если этот пункт не выполняется, то публичный конкурс признаётся несостоявщимся. Правда теоретически можно потребовать оплату усилий, потраченных на выполнение задания (167ая статья), но тут тоже спорно всё.
В любом случае, это теоретические рассуждения, потому что вы будете судиться с израильской Hola Ltd, которая не имеет представительства в России.deniskreshikhin
11.01.2016 20:22-2Публичный конкурс может быть закрытым, т.е не обязательно через СМИ. Причем в РФ есть более расширенная трактовка СМИ, это не только зарегистрированное СМИ. Сайт при некоторых условиях тоже может рассматриваться как СМИ, даже если его нет в реестре. Т.к. важен характер предоставления и распространения информации, а не его нахождение в реестре.
Общественно полезная цель была заявлена «мы ищем талантливых программистов, поэтому авторы интересных решений будут приглашены на собеседования.» Поиск талантливых программистов это общественно полезная цель. Т.к. все олимпиады по программированию, в т.ч. государственные только для этого.
Израиль это вполне правовое государство, найти юриста там не проблема. 1500 USD в Израиле тоже деньги.
Хотя что-то мне подсказывает, что Hola Ltd. зарегистрирована в оффшоре, т.к. ее деятельность в Израиле считается незаконной.
PS
Вообще мне не столь важны деньги, сколько вероломное поведение организаторов и их работников.
Эти люди должны быть наказаны и опозорены.
Таким не место на Хабре. Надо уметь отвечать за свои слова.mark_ablov
11.01.2016 20:32> Публичный конкурс может быть закрытым, т.е не обязательно через СМИ
Вам пришло персональное приглашение на конкурс? Нет? Тогда это не закрытый конкурс.
> Поиск талантливых программистов это общественно полезная цель
Здесь монут быть разные точки зрения. Для меня это выглядит как рекрутинг, не несущий пользу обществу.
> Хотя что-то мне подсказывает, что Hola Ltd. зарегистрирована в оффшоре, т.к. ее деятельность в Израиле считается незаконной
Насколько я знаю, юр. лицо израильское. Поэтому они, кстати, у них и нет exit node в Израеле, чтобы а-та-та не получить.
> Вообще мне не столь важны деньги, сколько вероломное поведение организаторов и их работников
Хз. По мне так всё честно. В методике тестирования объективный косяк — обновляем методику и производим перетестирование решений. Кстати, в вышеупомянутых вами олимпиадах такое тоже практиковалось. Как в ACM так и в личных. Бывали пересмотры и через неделю после проведения.deniskreshikhin
11.01.2016 20:41Для закрытого конкурса персональное приглашение является не обязательным, в законе лишь об определенном круге лиц: «когда предложение принять участие в конкурсе направляется определенному кругу лиц по выбору организатора конкурса.»
Я лично получил сообщение о конкурсе на email, т.к. был подписан на хаб, как член хабра-сообщества. Т.к. вполне определенный круг лиц.
Здесь монут быть разные точки зрения. Для меня это выглядит как рекрутинг, не несущий пользу обществу.
Юридически, общественно полезная деятельность — любой, не противоречащий Конституции вид деятельности, связанный с удовлетворением личных и общественных потребностей.
Наем работников вполне себе общественно полезная деятельность.
Насколько я знаю, юр. лицо израильское. Поэтому они, кстати, у них и нет exit node в Израеле, чтобы а-та-та не получить.
Ок.
Хз. По мне так всё честно. В методике тестирования объективный косяк — обновляем методику и производим перетестирование решений. Кстати, в вышеупомянутых вами олимпиадах такое тоже практиковалось. Как в ACM так и в личных. Бывали пересмотры и через неделю после проведения.
В олимпиадах есть апелляция, она предусмотрена правилами олимпиад. После апелляции результаты можно изменить только в судебном порядке.
В этом конкурсе ничего такого не было предусмотрено. Если бы было, то я бы и не возмущался. Ну и не участвовал бы, прошел мимо.
zBit
11.01.2016 22:25+2Прошу обратить внимание организаторов на github.com/hola/challenge_mail_filter/pull/5
Добавлены тесты для проверки корректности, такие данные могут ввести пользователи, поэтому их нужно учитывать, следовательно тест на корректность станет более подробным, что может отсеять ещё несколько участников.
rmaksim
11.01.2016 23:57+3feldgendler, может тогда уж и участникам подкорректировать код, как минимум для прохождения корректности?
feldgendler
12.01.2016 18:04+1Мы уже приняли от участников две поправки к своим решениям. Естественно, исправленные версии будут участвовать вне конкурса.
degorov
12.01.2016 18:30+2Отправлял наиболее общее решение, решил не рисковать с более хитрыми вариантами. Зря :) Так я в шестом десятке, другие мои варианты позволили бы попасть в пятый. Авторы топовых решений, молодцы, конечно, моя подготовка в этой области сильно слабее — я на околопрофильной специальности учился, теперь есть стимул почитать подробней про DFA и т. п. Плюс на некоторые грабли, которые тут в комментариях фигурируют в том числе, я наступил сам и сам разобрался почему и зачем. В моей деятельности оптимизация скорости не является основной задачей, так что подобный опыт был интересен и полезен без сомнения.
А что касается пересмотра результатов, ну, как я понимаю, если задаться целью, то можно подобрать такой набор данных, который расставит участников в любом порядке. Утрирую, конечно, моё решение, например, вряд ли догонит топов как ни крути (если не брать совсем вырожденные наборы, пожалуй), но тем не менее. С другой стороны, я сильно сомневаюсь, что организаторам подобные манипуляции могут быть интересны, если честно.
Спасибо за конкурс, жду следующего!
whoozle
14.01.2016 10:20+6Добрый день, хабр.
Летучие обезьяны подняли мне веки, и я всё-таки решился написать здесь. Я создал тот самый баг на github, по итогам которого пересмотрели методику, и хочу чтобы кто-нибудь всё-таки попытался объяснить hola, что такое соревнование, раз уж у меня не получается.
Соревнование это не «о чувак, нам нужен фильтр для 100 сообщений». Соревнование — это гонка лучших умов в погоне за какой-то великой целью, за невозможным. Играть музыку на калькуляторе, писать десятикилобайтные RPG в браузере, процессить стотыщмиллионов сообщений миллиардом правил за секунду, вот что такое соревнование.
Цель в 100 (!!) рулесов, так отстаиваемая холой как реальная НИЧЕГО общего не имеет с соревнованиями вообще. Ну и это такая классная русская черта, прикрывацо лозунгами про ДНК и международный опыт (см. первый ответ), а потом в закрытом issue писать что «мы верим что больше 100 рулесов никакой пользователь не создаст».
Классно, ребята, но я бы никогда бы не учавствовал в таком, дело же совсем не в призах. По крайней мере, для меня.OLS
14.01.2016 10:55+3Золотые слова.
Я переписывался по e-mail с организатором конкурса, пытаясь донести идею увеличения набора правил до 1000 и значимо увеличить их алгоритмическую сложность, но увы…
github.com/OLS-RU/challenge_mail_filter
xytop
Денис молодец! Мне в голову вообще не шло как ещё оптимизировать можно все это кроме как избавиться от регулярок.
Я пытался объединить все фильтры в граф и проходить по нему, но это работало дольше решения с обычным поиском…
А Денис даже не заморачивался и оставил регулярки) без них было бы ещё чуть быстрее.
Вот моё решение: github.com/hola/challenge_mail_filter/blob/master/submissions/Vitaly%20Dyatlov/filter.js
deniskreshikhin
Спасибо, регулярки я решил трогать в последнюю очередь т.к. даже indexOf выполняется медленнее чем эквивалентное регулярное выражение.
Главный профит был от использования бинарных масок, что-то подобное как я понял использовали и остальные участники вверху таблицы.
Т.к. этот подход сработал, то я решил провернуть его еще раз, т.е. сделать маски для масок. Для этого правда пришлось рассчитывать среднюю собственную информацию на бит. (это в итоге составило 50% кода)
В итоге сначала вычисляется 4 битная маска, выбирается оптимальный список, потом уже идет поиск по полной маске, это видимо в итоге дало выигрыш на треть.
Т.к. первоначально я писал алгоритм на 1M+ сообщений, что бы иметь статистически значимые результаты, то потом столкнулся с тем, что на малых значениях все предварительные расчеты занимают очень много времени, пришлось добавить брутфорс и упрощенный алгоритм. Т.е. перед фильтрацией производится оценка количества писем и фильтров и выбирается наилучший алгоритм. Я прост боялся что будут данные типа 5000 писем и 100 фильтров.
Но мне повезло, хотя 100к сообщений это не 1М, но даже на этих значения получился хороший отрыв.
Я могу в принципе статью небольшую написать, если это интересно, т.к. сложно в одном комментарии все уписать, особенно про бинарную часть, т.к. я заюзал фишки из дискретной математики и теор. информации.
feldgendler
Мне отдельным пунктом понравилась вот эта адаптивность. Многие задавали вопросы об объёмах и характеристиках тестовых данных, но почти никому не пришло в голову выбирать из нескольких вариантов реализации в рантайме.
asavin
Если у вас найдётся время — напишите статью, было бы очень интересно прочитать.
Alex_At_Net
Очень интересно! Очень интересно именно в плане задействованных теорий.
ivann
Денис, спасибо за комментарий. Можете дать ссылку на описание алгоритмов масок или просто название этого класса алгоритмов? Они почему-то совсем мимо меня прошли.
deniskreshikhin
По своему принципу это маленькие фильтры Блума, где каждый бит сигнализирует о наличии буквы. В общем я этим вдохновился.
ru.wikipedia.org/wiki/Фильтр_Блума
OLS
Я тоже фильтр Блума использовал, только для триграмм и потом хешировал в пространство в 8000 значений