- Первое место: 1500 USD
- Второе место: 1000 USD
- Третье место: 500 USD
- Возможно, мы решим отметить чьё-то чрезвычайно оригинальное решение специальным призом в 350 USD.
- Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите такую же сумму, как и он.
Мы ищем талантливых программистов, поэтому авторы интересных решений будут приглашены на собеседования.
Правила
Некоторые из тех, кто помнит наши предыдущие конкурсы, были недовольны тем, что условия задач были сформулированы нечётко, и от участника требовалось «угадать», что мы имели в виду. На этот раз условие сформулировано предельно однозначно, а в распоряжении участников — эталонная реализация решения. Победит тот, чей код будет самым быстрым при условии прохождения тестов на корректность.
Условия конкурса на английском языке размещены на нашем сайте. Ниже — перевод на русский язык.
- Отправляйте решения на challengejs@hola.org.
- Решения принимаются до 25 декабря 2015, 23:59:59 UTC.
- Победители будут объявлены 8 января 2016.
- Можно отправлять решения многократно, но от каждого участника будет рассмотрено только самое последнее решение, отправленное до окончания срока приёма работ.
- Для тестирования мы будем использовать Node.js v5.0.0 (стабильная версия на момент публикации).
- Ваше решение должно состоять из единственного файла на JS.
- Решение должно быть на чистом JS. Если Вы предпочитаете CoffeeScript или подобные языки, необходимо оттранслировать решение в JS перед отправкой. Мы приветствуем (но не требуем) отправку оригинала вместе с результатом трансляции (но не вместо).
- Нельзя загружать никаких модулей, даже тех, что входят в стандартный комплект Node.js.
- Мы будем тестировать решения на корректность и производительность. Только решения, прошедшие тестирование на корректность, будут допущены к тестированию на производительность. Победит самое быстрое из корректных решений.
- Все работы участников, а также наши тесты на корректность и производительность, будут опубликованы при подведении итогов.
- Подводя итоги, мы опубликуем Ваше полное имя (или псевдоним, если Вы подпишетесь им), но не адрес электронной почты.
- Запрещается публикация участниками своих решений до окончания конкурса. Нарушители будут дисквалифицированы.
- Если условие задачи кажется Вам неоднозначным, проверьте своё понимание условия с помощью нашей эталонной реализации (см. ниже), вместо того, чтобы задавать вопросы по условию. Если Вы обнаружите, что поведение эталонной реализации противоречит условию, пожалуйста, сообщите нам.
Постановка задачи
Вы разрабатываете систему применения фильтров для почтовой системы. Вам нужно написать модуль для Node.js, экспортирующий одну функцию:
filter(messages, rules)
messages— это объект, ставящий в соответствие уникальным идентификаторам сообщений объекты с двумя свойствами:fromиto. Каждый такой объект описывает одно электронное письмо.rules— это массив объектов с тремя свойствами:from(необязательно),to(необязательно) иaction(обязательно). Каждый из этих объектов описывает одно правило фильтрования.
Все строковые значения во входных данных непустые и содержат только символы ASCII в диапазоне от
0x20 до 0x7F включительно.Считается, что письмо удовлетворяет правилу фильтрования, если оба его свойства
from и to удовлетворяют маскам, заданным в соответствующих свойствах правила. Маски регистрозависимые; символу * в маске удовлетворяет любое число (0 или более) любых символов, а символу ? — один любой символ. Если свойства from или to отсутствуют в правиле фильтрования, то в качестве значения по умолчанию используется *. Как следствие, если в правиле отсутствуют оба свойства from и to, то ему удовлетворяют все письма.К каждому письму необходимо применить все правила, которым оно удовлетворяет, в правильном порядке. Функция
filter должна вернуть объект, ставящий в соответствие идентификаторам сообщений массивы действий. Для каждого письма такой массив должен содержать значения свойств action всех правил, которым это письмо удовлетворяет, в порядке перечисления правил в массиве rules. Если письмо не удовлетворяет ни одному из правил, пустой массив для этого письма всё равно должен присутствовать в результате.Пример
Ниже приведён типичный пример корректного вызова функции
filter:filter({
msg1: {from: 'jack@example.com', to: 'jill@example.org'},
msg2: {from: 'noreply@spam.com', to: 'jill@example.org'},
msg3: {from: 'boss@work.com', to: 'jack@example.com'}
}, [
{from: '*@work.com', action: 'tag work'},
{from: '*@spam.com', action: 'tag spam'},
{from: 'jack@example.com', to: 'jill@example.org', action: 'folder jack'},
{to: 'jill@example.org', action: 'forward to jill@elsewhere.com'}
])
Правильная реализация
filter в этом случае вернёт следующее:{
msg1: ['folder jack', 'forward to jill@elsewhere.com'],
msg2: ['tag spam', 'forward to jill@elsewhere.com'],
msg3: ['tag work']
}
Эталонная реализация
Мы подготовили эталонную реализацию функции
filter по адресу http://hola.org/challenge_mail_filter/reference. Для заданных значений аргументов она выдаёт корректный результат. Эта реализация также строго проверяет корректность входных значений (от Вашего решения проверки входных данных не требуется). В спорных случаях вместо того, чтобы задавать нам вопросы по условию задачи, пользуйтесь эталонной реализацией. Если Вы подозреваете, что эталонная реализация выдаёт неверный ответ для тех или иных входных данных, пожалуйста, сообщите нам.Чтобы не допустить перегрузки нашего сервера, мы ограничили объёмы входных данных 10 правилами и 10 письмами. Ваше решение не должно иметь таких ограничений.
К эталонной реализации по упомянутому выше адресу можно делать HTTP-запросы методом POST с телом запроса типа
application/json. Тело должно представлять собой объект с двумя свойствами: messages и rules, — содержащими значения соответствующих аргументов функции filter. Тело ответа, также в формате JSON, будет содержать значение, которое функция должна вернуть. При недопустимых входных данных Вы получите ответ HTTP 400 с описанием ошибки в формате text/plain.Желаем удачи всем участникам!
Комментарии (137)
Antelle
13.11.2015 21:47+3Какие регулярки быстрее — компилируемые или нет? =)
> условие сформулировано предельно однозначно
> победит самое быстрое
Чтобы однозначно сформулировать, что значит быстрый, надо описать, как вы её хотите использовать:
1. 2-3 фильтра, 1М сообщений
2. 1M фильтров, 100 сообщений
3. повторное использование с большей вероятностью с теми же фильтрами или с разными
feldgendler
13.11.2015 22:27Повторного использования не будет, перед каждым запуском мы будем загружать Ваш модуль в свежей виртуальной машине. Сообщений будет на несколько порядков больше, чем фильтров, как это и бывает в реальных почтовых системах.
AxVPast
14.11.2015 01:44+3Человек как бы намекает на неудачную сигнатуру метода, который предложен в задании.
Логичнее было бы попросить седелать метод-фабрику, который принимает правила в качестве аргумента и возвращает функцию с единстенным аргументом — сообщением. Скорость работы подобного оптимизированного решения будет наибольшей.
Просто по требованиям сразу и сходу напрашивается решение на nools. Кстати они умеют компилироваться в 1 JS файл без лишних зависимостей. Никогда не смотрел, что оно там компилит, но уверен разобраться в коде будет трудно :). Понятное дело, что построение сети reto на каждом вызове функции решение не из самых быстрых, в результате половину решения будет составлять автодетект, что правила поменялись и нужно их перекомпилировать заново.
Поменяйте сигнатуру метода в задании, то что есть точно не в стиле NodeJS.feldgendler
14.11.2015 01:52-3Я понимаю, о чём Вы. Вы можете сделать все оптимизации, которые задумали, в рамках нынешнего условия. Обработайте правила как хотите и применяйте их затем к письмам. Писем будет много.
DYefimov
14.11.2015 12:56+6Я, может, додумываю, но мне так кажется, что вопрос в самом слове «много».
Что для Вас «много» — обычный нечищеный почтовый ящик, и функция фильтр будет вызываться на каждый такой ящик?
У меня в спам-ящике 6к сообщений…
Или разговор идет о строке (если конкатенировать все from в сумме) в сотни мегабайт?
Если второе — я бы с удовольствием поучастовал.
Как можно что-то оптимизировать, когда не заданы граничные (реальные) условия?
В общем, в моём понимании, «много» — это сферический конь в вакууме.
Дальше.
Данная задача на матчинг по паттерну больших объёмов данных.
Вы боритесь за скорость, но не говорите об ограничениях по памяти.
Как и всё в программировании, есть трейд-оф.
Потратили память на дерево, записали в него предварительно (при поступлении письма в базу) — тогда искомая функция будет быстрее некуда.
Оптимизировать вызов самой функции (т.е. строить леса внутри самой функции), есть… даже не знаю — зачем так тупо делать?
Ну или опять — недостаток исходной информации — может Вы хотите не тратить память? Почему не сказали?
Резюмируя.
Вы хотите найти человека, который умеет оптимизировать под v8?
Тогда условия задачи понятны.
Или Вы хотите решить реальную задачу?
Тогда Ваше заявление, что всё будет задано «конкретно» в этот раз — не прокатывает.
И пост скриптум.
Никогда не пишу комментарии в принципе, и я так «завёлся» потому, что у меня есть одинмогильничекалгоритмик на яваскрипте…
Пришлось писать велосипед используя мат-выкладки одного гения (заняло месяц понять, что он имелл в виду, т.к. реализации не было на тот момент в принципе...)
История простая.
Нужен был быстрый поиск с ошибками по большому объёму строковых данных (привет биоинформатика!)
Исходные данные:
1) полный японский словарь с полным переводом на английский (10Mb данных, что равно ~3 раза вся «Война и Мир» целиком)
2) работаем на клиенте в хроме
Задачи:
1) бытро искать
2) искать с ошибками
Первый результат был не ахти: дерево строилось (по искомым 10Mb) ~30 сек и весило 750Mb.
Обход же был впечатляющим, например:
1) найти все буквы «a» во всех переводах японских слов (давно было, не помню точную цифру, но больше полумиллиона результатов)
2) отранжировать результаты по появлению буквы в слове
3) отранжировать результаты по длинне слова
4) отрисовать первую сотню
= ~10ms (chrome, i3, 8Mb RAM)
Уточнение — хром падал, если забрать больше 500Mb памяти.
1я оптимизация
скорость построения 5-7сек, вес дерева 170Mb (тут можно еще много чего накрутить, но задачи не было)
2я оптимизация
Поскольку словарь статичный, то операции добавления и удаления были не нужны.
Всё сократилось до ~7Mb под дерево
3я оптимизация
Сам словарь в дереве задан неявно = исходные данные не нужны = 10Mb исходников -> ~7Mb дерева + быстрый поиск
Имея в виду всё что выше, что вы, блин, хотите сделать то?
Давайте тестанём эту историю?
Ну и пост пост скриптум.
1) этот алгоритм был «лучшее что я сделал за 25 лет стажа» (ну или может самое интересное)
2) имея этот опыт, очень захотелось поучаствовать (не ради копеек, конечно), но я действительно не понимаю, чего Вы хотите добитьсяfeldgendler
14.11.2015 12:59-1Писем будет на несколько порядков больше, чем правил. Это всё, что я могу пока сказать.
DYefimov
14.11.2015 13:30+9Задайте порядок в 10й системе того и другого, и все будут счастливы — это всё, что я хотел спросить.
AxVPast
14.11.2015 14:01+2Судя по условиям они ищут более менее (алгоритмически) толкового джуниора, который более менее разбирается в теории построения регулярных выражений и JavaScript.
Если у них всегда так ставят задачи в компании и такие сигнатуры методов от архитектора — то сомительно, что даже стоит пробовать участвовать в подобном конкурсе.
P.S. Предлагаю подумать над другим вопросом — можно ли в JS перехватить сам факт создания обоих массивов до того как вызовут функцию filter. То есть достичь ситуации когда выходящий массив будет построен до вызова саомй функции :))). Наверняка время меряют по вызову самой функции фильтр не считая накалдные расходы времени на загрузку структур данных в память.DYefimov
14.11.2015 14:05-5Вооооот!
Жму руку, мысль доехала, как я смотрю.
К сожалению, я немного набухался в данный момент — отвечу завтра на трезвую.DYefimov
14.11.2015 23:13+2Ладно, ладно — хватит минусовать.
По делу.
Своим постом выше, я пытался сказать, что (при нормальной реализации) затраты на «поддержание» данных намного меньше (место/время), чем то, что предложили нам в этом задании.
DYefimov
14.11.2015 14:23Да, замечу, что регулярки не панацея — на JS можно делать вещи намного быстрее регулярок. Была бы задача.
Drag13
13.11.2015 21:49+4Сторонние библиотеки использовать запрещено, все велосипеды своими руками. Правильно?
xytop
13.11.2015 22:11+3Хорошо было бы иметь страницу, куда можно было бы отправлять свое решение и оно бы подсчитывало скорость и добавляло это в какую-нибудь онлайн таблицу результатов. Это хорошо стимулирует на оптимизацию :)
NoorBall
13.11.2015 22:26+13Как выиграть 3000 USD?
1. Создаешь липовую почту.
2. Отправляешь себе приглашение на настояющую почту.
3. Участвуешь в конкурсе и выигрываешь 1500 USD.
4…
5. Profit!
dom1n1k
13.11.2015 23:07+19Имеет смысл переслать это письмо туда-обратно много раз, чтобы в каналах образовалась стоячая волна из долларов.
caveeagle
13.11.2015 23:19Предположим, что у тебя шанс выиграть 1:100, но ты знаешь человека, у которого такой шанс намного выше =))
xenohunter
16.11.2015 12:03+1Как выиграть 6000 USD?
1. Создаёшь три липовых ящика.
2. Отправляешь приглашения на три других ящика.
3. Пишешь для конкурса три крутых реализации.
4.…
5. Profit!
P.S. Вообще, я что-то не очень верю в эти конкурсы. Кажется, были уже прецеденты.
Lennotoecom
13.11.2015 23:23Пожалуйста подскажите если позволяют правила,
какие минимальные параметры теста нужно использовать при отладке,
количество messages, количество rules, максимальное время выполнения при таких условиях,
чтобы, так сказать, чувствовать где планка.
Спасибо.feldgendler
14.11.2015 00:56-1Ограничений на количество не должно быть, пока хватает памяти. Чтобы победить, нужно написать код, который работает быстрее, чем у других. Я не знаю заранее, быстрый ли будет код у Ваших конкурентов.
g1t5
14.11.2015 08:18+2пока хватает памяти
т.е. память ограничена? :)feldgendler
14.11.2015 11:49-2Память ограничена у любого физического компьютера, на котором мы могли бы запускать тесты. Мы не хотим, чтобы память была ограничивающим фактором, и постараемся сделать так, чтобы её всем хватило.
Aquahawk
13.11.2015 23:49-5Вам нужно написать модуль для Node.js
Ваше решение должно состоять из единственного файла на JS.
производительность
ionicman
13.11.2015 23:55+1Можно узнать, что не так?
Насколько я понимаю всю суть, файл будет типа:
function filter(...) {} exports.filter = filter;
И все.Aquahawk
14.11.2015 00:25-3Решение должно быть на чистом JS.
В случае если код планируется гонять на сервере, и он критичен к скорости, то гораздо производительнее будет сделать нативный модуль.
А в такой постановке устраивать игрища с js имхо странно.dom1n1k
14.11.2015 01:46+2Ясно же, что конкурс нужен для поиска JS-программистов, а не прикладного решения задачи фильтрации.
Alex_At_Net
14.11.2015 01:02+3Укажите, пожалуйста, жадность * в маске. А то непонятно, «aba» подходит "*a*b*" или нет.
Drag13
14.11.2015 01:14А можно список имейлов (хотя бы тысяч 50) что бы тесты погонять? Или это очень нагло и надо искать самому? :(
Sirion
14.11.2015 02:40М… я, конечно, не гений-алгоритмист, но чем эта задача отличается от простой задачи на проверку соответствия строки маске? Тем, что придётся повторить эту операцию от M*N до 2*M*N раз, где M — количество писем, а N — количество правил? Всё равно же придётся каждое с каждым проверять. Ну, мемоизацию разве что прикрутить, на случай одинаковых адресов.
mark_ablov
14.11.2015 08:00+1наверно, это задание скорее на знание того, как оптимизировать js-код для v8, а не про алгоритмическую оптимизацию.
feldgendler
14.11.2015 11:47Надеюсь, мы увидим наглядный ответ на этот вопрос при подведении итогов, когда все решения будут опубликованы.
dangreen
14.11.2015 07:49+1Странно что паттерн для адреса почты чувствителен к регистру, в эталонной реализации.
vintage
14.11.2015 10:32Не нашёл описания паттернов.
feldgendler
14.11.2015 11:47+1Маски регистрозависимые; символу * в маске удовлетворяет любое число (0 или более) любых символов, а символу? — один любой символ.
Lennotoecom
14.11.2015 13:59Пытаюсь протестироваться у вас на сайте по ссылке через ajax,
все время получаю ошибку
Response to preflight request doesn't pass access control check: No 'Access-Control-Allow-Origin' header is present on the requested resource.
: ( простите за нубский вопросfeldgendler
14.11.2015 14:02Я сейчас проверил, эталонная реализация работает. Проверяйте, как именно Вы делаете запрос.
dangreen
14.11.2015 16:37Делайте запрос с помощью curl или wget или еще чего, из браузера у вас это не получится.
Drag13
14.11.2015 17:19Есть предложение
Брать не последний лучший результат, а лучший результат последних двух.
Причина в том, что частота встречаемости почтовых адресов не известна. Или дать больше информации.
xytop
14.11.2015 18:52+3Вопрос по поводу написания модуля:
Вам нужно написать модуль для Node.js, экспортирующий одну функцию
Это значит
module.exports = function(m, r){ /* .. */ }
или
exports.filter = function(m, r){ /* .. */ }
?
В первом варианте экспортируется функция, а во втором объект с этой функцией. Как правильно сделать?feldgendler
15.11.2015 04:31-1Второе.
Aquahawk
15.11.2015 10:37+3А может вы это в правила внесёте официально? Ибо уже наблюдаем людей введённых в заблуждение(см выше). Я всё ещё думаю участвовать или нет, и честно говоря, при интересной задаче постановка конкурса не блещет качеством, мягко говоря. Если хотите научиться конкурсы нормально проводить, почитайте как вот тут делают: russianaicup.ru
feldgendler
15.11.2015 23:48После некоторого размышления мы решили принимать решения, написанные и так, и эдак (касательно способа экспорта функции), поскольку нет никаких проблем научить нашу тестилку понимать оба варианта.
zBit
15.11.2015 11:42+3Вам нужно написать модуль для Node.js, экспортирующий одну функцию
Модуль, экспортирующий одну функцию, а не модуль, экспортирующий объект с одним методом! В задании одно, в комментариях другое. Я понял это какmodule.exports = function() {};feldgendler
15.11.2015 23:49Мы уже решили принимать модули, сделанные и так, и эдак, раз возникли разночтения.
Lennotoecom
14.11.2015 21:03Как работают эталонные регэкспы:
'jack@example.com' ?jack@example.com not match 'jack@example.com' *jack@example.com match 'jack@example.com' ?ack@example.com match 'jack@example.com' *?k@example.com match 'jack@example.com' *a*@example.com match 'jack@example.com' *a*a* matchkazmiruk
14.11.2015 21:19? это не 0 или 1 символ, а строго 1 символ, поэтому первая строка и не подходит
zBit
14.11.2015 23:23+2Задание кажется каким-то не полным. Мне кажется не хватает тестовых данных и описания метода замера производительности.
arusakov
15.11.2015 00:36+1Поддерживаю, опишите хотя бы в общих чертах то, как будет производится замер. А лучше выложите ваш эталонный код для замера в opensource.
zBit
15.11.2015 01:50Если выложить реализацию в паблик, то остаётся только оптимизировать код, это несколько упрощает задачу. Но описать как будет определяться «самая быстрая реализация» было бы не лишним. Какие критерии будут учитываться (время выполнения, потребление памяти, количество операций, визуальный осмотр ващего гуру JS или что-нибудь ещё)?
arusakov
15.11.2015 02:53Не эталонную реализацию, а некоторое подобие фреймворка, с помощью которого будут производиться замеры производительности. Я это имел в виду.
feldgendler
15.11.2015 04:32+2Мы не хотим оптимизации под бенчмарк. Скажу только, что характеристики тестовых данных будут напоминать реалии электронной почты.
zBit
15.11.2015 02:41+1Все строковые значения во входных данных непустые и содержат только символы ASCII в диапазоне от 0x20 до 0x7F включительно.
www.bluesock.org/~willg/dev/ascii.html
0x7F — это же del…
И вы уверены, что прямо во всех строковых значениях во входных данных (в т.ч. и в адресах почтовых ящиков) можно использовать все эти символы?
И как быть с ситуацией когда нужно в правилах указать наличие символа * как этого символа, а не как эквивалент любого количества любых символов? Если такие случаи надо учитывать, то реализация будет сложнее и как следствие медленнее.
Вывод: нужно выложить «тесты на корректность», которые вы будете гонять. Вы облегчите этим себе жизнь. Или хотя бы пачку входных данных, которые используются в «тестах на корректность».Lennotoecom
15.11.2015 03:32Да, действительно, эталонная проверочная балалайка на сайте (при использовании всех символов),
при попытке поиска строки «a*b», при входных значениях «a*b» и «abb» естесственно отбирает оба.
Так как "*" является абсолютно легитимным символом для адреса по условию задачи.
Так что вы определили неисправность в их алгоритме и проверочной балалайке.
похоже грядет апдейт по возможным символам в адресе до формы вида [.-@0-9a-zA-Z]feldgendler
15.11.2015 04:37Никакой неисправности. Так и должно быть. Ваш код должен вести себя так же.
feldgendler
15.11.2015 04:36В данном случае неважно, что можно, а что нельзя использовать в реальной электронной почте. Ваша функция должна быть готова к появлению в том числе символа 0x7F.
Символы * и? как таковые невозможно задать в маске. Такой вот несовершенный язык для фильтров.
Если Вы сомневаетесь в том, допустимы ли те или иные исходные данные, воспользуйтесь эталонной реализацией. Если она отвечает 200 OK, то Ваш код должен быть готов к таким значениям аргументов, и должен выдавать то, что вернула эталонная реализация.u1d
15.11.2015 10:29+1А если эталонная реализация возвращает 502 или 504 на валидных по правилам аргументах, то на тесте (проверке корректности/производительности) таких аргументов точно не будет дано?
feldgendler
15.11.2015 23:46Это означает, что у нас проблемы на сервере, попробуйте ещё раз через некоторое время. Если проблемы продолжаются, пришлите мне входные данные.
gandjustas
15.11.2015 03:37Пустая строка в правилах from и to эквивалентна отсутствию параметра или обязательно падать при этом значении?
feldgendler
15.11.2015 04:40Пустая строка недопустима и поэтому в наших тестах на корректность и производительность не попадётся. Неважно, падает ли Ваш код при таких входных данных, потому что мы это тестировать не будем.
dangreen
15.11.2015 10:40Но в эталонной реализации пустые строки отлавливаются. То есть нам их ловить не обязательно? Так же эталонная реализация проверяет объекты на посторонние свойства, но в правилах об этом ничего, то есть и это нам можно не реализовывать?
feldgendler
15.11.2015 23:50В условии сказано:
Эта [эталонная] реализация также строго проверяет корректность входных значений (от Вашего решения проверки входных данных не требуется).
ionicman
15.11.2015 10:58+6Господа, я вот искренне не понимаю негодующих.
Да, ко всему можно докопаться, тем более к конкурсу конторы, у которой совсем другой основной профиль. Да, никаких гарантий и все такое.
Но ведь никто не заставляет? Ну не нравится — можно просто пройти мимо-же, нет?
Мне вот тупо было интересно отвлечься от рутины, вспомнить некоторые вещи, о которых не дают задуматься рабочие будни.
Выиграю я или нет — главное я провел пару часов интересно и напрягая мозг. Я написал так, как понял и это меня вполне устраивает. ИМХО вполне нормально и понятно изложено, все остальное можно проверить на эталоне.
Что за снобизм и перфекционизм?
Иногда конкурс тем и интересен, что некоторое надо додумывать. Мало того, умолчание можно использовать в свою пользу (тут вон даже намеки были :)).
Мне здесь тоже кое-что не нравится (отсутствие пакетов эталонных данных и данные о том, что модуль хотя-бы нормально запустился на тестовом стэнде — первое решается элементарно — я написал генератор и успокоился, ну а на второе — на все воля Аллаха, что делать-то :)), но это не повод наезжать на организаторов и уж тем более не повод не поучаствовать. Нормальная такая разминка для мозга.vintage
15.11.2015 11:20Да и задача всё же не очень интересная. Вообще, по результатам конкурса было бы интересно почитать аналитику — кто как решал и какой профит от этого получил. Позапрошлая задача с сериализацией моментов, например, привела в итоге к написанию полезной библиотеки http://habrahabr.ru/post/263041/ где используется наиболее быстрая реализация без использования eval. C eval и код не красивый получается и доступен он не во всех окружениях, зато позволяет заинлайнить весь алгоритм в одну функцию и быстро применять её к данным.
DYefimov
15.11.2015 12:28Да этот конкус выйденого яйца не стоит.
Об этом и весь спич.
Пойди туда не зная куда…
Я, может, категоричен, но хочется самому приложиться.
Но есть одно «но»: в реальных системах не оптимизируют функции, а оптимизируют подход.
Назвали бы свой конкурс «оптимизация под v8», ни у кого бы вопросов не возникло.
topa
15.11.2015 11:47+8Если кому лень собирать данные для замеров производительности собственной реализации, я хочу поделиться своими:
— примерно 50 тыс сообщений, взял первую попавшуюся базу адресов из поисковика и наугад соединил их в пары. Имена у них тривиальные, типа msg15.
— примерно 500 правил, которые были сделаны из случайно выбранных электронных адресов путём замены нескольких символов на * или?
Сохранена разница в 2 порядка между числом сообщений и числом правил, как и указывалось выше в коментах.
Правила фильтрации в этих данных бестолковые, составленные случайным образом. Правильного ответа (от референсной модели) на эти данные нет, я готовил их исключительно для замеров производительности. При желании можете сами их собрать.zBit
15.11.2015 12:23+1Спасибо!
Жаль, что эталонная реализация может принимать только 10 сообщений, разницу между сообщениями и правилами как в реальности (несколько порядоков) они не учли=(feldgendler
15.11.2015 23:53Эталонная реализация предназначена только для проверки корректности, для чего лимита в 10 сообщений даже многовато.
cL1Nk3r
15.11.2015 13:00У кого какие результаты на этих данных?
Моя самая элементарная реализация (просто чтобы работало) показала 0.26 ops/sec используя benchmark.jstopa
15.11.2015 13:27Сравнивать на разных машинах несколько некорректно и весьма нерепрезентативно)
Но это даёт хоть какой-то уровень, на который можно ориентироваться.
На моем Core i5-2450M 2.5GHz первая пришедшая на ум реализация выполняет обработку примерно за 1,4 сек. (0.72 ops/sec по замерам с benchmark.js)
xytop
15.11.2015 13:12мой macpro за 30 секунд все обработал и ответ вернул. У кого еще какие результаты?
KingOfNothing
15.11.2015 14:49+3У меня тут 100000/1000 www.dropbox.com/s/5lu2gdzn68xecx0/test1.json?dl=0
xytop
15.11.2015 15:05сколько обрабатывается по времени, и какое железо?
KingOfNothing
15.11.2015 15:19Intel Core i7-4710HQ CPU @ 2.50GHz ? 8
9s, node 4.2.2xytop
15.11.2015 15:22у меня на 5й ноде за 14.5s
Проц тоже i7 (2 GHz Intel Core i7) но мобильный и 4 ядра…
Надо придумать как организовать централизованное тестирование и при этом не слить свой код )
OLS
15.11.2015 21:22Нужно просто создать эталонную нагрузку, запустить ее на своем ПК для сравнения коэффициента быстродействия с чужими, а потом при тестировании на своем компьютере делить/умножать на выясненный коэффициент.
gandjustas
15.11.2015 18:24Набор неадекватный, слишком много правил "*". Я не думаю что тестовый набор правил будет так выглядеть.
OLS
15.11.2015 21:30Более того я бы предположил, что "*" будут закрываться целые домены либо вся структура поддоменов
zBit
15.11.2015 21:53А с какими параметрами нода запускаться будет при тестировании производительности?
OLS
16.11.2015 00:59+4Уважаемые организаторы, к вопросу онлайн-рейтинга:
как мне представляется, основные дополнительные затруднения с его организацией лежат в области необходимости регистрации/анонимности и т.п. участников.
Позвольте мне предложить минимально затратный для Вас и при этом полностью анонимный вариант:
Публикуйте на сайте в виде статичного файла почасовой лог результатов тестирования с формализованным именем 'stat-YYYY-MM-DD-HH.csv' в формате CSV со столбцами: «DATETIME, SOURCEMD5, RESULT», т.е. наподобие:
2015-11-16 00:55:02, 0df4ac854afd6aadfa77afcd7ac31, 143.77
2015-11-16 00:55:07, 8fdac7ad5105fa77eec77bdc6562, 112.53
…
Каждый участник соревнования, отправивший очередной файл, может посчитать его MD5 и найти себя в логе. При этом данные получаются полностью анонимными.
А особо интересующиеся, я уверен, через несколько часов сформируют и турнирную таблицу, обновляющуюся и отсортированную по убыванию длительности исполнения кода.gandjustas
16.11.2015 13:24Толку от такой таблицы не будет без эталонных тестов. Причем тестов на корректность, а не на скорость.
gandjustas
16.11.2015 13:26+1Товарищи организаторы,
1) Дайте плз тесты на корректность, включая обработку ошибок
2) Уточните по входным данным: будут ли from и to в сообщениях всегда содержать символ @? будут ли правила, хотябы в большинстве случаев, содержать @?feldgendler
16.11.2015 13:34+2В условии сказано, что Ваша реализация не обязана проверять ошибки. Мы не будем тестировать её на некорректных входных данных.
В остальном задание достаточно специфицированно для того, чтобы сделать его правильно. На олимпиадах по программированию типа ACM тесты тоже не дают.
Никаких гарантий насчёт символа @ нет. С точки зрения этой задачи в этом символе нет ничего особенного, может встретиться несколько раз, может ни одного.
Ag47
18.11.2015 00:53+2На олимпиадах по программированию типа ACM тесты тоже не дают.
Да, но результат проверки на этих самых тестах виден сразу, хоть сами тесты и не известны, а не в самом конце, когда уже ничего не исправишь. Так то скрывать тесты и проверку провести в самом конце все же не самая лучшая затея по отношению к участникам. Ждать часа X и обнаружить, что в погоне за быстродействием, ты в скрипте не учел какой-то странный случай, не очень хочется.
P.S.
Конкурс отличный, жалею что предыдущие ваши пропустил, отличная разрядка.feldgendler
18.11.2015 03:38Здесь в комментариях уже начали обмениваться тестами. Мне кажется, это отличная идея.
Aquahawk
16.11.2015 15:46Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите такую же сумму, как и он.
Выше в комментариях уже заметили, но я уточню отдельно. Если 10 человек шлют кому-то ссылку на этот конкурс, поставив ваш адрес в CC, и этот человек займёт призовое место, то каждый из этих 10 получит столько же?
topa
16.11.2015 20:24+4По поводу тестирования корректности функции. Предлагаю немного скооперироваться и подобрать некоторые тесты, которые должна проходить разработанная функция.
Несколько тестов я разместил на гитхабе. Буду рад, если кто-нибудь найдет и добавит туда еще хитрые комбинации входных данных.feldgendler
16.11.2015 20:26Интересная инициатива! Хотя правила и запрещают публикацию своего решения до окончания соревнования, в них ничего не сказано о других видах сотрудничества.
Ag47
18.11.2015 01:48+1Проясните, пожалуйста, несколько моментов:
1. Использование стороннего кода
- Ваше решение должно состоять из единственного файла на JS.
- Нельзя загружать никаких модулей, даже тех, что входят в стандартный комплект Node.js.
Так то, если вставить код нужных модулей и библиотек в свой файл, кроме нативных естественно, условия формально выполнятся. Уж, чтобы уж совсем было не подкопаться, то лицензии по использованию это разрешают допустим. Можете как-то более развенуто свою позицию описать, пожалуйста.
2. Можете все-таки как-то определить ограничение по памяти. В погоне за быстродействием понятно, что будет увеличиваться расход памяти, так что коль скоро она ограничена, её количество достаточно важно, особенно в рамках разговоров, что «писем будет много».
Допустим 8/16/etc Гб, чтобы можно было протестировать как-то самим, а то ограничений по памяти нет в теории, а на практике у вас будет какое-то вполне конкретное.
Кроме того у самой ноды, если верить github.com/nodejs/node/wiki/Frequently-Asked-Questions на процесс оно есть
By default, --max_old_space_size (which controls the upper limit of the V8 heap) is ~1.5GB.
Вы будете этот лимит менять? В предыдущих версиях ноды, притом, он менялся не до бесконечности, в новой вроде починили.
3. В связи с предыдущим вопросом опять же, не могли бы вы как-то очертить, хотя бы порядок количества сообщений и фильтров. Например, 10K или даже 100K фильтров одно, 10M уже совсем другое, а если больше, то, вообще, надо думать. Память будет как-то ограничена, надо как-то представлять сколько вообще места у нас, может там места на эти самые письма и фильтры только и есть=).
4. Просто на всякий случай, точно ли ваши тесты на корректность будут проверять, что actions у сообщений перечислены «в порядке перечисления правил в массиве rules»? У вас это упоминается, но просто, может они все-таки коммутативны=)feldgendler
18.11.2015 03:461. Пожалуйста, вставляйте код сторонних библиотек, если это не нарушает их лицензии. Запрет на require обеспечивает, что решения не будут пытаться доступаться к файлам, сети и вообще нести в себе сюрпризы. Мы будем запускать его в виртуальной машине Node.js, где require вообще не будет.
2 и 3. Если надо, лимит по памяти будем менять. Мы ещё не определились с размером входных данных. Планируем выбрать такой размер, на котором все присланные программы будут вписываться в имеющуюся в нашем распоряжении память, кроме, разве что, намеренно пытающихся съесть всю память. В общем, считайте, что у Вас хватит памяти на любые разумные предвычисления, кэши и т.п.
4. Да, порядок действий важен.
degorov
19.11.2015 13:08Тут уже спрашивали, но всё же повторюсь. Не могли бы Вы озвучить характеристики набора? Просто по сути задачи, где повторяющихся наборов from-to половина, и где таких повторений (практически) нет — это РАЗНЫЕ задачи. Если неизвестны характеристики набора входных данных, то победа сводится к УГАДЫВАНИЮ характеристик Вашего конкретного тестового набора, а не к построению самого хитрого алгоритма ;)
Та же мемоизация, которую тут упоминали, она в любом случае не может быть бесплатной, как ты её не оптимизируй. И решение с мемоизацией на наборе полностью различных писем при прочих равных всегда проиграет решению, где её нет. И это касается любых других возможных оптимизаций.
Вы говорили, что «характеристики тестовых данных будут напоминать реалии электронной почты», но это очень расплывчатое понятие. Скажем, на наборе «У вас же, наверное, в почтовом ящике много писем.» из моего ящика вариант с тупейшей мемоизацией выиграет у решения, где сама функция проверки паттерна намного более эффективная, но мемоизации нет. А на наборах рандомных данных, которые здесь в комментариях есть мемоизация и вообще любые попытки предоптимизации только вредны — достаточно просто написать самую быструю функцию проверки паттерна.
Разные задачи — разные решения…feldgendler
19.11.2015 13:11-2Набор будет весьма похож на содержимое почтового ящика типичного пользователя.
zBit
19.11.2015 14:55У всех почтовый ящик выглядит по-разному. Кто-то получает тоннами спам с разных адресов, а кто-то очень активно переписывается с несколькими людьми и не получает спам.
ionicman
19.11.2015 15:13+1Если не придираться, и чуток подумать — тестовый генератор пишется за 3 минуты.
По-моему организатор конкурса непрозрачно намекнул в самом начале — СТАНДАРТНЫЙ почтовый ящик. ОБЫЧНЫЙ, не от техподдержки или кого-то еще. Так сложно распределение посчитать?
Дайте тестовые данные и скажите какое распределение...
Так может сразу алгоритм дать? :) А тогда где головой-то думать?
Поэкспериментировать чуток — и все понятно будет. Я вот сегодня время сократил в два раза у алгоритма, прикинув статистическое распределение. А я не могу про себя сказать, что мегамозг :D
P.S. Пока Вы тут жалуетесь, народ пишет и молчит — наверное это правильно?
Из цикла "Пока Вы спите, Ваш враг качается!" :))degorov
19.11.2015 15:23Да, и алгоритмов той же сортировки придумано уже десятки. А надо было просто прикинуть СТАНДАРТНЫЙ набор данных, ну ОБЫЧНЫЙ и посчитать распределение…
>Я вот сегодня время сократил в два раза у алгоритма, прикинув статистическое распределение.
А у меня есть два варианта скрипта, один из которых быстрей на этом наборе данных, а другой быстрей на вот этом. И я точно могу написать третий вариант, который будет быстрей на моём личном почтовом ящике…
zBit
19.11.2015 15:54Я всего лишь отметил, что никто не знает с вероятностью 100% о том как выглядит почтовый ящик типичного пользователя :) И я не считаю свой ящик — ящиком типичного пользователя :)
У меня скрипт с тестовыми данными выложенными выше (http://habrahabr.ru/company/hola/blog/270847/#comment_8654795) выполняется за чуть больше секунды на i5-4570 (3.2GHz).
Хотя я думал над тем, что если знать как будет выглядеть тестовый набор данных, то можно будет ещё что-нибудь придумать и оптимизировать алгоритм ещё лучше.ionicman
19.11.2015 15:58Оптимизировать под определенные данные, если данные могут быть другими — всегда плохо.
Никто не знает, но Вы вольны предположить исходя из статистики, и написать максимально универсальное решение, либо решение, анализирующее на ходу статистику и переключающееся на максимально более эффективный вариант.
Сколько секунд у Вас выполняется алгоритм — цифра абсолютно бесполезная, ибо неизвестна система, устройства на шине, что крутится в фоне и т.д.zBit
19.11.2015 16:04Согласен, цифра бесполезная:) Забыл затолкать всё что после первого абзаца в спойлер…
Была бы ещё эта статистика, мне известна… Мне кажется, что если какой-то анализ входных данных проводить, то можно получить вариант медленнее, чем один алгоритм ориентированный на универсальный набор данных. Надо будет попробовать:)
feldgendler
19.11.2015 16:31Я бы плюсанул, если бы мне карму не слили. Не нравятся людям мои конкурсы, очевидно.
При разработке реальной почтовой системы разработчикам тоже не известны заранее точные характеристики почты, которая будет у пользователей. При этом какую-то стратегию оптимизации выбирать приходится, ходя для кого-то из пользователей, например, для работника техподдержки, это может оказаться пессимизацией.zBit
19.11.2015 16:56Я не эксперт, но карму слили скорее всего из-за плохой организации. Надо было запилить на сайте форму куда можно загрузить скрипт и узнать свой результат, плюс посмотреть предварительно на каком месте находится загруженное решение. Сделать ограничение по несколько загрузок в день от каждого пользователя, конкурс был бы прозрачнее и было бы счастье. Я понимаю, что слишком многого хочу, это всего лишь моё представление того как я бы организовал подобного рода мероприятие. С таким подходом было бы меньше вопросов и возмущений, наверняка.
ionicman
19.11.2015 17:15+1Вот представьте себе — Вы работает в некой фирме девелопом (например).
Каким-то образом в фирме решают что есть деньги на конкурс (for fun, сверху или как-нибудь еще, теоретически это может быть и попытка хэдхантинга).
У Вас есть деньги на призовой фонд и Вам надо провести конкурс. Но Вы не спец по этому делу, мало того — Ваши основные обязанности тоже никуда не делись.
Конечно, если Вы уровнем mailru/яши — можно запилить команду, которая все что Вы написали забацает. При этом прожрет денег чуть ли не больше, чем выделено на конкурс + это время — мало того, даже в больших компаниях тоже все не гладко — вспомните конкурс на хабре от мейлру, где победили боты.
Есть вариант сделать это все на энтузиазме — но тут вопрос уже конкретно в компании и человеке. Да и редко сейчас он встречается.
Вот Вы, например, посвятите свое нерабочее время своей компании бесплатно? :)
Плюс у Вас нет опыта проведения данных мероприятий — Вы даже можете и не знать всего этого — просто потому что не сталкивались.
Обычно на вопрос "А давай ты проведешь конкурс у нас на фирме, на него выделили деньги!" большинство нормальных людей, анализируя размер предстоящего геморроя ответят "А давай нет!" :)
Поэтому, ИМХО, надо радоваться, что конкурс вообще состоялся и в нем можно принять участие. Для меня — это самое главное.
А придраться можно до всего, как и хаять.
Я, если честно, вообще все это нытье не понимаю. Если я вижу, что меня что-то не устраивает, чего можно избежать просто пройдя мимо — я пройду мимо. И уж никак не буду кидаться на баррикады «В интернете опять кто-то не прав».
Мира Вам, господа! Относитесь ко всему легче и добрее.
zBit
19.11.2015 17:42+1Я всего лишь написал как я бы сделал :) Я перфекционист, поэтому я не буду объявлять о конкурсе пока не подготовлю всё для него и не буду уверен, что это будет удобно.
Согласитесь, это соревнование и как в любом соревновании надо примерно понимать где ты находишься. Когда спортсмены соревнуются в беге или прыжках в длину/высоту/глубину, устраивают гонки и ещё много в чём соревнуются, то они знают примерно где они находятся в данный момент времени в турнирной таблице (за исключением тех видов спорта где есть очередь и вы не первый кандидат). Вы бы пошли на соревнования по бегу если бы каждого из участников загоняли на стадион по очереди и заставляли бегать на время, при этом никто кроме судьи не видит и не знает о результатах и сообщает о том кто выиграл через неделю, например? Я бы не пошёл, т.к. в такой реализации нет прозрачности, нет уверенности в том, что всё проходит честно. Я думаю вы согласитесь, что намного приятнее бегать всем вместе, чтобы знать когда и на сколько нужно поднажать, чтобы вырваться вперёд.
Только не пишите о том, что я ною или придираюсь! :) Я тоже рад, что конкурс вообще есть, но был бы ещё рад, если бы его организовали лучшим образом. Я всего лишь пишу о том как сделал бы я на их месте и это не значит, что у текущей реализации конкурса всё плохо, может у организаторов другое представление о соревнованиях, которым они не делятся с участниками конкурса (и всем остальным миром), отсюда и негодование/непонимание/возмущения и т.п.
В данном случае получается соревнование с самим собой, целью которой является написать реализацию, которая работает быстрее предыдущей твоей же реализации и нет знания о том, что можно сделать ещё быстрее или о том, что ты впереди планеты всей и никто не реализовал более быстрый алгоритм, чем ты.
Тем более можно было взять, например, уменьшить призы на 100 баксов и на разницу нанять фрилансера, который бы сделал страничку и сделал бы серверную часть, которая делала бы замеры и хранила результаты. Я уверен, что обрабатывать входящие сообщения будет дороже, чем автоматизировать это и любоваться графиками.
vintage
19.11.2015 17:35Ну, после сливания кармы хорошей организации конкурса тем более ждать не стоит как и новых статей :-)
gwer
19.11.2015 14:07Ну а чего вы на рандомные данные смотрите, когда сказано, что будет типичное содержимое почтового ящика?
Типичное содержимое в моем понимании — это однозначное повторение в каждом письме одного из немногочисленных адресов пользователя и нередкое повторение прочих адресов: уведомления от соцсетей, сайтов, переписки и с кем-либо. Хотя, конечно, есть там и адреса, появляющиеся единожды, те же спамеры могут этим разбавить содержимое.degorov
19.11.2015 14:21А в моём понимании какой-нибудь работник службы техподдержки тоже является типичным пользователем и у него/неё там будет адресов тонны всяких разных и куча уникальных писем. Свой личный ящик я уже давно распарсил и да, он совпадает с Вашим пониманием, но вопрос о его ТИПИЧНОСТИ лично для меня останется открытым по крайней мере до тех пор, пока не будет проведён статистически значимый анализ нужного количества (сотен, тысяч, миллионов?) содержимого других почтовых ящиков людей с разной половой принадлежностью, профессией, возрастом, вероисповеданием итд итп :)
С моей точки зрения было бы более правильно вообще не скрывать тестовый набор, но явно запретить правилами указание в коде любых констант хоть строковых, хоть числовых, направленных на оптимизацию под бенчмарк. А попробовать пореализовывать самому разные варианты оптимизаций и повключать/поотключать их для получения лучшего результата, как по мне, так это как раз весьма спортивно и интересно. Любые задачи в реальной работе программиста — это всегда оптимизация под бенчмарк в этом смысле.
При текущей постановке задачи я, вероятно, буду пытаться отрабатывать максимально общий случай и не буду рисковать подцеплять более хитрые штуки в расчёте на то, что тестовый набор будет соответствовать Вашему пониманию в том числе, ибо в общем случае они всегда вредны, как ни крути.gwer
19.11.2015 14:30-1Запрещать использование тех же констант — затея какая-то нелепая. Проще выложить предварительный тестовый набор, а итоги подводить на аналогичном: другие ящики, другие маски, но схожие характеристики.
degorov
19.11.2015 14:35Констант в том ключе, чтобы в коде не было предварительно рассчитанных значений. Так как исходники всех решений открыты — в этом ничего нелепого я не вижу.
Или разрешить присылать несколько вариантов скриптов, в зачёт идёт лучший результат, а не последний. Так как тестирование всё равно автоматическое — не вижу в этом вообще никакой проблемы.
degorov
19.11.2015 14:40Аналогичный по характеристикам набор — тоже вполне себе вариант при условии повторения ВСЕХ характеристик, а они совсем не ограничиваются повторением в письмах. Я бы даже сказал, что создание двух действительно схожих наборов является более сложной задачей, чем собственно, все те решения, что мы тут все изобретаем. Потому что для этого нужно знать все возможные оптимизации и подогнать/не подогнать под них всех одинаково :)
kumekay
при отправке пустого POST запроса с Content-Type: application/json на hola.org/challenge_mail_filter/reference в ответ 502 Bad Gateway
feldgendler
В теле запроса должен быть корректный JSON.
vintage
И тем не менее, на неверный запрос сервер должен возвращать 4** ошибку, а не 5**.
feldgendler
Мы парсим JSON на уровне express middleware, и было неудобно для этого одного урла делать исключение. Вам же это не сильно мешает пользоваться эталонной реализацией? Ну вот и славно.
Aquahawk
Какие правила ещё реализовать было неудобно? Может и выплаты неудобно будет делать?