Компания
58,90
рейтинг
8 января в 17:40

Разработка → Итоги конкурса по программированию на JS: Почтовые фильтры

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

Спасибо всем участникам нашего последнего конкурса по программированию!

Мы получили 408 решений от 237 различных участников (в конкурсе участвует только одно, последнее из решений от каждого участника, и мы публикуем именно последние варианты). Кроме того, 7 решений было отправлено нам либо после окончания срока приёма работ, либо сотрудниками Hola, и мы рассмотрели их вне конкурса.

64 решения, или 16% от общего числа, были отправлены в течение последних суток до окончания срока. Из них 15 были отправлены в течение последнего часа, а самое последнее «проскочило» за 34 секунды до дедлайна.

Тесты на корректность прошли 114 программ, что составляет 48% от числа протестированных.

Самое короткое решение уместилось ровно в 666 байт, а самое длинное растянулось на 90274 байт.

Один из участников был дисквалифицирован за попытку обмануть тестовую систему. Забавно, что его результат всё равно уступил честному результату победителя конкурса.

Двое участников разделили второе место, так как производительность их решений оказалась одинаковой в пределах точности измерения. В связи с этим мы увеличили призовой фонд на $500 и наградили каждого из них призом по $750.

Поздравляем победителей:

  1. Денис Крешихин — приз 1500 USD.
  2. Илья Макаров и Юрий Килочек — призы по 750 USD.
  3. Сергей Голуб — приз 500 USD.

Дополнительно мы решили наградить автора самого короткого корректного решения. Специальный приз в 350 USD получает Надав Ивги.

Полная таблица результатов и подробности о тестировании — в репозитории на GitHub.

Мы постараемся учесть многочисленные замечания участников при подготовке следующего конкурса.
Автор: @feldgendler
Hola
рейтинг 58,90

Комментарии (121)

  • +6
    Денис молодец! Мне в голову вообще не шло как ещё оптимизировать можно все это кроме как избавиться от регулярок.
    Я пытался объединить все фильтры в граф и проходить по нему, но это работало дольше решения с обычным поиском…
    А Денис даже не заморачивался и оставил регулярки) без них было бы ещё чуть быстрее.
    Вот моё решение: github.com/hola/challenge_mail_filter/blob/master/submissions/Vitaly%20Dyatlov/filter.js
    • +22
      Спасибо, регулярки я решил трогать в последнюю очередь т.к. даже indexOf выполняется медленнее чем эквивалентное регулярное выражение.
      Главный профит был от использования бинарных масок, что-то подобное как я понял использовали и остальные участники вверху таблицы.

      Т.к. этот подход сработал, то я решил провернуть его еще раз, т.е. сделать маски для масок. Для этого правда пришлось рассчитывать среднюю собственную информацию на бит. (это в итоге составило 50% кода)

      В итоге сначала вычисляется 4 битная маска, выбирается оптимальный список, потом уже идет поиск по полной маске, это видимо в итоге дало выигрыш на треть.

      Т.к. первоначально я писал алгоритм на 1M+ сообщений, что бы иметь статистически значимые результаты, то потом столкнулся с тем, что на малых значениях все предварительные расчеты занимают очень много времени, пришлось добавить брутфорс и упрощенный алгоритм. Т.е. перед фильтрацией производится оценка количества писем и фильтров и выбирается наилучший алгоритм. Я прост боялся что будут данные типа 5000 писем и 100 фильтров.

      Но мне повезло, хотя 100к сообщений это не 1М, но даже на этих значения получился хороший отрыв.

      Я могу в принципе статью небольшую написать, если это интересно, т.к. сложно в одном комментарии все уписать, особенно про бинарную часть, т.к. я заюзал фишки из дискретной математики и теор. информации.
      • +3
        Мне отдельным пунктом понравилась вот эта адаптивность. Многие задавали вопросы об объёмах и характеристиках тестовых данных, но почти никому не пришло в голову выбирать из нескольких вариантов реализации в рантайме.
      • +8
        Если у вас найдётся время — напишите статью, было бы очень интересно прочитать.
      • +4
        Очень интересно! Очень интересно именно в плане задействованных теорий.
      • +1
        Денис, спасибо за комментарий. Можете дать ссылку на описание алгоритмов масок или просто название этого класса алгоритмов? Они почему-то совсем мимо меня прошли.
        • +2
          По своему принципу это маленькие фильтры Блума, где каждый бит сигнализирует о наличии буквы. В общем я этим вдохновился.

          ru.wikipedia.org/wiki/Фильтр_Блума

          • +1
            Я тоже фильтр Блума использовал, только для триграмм и потом хешировал в пространство в 8000 значений
  • +2
    Очень интересно читать решения других участников. Например, я тоже копал в сторону nfa/dfa, но мои тесты показали, что регулярки работают быстрее. Как оказалось нет :-) Спасибо за конкурс!

    Было бы интересно услышать комментарии от победителей о своих решениях и процессе разработки. Еще было бы интересно узнать, кто сколько времени посвятил конкурсу.
  • 0
    Очень интересно было бы почитать разбор решения Дениса и как оно такое получилось — выглядит необычно.
    • +3
      Я предложил бы всем победителям написать немного о том, как решали задачу.
    • 0
      См. веткой выше.
  • +1
    Поздравляю победителей! Приятно было поучаствовать. :)
  • –1
    Какой-то странный тест производительности.
    Мы с коллегами тоже участвовали в конкурсе, у нас свои методы тестирования производительности, как нам кажется, более объективные cloud.mail.ru/public/CZJu/iunQzxYW6 (bash скрипты), и у нас предложенные в конкурсном репозитории решения показали совсем другие цифры.
    • 0
      Можете показать код, которым генерировали тестовый набор данных, или рассказать методику?
      • –1
        Взяты из открытых источников. Не в этом суть. Вы свой тестовый набор данных подставьте, посмотрите разницу, это если интересно :) Я не намекаю, что должен быть в тройке призёров, я только лишь хочу сказать, что методика измерения производительности может сильно влиять на результат. В случае с bash скриптами на 100% исключается оптимизация движком, правда появляется время загрузки тестовых данных, но это время у всех будет примерно одинаковым и на большом количестве выборок можно посчитать avg и судить по нему.
        • 0
          Наш набор, а также код, которым он сгенерирован, находится в директории tests в репозитории.
          • –1
            К сожалению, нет возможности сейчас откорректировать свой вариант бенчмарка и добавить в него ваш набор тестовых данных… Поэтому предложил это сделать вам. Там изменять надо всего ничего, одну или 2 строчки, ну и файлы с данными рядом положить.
            • 0
              Я не сомневаюсь, что расстановка лидеров от этого изменится. Я хочу понять, почему Вы считаете свой набор более справедливым.
              • –1
                Да не в наборе тестовых данных дело, а в методике тестирования. Прошу прощения, если написал так, что вы подумали, что я жалуюсь на набор тестовых данных.
        • 0
          Что такое «оптимизация движком»?
          • –3
            Неплохой троллинг :)
            Если это, таки, был не троллинг
            Ну самый простой способ узнать про оптимизацию V8 — погуглить.
            В процессе выполения скрипта движок V8 умеет определять какие функции можно оптимизировать, вывести их выполнение на более низкий уровень, что увеличивает скорость выполнения этих функций в разы.
            • 0
              Это был не троллинг. Я просто само выражение не понял. Что V8 оптимизирует, я, конечно, знаю, но почему Вы считаете, что это надо исключить? Какой будет движок, было объявлено заранее.
              • –2
                Вы запускаете фильтр 10 раз с одними и теми же тестовыми данными. Вы думаете в реальной ситуации вам шлют по 10 раз одно и то же письмо всегда? Я тоже считаю, что нет. Поэтому, думаю, что нужно было исключить оптимизацию V8 между запусками фильтра по одному и тому же набору данных. Если бы это было 10 запусков фильтра по разным наборам данных, то всё нормально.

                Каждая итерация теста производительности у нас ассоциируется с временем жизни почтового ящика. У вас этот почтовый ящик проживает 10 одинаковых жизней.

                Это исключит не только оптимизацию движком, но и кеш внутри самого фильтра. Например, я все регулярки кеширую и при повторном использовании фильтра с тем же набором тестовых данных он отработать немного быстрее, т.к. всё что нужно уже будет в кеше, что тоже считаю не очень честным решением, т.к. именно такой подход к тестированию как у вас позволяет немножечко читерить и уже не важно на сколько хорош твой алгоритм с теоретической точки зрения, а важно угадал ты или нет с тем как будут проводить тестирование.
                • +1
                  Мы запускаем каждый проход в новой виртуальной машине, поэтому кэширование в тестируемом коде исключено. При этом оптимизация V8 действительно может влиять на следующие проходы, но в реальности так было бы — код запускался бы многократно без перекомпиляции. На оптимизацию V8 не могли бы повлиять конкретные данные, а только их статистическое распределение, которое в реальной ситуации вполне могло бы быть неизменным от раза к разу.
                  • –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
                    

                    Проверил только призёров и результат уже другой, тот кто на втором месте оказался на первом. Если интересно, то могу моим способом всех остальных тоже проверить и выложить результат, мне не сложно. Но тут время зависит ещё от некоторых факторов, загруженность процессора и прочее, т.к. выполнял на своём ноуте из под рут-системы. Думаю, что на выделенной виртуалке на свободном новеньком серваке результаты будут более показательыми.

                    Я лишь хочу сказать, что результат зависит ещё и от метода тестирования. Я считаю, что выбранный вами способ бенчмаркинга «трушным» способом протестировать производительность. Считаю, что правильнее перезапускать скрипт полностью для каждой итерации. Не прошу соглашаться со мной, не пытаюсь спорить, не жду пересмотра результатов, не жду ответа и понимания, не разжигаю межрассовые войны, просто делюсь мыслями и рассказываю о своей точке зрения, о том как я бы реализовал бенчмарк на вашем месте. Ну и итераций взял бы не 10, а штук 50, чтобы выборка была более репрезентативной.
                    • +1
                      Можете мой вариант (Andrew Kashta/filter.js) тоже проверить вашим скриптом?
                      • 0
                        $ ./run4.bash ./submissions/Andrew\ Kashta/filter.js
                        AVG = .74896037
                        BEST = .702608300
                        

                        Это быстрее чем у всех призовых.
                    • +1
                      Я попробовал делать как-то вроде этого, всё равно разброс между запусками одной и той же программы шире, чем зазор между лидерами. Это означает, что мы получили много хороших решений.
                      • +1
                        То есть вы считаете, что разница между вашим подходом (запуск в песочнице vm) и обычным запуском (require модуля и вызов функции) укладывается в статистическую погрешность? Можете объяснить, почему некоторые решения при вашем методе запуска работают в несколько раз медленнее? Уверен, что мое решение не единственное такое. Интересно было бы посчитать альтернативную таблицу результатов для всех участников, прошедших тест на корректность.
                        • 0
                          Нет, запуск в VM и без сильно различается. Но мы тестировали всех в одинаковых условиях.
                  • +2
                    Возможно, следующий раз имеет смысл публиковать также инструменты, которыми всё тестируются — коль скоро разные способы существенно влияют на результат. Чтобы участники могли не только проверить годность на эталонном варианте, но и измерить производительность разных подходов эталонным скриптом.

                    По мне, «в новой виртуальной машине» должно означать, что параметры производительности этой машины, с точностью до ошибки эксперимента, ровно те же (и это можно как-то проверить при тестировании).

                    В любом случае было интересно.
                    • +3
                      Обдумываю мысль в следующий раз использовать реальную виртуальную машину наподобие QEMU, раз «виртуалки» Node.js вносят такие сильные искажения.
                      • 0
                        Так было бы лучше. Свои варианты я тестировал на KVM-ной виртуалке (для чистоты эксперимента, хост-машина также перегружалась перед очередным массивом проверок), и, судя по итогам конкурса, итоги моих тестов дали бы иной результат.

                        При точном знании способов проверки будет проще создавать правильным образом оптимизированный код.

                        Спасибо!
                        • 0
                          Для авторов минусов: в моих тестах мои решения не попали магическим образом на первые места. :)

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

                          Надеюсь, организаторы конкурса найдут дебатах что-нибудь полезное. ну, и не только организаторы.
                      • 0
                        Кстати, когда вы писали про виртуальную машину в условиях конкурса, я подумал о нормальной виртуальной машине, а не о модуле vm… Думаю, что с этим лоханулся не я один…
  • 0
    Решение должно быть на чистом JS. Если Вы предпочитаете CoffeeScript или подобные языки, необходимо оттранслировать решение в JS перед отправкой.


    Почему нет чистого js-кода от Nadav Ivgi? github.com/hola/challenge_mail_filter/tree/master/submissions/Nadav%20Ivgi
    И почему вы посчитали 666 байт не чистого js-кода?
    • 0
      Да нет, вроде чистый JS. Только уж слишком топорное решение. Никакой алгоритмической ценности нет.
    • +1
      github.com/hola/challenge_mail_filter/blob/master/submissions/Nadav%20Ivgi/filter.js — это чистый JS, в смысле, что не CoffeeScript или подобное.
    • +3
      Fat arrow, она же => является частью ECMAScript 2015
      • 0
        Теперь понимаю, что Вы поняли «чистый JS» как чистоту стандарта. Такой вариант прочтения не приходил нам в голову до сих пор, иначе мы внесли бы в текст уточнение. Жаль, что так получилось.
      • 0
        Ах да, читал про это некоторое время назад.
        По сути, это замена function(), просто более красивее и чище.
        Ерунда, можно пренебречь.
  • +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());
    


    Кто-нибудь может погонять у себя скрипт? Интересны результаты в различных средах исполнения.
    • –1
      Есть разница между 32-х и 64-х битными версиями. Возможно это ваш случай.
      • 0
        Проверил и там, и там. У меня на node x64 все решения получаются немного медленнее, но кардинальной разницы нет. Возможно, дело в ОС.
        • 0
          Отвечу сам себе. Дело не в битности и не в ОС, а в способе запуска тестов. Организаторы запускают через vm, для моей реализации это почему-то оказалось критично. Безхитростный запуск отрабатывает в 2.5 раза быстрее чем через tests/test.js.
          • 0
            Да, судя по всему v8 не производит какие-то оптимизации, когда код выполняется не в текущем контексте, а require же использует текущий контекст. Вроде даже для текущего контекста резервируются отдельные регистры.

            Т.е. разница в методах выполнения script.runInContext или script.runInThisContext.

            В общем-то это косвенно можно было понять по комментарию habrahabr.ru/company/hola/blog/270847/#comment_8657097, что выполнятся будет на vm и очевидно не в runInThisContext

            Для меня на самом деле это было неожиданностью, такое поведение v8.
            • 0
              Проверил, действительно, если переделать тест на использование runInThisContext вместо runInContext, начинает работать в 3 раза быстрее. Понять бы еще, что именно так тормозит в не текущем контексте
              • +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, его код быстрее.
                (если что, я ни с кем не аффилирован и в конкурсе не участвовал)
                • 0
                  Думаю, что это серьёзный повод пересмотреть результаты. Заодно и методику замера изменить. И запускать по 10 итераций на каждое решение и запустить так все решения 10 раз. В итоге будет по 10 лучших результатов на каждое решение и из них выбрать лучшее. Так будет справдливее! А то я сейчас тесты гоняю и время от времени некоторые тесты на 30-40% быстрее начинают работать, а некоторые наоборот медленнее… И всё это на одном и том же наборе данных (на том, что предложено организаторами конкурса).
                  И самое оригинальное решение надо тоже пересмотреть, как мне кажется, оно никапли не оригинальное, оно слишком простое и просто маленькое по размеру, но никак не оригинальное. Но последнее это моя субъективная точка зрения.
                  • 0
                    Как и в прошлом конкурсе, мы сделаем выводы на следующий раз, но пересматривать результаты не будем.

                    Мы не утверждали, что то решение — самое оригинальное. Специальный приз присуждается по нашему субъективному усмотрению. Например, в одном из конкурсов его получил самый младший участник.
                    • +1
                      Раз уж вы хотите оптимизацию под дивжок (а не под весь зоопарк js vm) — по идее, надо выкладывать и конфиг движка, который будет использоваться (например, внутри vm или нет, под какой архитектурой, os, с какими ключами будет запускаться — производительность операций от этого может меняться). А то, получается, рассчитывали на одно, увидели другое. Это как, к примеру, инлайнинг отключить в компиляторе. Я бы выкладывал тестовый код и конфиг, естественно, без датасета (возможно ещё без проверки валидности).
                    • +1
                      Я разочарован. Уверен, что в следующий раз будет такая же балалайка.
    • –1
      Typealias Nonmutating 563
      Dmitry Rybin 920

      i5-3230M@2.6GHz/win7(64)/node-5.3.0/

      Несколько раз прогнал
      • +1
        Мы использовали Node.js 5.0.0, о чём было написано в правилах.
    • +1
      1. git clone github.com/hola/challenge_mail_filter.git
      2. cd challenge_mail_filter
      3. node --expose-gc tests/test.js submissions/*****/*****.js
  • +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. Поскольку в комментариях подняли эту тему, то замечу, что на моем бенчмарке + тестовых данных от организаторов лучшим из призеров оказался Юрий Килочек (примерно на 17% обойдя официального победителя). Впрочем, мой алгоритм на моем бенчмарке еще в 1,5 раза быстрее. Впрочем, мне это уже не поможет. Впрочем, и Юрию, скорее всего, тоже :)
    • +2
      Большое спасибо за развёрнутый комментарий! Очень интересно. Жаль, что Ваше решение не прошло. Мы всё равно его обязательно почитаем.

      К тому же, хотя денежные призы и ценные, здо́рово, что Вы цените саму возможность решить интересную задачу. Мы будем устраивать новые конкурсы и постараемся сделать так, чтобы таких случаев, когда хорошие решения не проходят из-за мелких ошибок, было поменьше.
  • +3
    хе, тоже не дотестил )))
    провалился на test_glob(script, '?', ['.', '?', '*', 'z'], ['zz', '\\?']);
    не ожидал в проверке на корректность одного '?' в правиле

    но если исправить в одном месте, то все гут — было бы 35 место
    в принципе доволен результатом )))
    спасибо за конкурс !
  • +2
    хм
    если бы #12 Pavel Gruba вставил бы самый простой кэш — его результат был бы на 1 месте
    ну как же так забыть про кэш…

    p.s. правда тестил на node v4.2.1, но думаю не сильно что-то измениться?
    • +2
      Может измениться. Например, из-за особенностей запуска тестов организаторам и, выиграли те, кто имел все объявления методом внутри функции filter. Сыграло роль как сработал компилятор и рантайм v8. Между 4.2 и 5.0 он может сильно различаться.
  • +1
    Спасибо за отличный конкурс!

    Очень понравилось лаконичностью решение Сергея Голуба. Ну и 1-2 места респект, господа. Очень было бы не плохо увидеть статью, где бы Вы рассказали про маски.

    Сам я на 16 месте.

    P.S. гн zBit Вы на каком месте? По нику не вижу Вас в табличке. Так, помериться просто :)
    • 0
      Опишу оптимизации, которые использовал, может кому интересно будет.

      1. Упаковка regexp-ов в массив правил
      2. Кэш по ключу «from + разделитель + to» — т.е. если встречается пара from/to, которая уже встречалась, то сразу отдаются подготовленные actions по данному ключу из массива кэша
      3. Т.к. для кэша надо считать ключ «from + разделитель + to», то можно и проверять сразу всю это строку за один раз одним regexp-ом вида «regexpFrom + разделитель + regexpTo»
    • 0
      19 место.
      Прогнал все решения по своим тестам на корректность, которые были проверены по «эталонной реализации», получилось -19 человек из тех что заняли хоть какое-то место. Т.е. не у всех ещё «по-настоящему» корректно работает фильтр.
      Сейчас сижу выбираю где виртуалку поднять, чтобы тест на производительность по моему бенчмарку прогнать с теми тестовыми данными, что были сгенерированы для конкурса организатором. Посмотрим что выйдет :)
  • +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 Pletnev
    • 0
      Роман прислал большую подборку тестов, за что ему спасибо. К счастью, призёры проходят все тесты.
      • 0
        Алексей, спасибо за ответ. Хотелось бы, чтобы вы также прокомментировали недостатки тестов на производительность, которые указали Роман и Алексей (zBit)
        • 0
          Учтём на будущее, что vm в Node.js вносит сильные искажения в замеры производительности. Рассмотрим возможность в следующий раз применять полноценную виртуальную машину наподобие QEMU.
  • +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 Pletnev
    • +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).
      Постараюсь сегодня успеть опубликовать результаты своего тестирования на гитхабе.
      • +1
        На гитхабе-то своем?
        Тут ссылочку оставить не забудьте — интересно.
        • 0
          Да, на своём, к другим доступов нет. Ссылку оставлю. Всё ещё выполняется бенчмарк, но уже половину прошло.
  • +5
    Как обещал, альтернативные результаты конкурса.
    github.com/zbitname/hola_nodejs_challenge
    Заранее прошу не бить. Сделал это только лишь для того, чтобы показать на сколько сильно могут отличаться результаты в зависимости от методики тестирования.
  • 0
    Еще одни альтернативные результаты конкурса:
    github.com/OLS-RU/challenge_mail_filter

    Но уже на другом тестовом файле (с большим количеством записей и более сложными масками).
    Мое субъективное мнение — на сложных тестах многие спорные моменты относительно методики тестирования, обсуждавшиеся в диалогах выше, перестают значимо влиять на результат, и он (результат) становится более точным отражением усилий участника, направленных на вопросы алгоритмической оптимизации.

    В любом случае, отдельная признательность организаторам конкурса за прошедшее мероприятие, достаточно нетривиальное на сегодняшний день.
    • –1
      P.S. Относительно проверки корректности, произведенной выше zBit, на моем тесте еще 4 участника дают результат, отличный от ожидаемого (все находятся в диапазоне 20-60 места).
  • +1
    Сделал тупую ошибку — Stepan Pupkin/solA.js
    function match(email, charPieces)
    {
            ...
    	var maskLen = mask.length;
            ...
    	if (email.length <= maskLen)
    	{
    		return false;
    	}
            ...
    

    Там очевидно нужно было использовать < вместо <=. Я как-то пропустил это при тестировании. А так бы был где-то посередине таблицы.

    А вообще, надо было отправлять solB (regExp, а в случае отсутствия * — сравнение по charCodeAt()), которое на тестах организатора врывалось в 15 лучших. К сожалению, с моими тестовыми данными оно показывало время хуже, чем solA.
    • –1
      А на моем тесте
      github.com/OLS-RU/challenge_mail_filter
      Ваше решение (solA, в случае исправления ошибки) было бы 10-ым с результатом 8,009 (тест на корректность был бы пройден).
  • +3
    Идеальных конкурсов не бывает, но организаторы очень старались. Большое спасибо организаторам за конкурс, а участникам — за интересные решения. Критерии и способы оценки у всех разные, в данном конкурсе способы и результаты тестирования видны всем, а не являются «черным ящиком».

    Лично мне понравилось решение Sergey Golub — при высокой скорости обработки такой код понятен с первого взгляда, и в дальнейшем его поддержка и доработка будет простой, что порой имеет большее значение, чем выигрыш в несколько мс.
    • 0
      для интереса посмотрите ещё код Pavel Gruba
      код практически такой же с первого взгляда +- пару мелочей
      просто он магическим образом забыл про кэш (
      но если добавить кэш — то из-за этой пары мелочей работает довольно быстро (у меня на тестах организатора получилось для него 1 место)
  • 0
    А самое оригинальное решение тоже будет пересмотрено? Чтобы не разбираться в чужом коде, может попросить людей прислать описания их алгоритмов человечьим языком?
    • 0
      В этот раз мы решили присудить специальный приз не за оригинальность, а за компактность кода.
      • 0
        А в условиях конкурса написали, что выберите самое оригинальное решение, а не компактное…
  • 0
    Объявление: Мы решили пересмотреть итоги конкурса из-за серьёзных недостатков, обнаруженных в тестовой системе. Новые итоги будут через 1–2 дня.


    Вот, интересно. А это на каком основании? Юридически, ваш пост habrahabr.ru/company/hola/blog/270847 является публичной офертой, и там указано что:

    Победит тот, чей код будет самым быстрым при условии прохождения тестов на корректность.

    Победители будут объявлены 8 января 2016.


    Я как лицо крайней заинтересованно, хочу спросить вас, на каких юридических основаниях вы меняете уже объявленные результаты конкурса?

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

    Результаты объявленные 8 января — единственно предусмотренные по договору. Поэтому требую объяснений.
    Вопрос 1500 долларов довольно серьезный, мне и к юристу не сложно обратиться по этому поводу.
    • +1
      Мы неправильно определили, чей код самый быстрый. Не меняя заявленного критерия присуждения призов, мы исправляем ошибку в тестах на соответствие этим критериям.
      • –4
        В вашей оферте про это ничего не сказано. Я сразу говорю — если вы поменяете результаты конкурса, мне придется обратиться в суд.

        Договор надо исполнять. А в нем нет ни слово о том, что предусматриваются какие-то дополнительные прогоны и т.д., ни критерии тестирования, ни т.п. У вас было 2 недели фактически, что бы провести тестирования как надо, и определится к 8 января.

        Хотите что-то поменять, создавайте альтернативный прогон, с призами или нет но эти результаты юридически вы не имеете права трогать.

        Это моя принципиальная позиция.

        • 0
          А кто ответчиком будет?
    • +2
      Если вы уверены в том, что ваш алгоритм действительно быстрее всех, то вам не стоит беспокоиться о том, что кто-то может вас сместить с 1-го места.
      Но вообще, по-честному, замеры были произведены некорректно, это объективная оценка и с ней согласились организаторы конкурса. Надо смириться с этим.
      • 0
        Честно это когда договор исполняеют обе стороны. Я свою часть выполнил честно, не мухлевал, отослал в срок, все как надо.

        У организаторов было куча времени что бы все проанализировать и сделать тестирование как им хочется. Никто не тянул их «за руку». Если опубликовали результаты, то должны выполнять свои обещания.

        В конечном итоге результат зависит не только от того runInContext/runInThisContext, а от количества фильтров/писем, разрядности процессора, способа сборки node.js, средней длины писем и сложности фильтров.

        Т.е. элемент неожиданности заложен в сам конкурс, и я участвуя в нем учитывал это. А сейчас тестовые условия переделывается постфактум, без извещения других участников, а тем более объявленных победителей. Это прямое нарушение оферты.

        Т.е. проблема в юридическом аспекте, а не в том чей алгоритм лучше.
        • 0
          У организаторов было куча времени что бы все проанализировать и сделать тестирование как им хочется.
          Да, у них было много времени (если учесть, что они по праздникам работают), но они этого почему-то не сделали.

          Элемент неожиданности должен быть только в тестовых данных (количество условий, значения), а не в методах тестирования, иначе это не конкурс, а рулетка какая-то. Некорректный метод тестирования вносит слишком большую погрешность, согласитесь с этим. А теперь поймите людей у которых действительно интересные и эффективные решения практически на любых типах и размерах входных данных, а они почему-то занимают 50+ место, хотя реально должны входить в тройку победителей. И всё из-за того, что они и представить себе не могли, что тестирование будет проводиться именно так (проблема не в тестовых данных, а в том каким образом запускают эти тесты).
          • +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


            Т.е. у всех у кого алгоритмы сливаются при выполнении в другом контексте, так же успешно сливаются и при разных входных данных.
            Поэтому, какой смысл в пересмотре?

            Текущие победители, и не только мой алгоритм, хотя бы стабильно показывают приличный результат вне зависимости от входных данных. Причем как в абсолютном, так и в относительном измерении.
            • 0
              В моей версии входные данные идентичные тем, что были в конкурсе, изменён лишь метод тестирования. Я писал об этом уже очень много раз, в описании репозитория об этом написано тоже.
              • +1
                Раз можно поменять способ запуска, то почему нельзя поменять количество фильтров/писем?

                Если версия Roman Pletnev хорошо ведет себя на 100 фильтрах, но плохо на 1000, то какой результат надо брать?
                • –1
                  Об изменении тестовых данных или их размеров никто речи не вёл, на сколько я вижу. Речь идёт о способе тестирования, способе запуска тестов.
                  • +2
                    А почему можно менять способ запуска, а нельзя поменять количество фильтров?

                    О количестве фильтров вообще никаких данных не было. А вот о способе запуска были указания feldgendler:



                    Т.е. многие сетуют что писали и оптимизировали под запуск через require, ну вот в комментарии от представителя компании указано что запускаться будет без require.
                    • 0
                      Вот одно из описаний сути проблемы: habrahabr.ru/company/hola/blog/274697/#comment_8730883
                      • +2
                        Суть проблемы в том, что организаторы:
                        1. Не дают ни четкого описания окружения, ни количественных/качественных характеристик входных данных.
                        2. Не следят за своими словами, сначала говорят одно, потому делают другое.
                        3. Задним числом нарушают свои же обязательства.

                        Первая проблама да, неприятная, но она не противоречит правилам конкурса и порядку проведения. Так что это субъективное дело.

                        Вторая и третья проблема лежат в совершенно другой плоскости, в объективной, в юридической. Организатор конкурса опубликовал одни результаты, затем хочет их аннулировать. Сказал одно — сделал другое. Поменял правила задним числом. Выставил других дураками.

                        Это не просто сомнительный параметры запуска, это явное нарушение своих обязательств, нарушение интересов участников, которые имеют права, на то, что бы конкурс проходил по тем правилам которые были опубликованы в ноябре.

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

                        Вот и все. Что касается, что результаты должны соответствовать реальной жизни и т.д. В реальной жизни я бы просто написал модуль на C, и сделал пакет для npm и получил быстродействие на порядок выше чем лучшие из приведенных результатов.
                        • 0
                          > 2. Не следят за своими словами, сначала говорят одно, потому делают другое.
                          > получил быстродействие на порядок выше чем лучшие из приведенных результатов.
                          ок. «на порядок» это как минимум 10x. сомнительно.
                          • +1
                            Не сомнительно, я переписывал решения на golang, получил быстродействие на порядок больше.
                            Причем мое решение даже при другом способе измерения не отсает более чем на 20-30% от других решений.

                            Я вообще планировал написать большую статью по этой теме, с разбором других результатов, и результатами прогона других решений на golang (я переписал некоторые решения 1 в 1).

                            Но сейчас понимают что это бессмысленно.

                            Получить хотя бы свои законные деньги. Какие уж там статьи.
                  • 0
                    [del]
          • +1
            PS.
            Но вопрос, не кто лучше, а в том что налицо нарушение договора. Это намного серьезнее, чем неаккуратное тестирование.
            В плане методики тестирования никаких четких обязательств авторы конкурса на себя не брали.

            А вот в плане дат, победителей и т.д. — все довольно четко, и сейчас мы видим как они собираются нарушить свои же обязательства.
    • 0
      > является публичной офертой
      С чего вы взяли? По статье 1057?
      Дык легко опровергнется по «2. Публичный конкурс должен быть направлен на достижение каких-либо общественно полезных целей».
      • 0
        Публичный конкурс это вид публичной оферты, т.е. публичного предложения. Если организатор его опубликовал, а участник выполнил требования конкурса, то между ними устанавливаются соответствующие обязательства.

        Там же кстати, в статье 1058:
        1. Лицо, объявившее публичный конкурс, вправе изменить его условия или отменить конкурс только в течение первой половины установленного для представления работ срока.


        4. Если при изменении условий конкурса или при его отмене были нарушены требования, указанные в пунктах 1 или 2 настоящей статьи, лицо, объявившее конкурс, должно выплатить награду тем, кто выполнил работу, удовлетворяющую указанным в объявлении условиям.


        Статья 1059
        1. Решение о выплате награды должно быть вынесено и сообщено участникам публичного конкурса в порядке и в сроки, которые установлены в объявлении о конкурсе.



        В общем, организатор не имеет права менять даже дату публикации результатов, а уж тем более изменять какие-то параметры и публиковать новые результаты.
        • 0
          Ну я бы начал с того, что я не уверен что Хабр является СМИ (http://rkn.gov.ru/mass-communications/reestr/media/).
          И вы почему-то проигнорировали п.2 ст 1057 о том, что конкурс должен быть направлен на достижение каких-либо общественно полезных целей. Если этот пункт не выполняется, то публичный конкурс признаётся несостоявщимся. Правда теоретически можно потребовать оплату усилий, потраченных на выполнение задания (167ая статья), но тут тоже спорно всё.
          В любом случае, это теоретические рассуждения, потому что вы будете судиться с израильской Hola Ltd, которая не имеет представительства в России.
          • –2
            Публичный конкурс может быть закрытым, т.е не обязательно через СМИ. Причем в РФ есть более расширенная трактовка СМИ, это не только зарегистрированное СМИ. Сайт при некоторых условиях тоже может рассматриваться как СМИ, даже если его нет в реестре. Т.к. важен характер предоставления и распространения информации, а не его нахождение в реестре.

            Общественно полезная цель была заявлена «мы ищем талантливых программистов, поэтому авторы интересных решений будут приглашены на собеседования.» Поиск талантливых программистов это общественно полезная цель. Т.к. все олимпиады по программированию, в т.ч. государственные только для этого.

            Израиль это вполне правовое государство, найти юриста там не проблема. 1500 USD в Израиле тоже деньги.

            Хотя что-то мне подсказывает, что Hola Ltd. зарегистрирована в оффшоре, т.к. ее деятельность в Израиле считается незаконной.

            PS
            Вообще мне не столь важны деньги, сколько вероломное поведение организаторов и их работников.
            Эти люди должны быть наказаны и опозорены.

            Таким не место на Хабре. Надо уметь отвечать за свои слова.
            • 0
              > Публичный конкурс может быть закрытым, т.е не обязательно через СМИ
              Вам пришло персональное приглашение на конкурс? Нет? Тогда это не закрытый конкурс.
              > Поиск талантливых программистов это общественно полезная цель
              Здесь монут быть разные точки зрения. Для меня это выглядит как рекрутинг, не несущий пользу обществу.
              > Хотя что-то мне подсказывает, что Hola Ltd. зарегистрирована в оффшоре, т.к. ее деятельность в Израиле считается незаконной
              Насколько я знаю, юр. лицо израильское. Поэтому они, кстати, у них и нет exit node в Израеле, чтобы а-та-та не получить.

              > Вообще мне не столь важны деньги, сколько вероломное поведение организаторов и их работников
              Хз. По мне так всё честно. В методике тестирования объективный косяк — обновляем методику и производим перетестирование решений. Кстати, в вышеупомянутых вами олимпиадах такое тоже практиковалось. Как в ACM так и в личных. Бывали пересмотры и через неделю после проведения.
              • 0
                Для закрытого конкурса персональное приглашение является не обязательным, в законе лишь об определенном круге лиц: «когда предложение принять участие в конкурсе направляется определенному кругу лиц по выбору организатора конкурса.»

                Я лично получил сообщение о конкурсе на email, т.к. был подписан на хаб, как член хабра-сообщества. Т.к. вполне определенный круг лиц.

                Здесь монут быть разные точки зрения. Для меня это выглядит как рекрутинг, не несущий пользу обществу.

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

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

                Насколько я знаю, юр. лицо израильское. Поэтому они, кстати, у них и нет exit node в Израеле, чтобы а-та-та не получить.

                Ок.

                Хз. По мне так всё честно. В методике тестирования объективный косяк — обновляем методику и производим перетестирование решений. Кстати, в вышеупомянутых вами олимпиадах такое тоже практиковалось. Как в ACM так и в личных. Бывали пересмотры и через неделю после проведения.

                В олимпиадах есть апелляция, она предусмотрена правилами олимпиад. После апелляции результаты можно изменить только в судебном порядке.

                В этом конкурсе ничего такого не было предусмотрено. Если бы было, то я бы и не возмущался. Ну и не участвовал бы, прошел мимо.
  • +2
    Прошу обратить внимание организаторов на github.com/hola/challenge_mail_filter/pull/5
    Добавлены тесты для проверки корректности, такие данные могут ввести пользователи, поэтому их нужно учитывать, следовательно тест на корректность станет более подробным, что может отсеять ещё несколько участников.
    • +1
      Спасибо, Ваши дополнения добавлены в тестовую систему.
      • 0
        Не за что! :)
  • +3
    feldgendler, может тогда уж и участникам подкорректировать код, как минимум для прохождения корректности?
    • +3
      … вдруг появятся еще интересные решения
    • +1
      Мы уже приняли от участников две поправки к своим решениям. Естественно, исправленные версии будут участвовать вне конкурса.
      • 0
        +1 — третье примите?
        Естественно вне конкурса — ради спортивного интереса…
        • 0
          Принял.
  • +2
    Отправлял наиболее общее решение, решил не рисковать с более хитрыми вариантами. Зря :) Так я в шестом десятке, другие мои варианты позволили бы попасть в пятый. Авторы топовых решений, молодцы, конечно, моя подготовка в этой области сильно слабее — я на околопрофильной специальности учился, теперь есть стимул почитать подробней про DFA и т. п. Плюс на некоторые грабли, которые тут в комментариях фигурируют в том числе, я наступил сам и сам разобрался почему и зачем. В моей деятельности оптимизация скорости не является основной задачей, так что подобный опыт был интересен и полезен без сомнения.

    А что касается пересмотра результатов, ну, как я понимаю, если задаться целью, то можно подобрать такой набор данных, который расставит участников в любом порядке. Утрирую, конечно, моё решение, например, вряд ли догонит топов как ни крути (если не брать совсем вырожденные наборы, пожалуй), но тем не менее. С другой стороны, я сильно сомневаюсь, что организаторам подобные манипуляции могут быть интересны, если честно.

    Спасибо за конкурс, жду следующего!
  • +6
    Добрый день, хабр.
    Летучие обезьяны подняли мне веки, и я всё-таки решился написать здесь. Я создал тот самый баг на github, по итогам которого пересмотрели методику, и хочу чтобы кто-нибудь всё-таки попытался объяснить hola, что такое соревнование, раз уж у меня не получается.

    Соревнование это не «о чувак, нам нужен фильтр для 100 сообщений». Соревнование — это гонка лучших умов в погоне за какой-то великой целью, за невозможным. Играть музыку на калькуляторе, писать десятикилобайтные RPG в браузере, процессить стотыщмиллионов сообщений миллиардом правил за секунду, вот что такое соревнование.

    Цель в 100 (!!) рулесов, так отстаиваемая холой как реальная НИЧЕГО общего не имеет с соревнованиями вообще. Ну и это такая классная русская черта, прикрывацо лозунгами про ДНК и международный опыт (см. первый ответ), а потом в закрытом issue писать что «мы верим что больше 100 рулесов никакой пользователь не создаст».

    Классно, ребята, но я бы никогда бы не учавствовал в таком, дело же совсем не в призах. По крайней мере, для меня.
    • +3
      Золотые слова.
      Я переписывался по e-mail с организатором конкурса, пытаясь донести идею увеличения набора правил до 1000 и значимо увеличить их алгоритмическую сложность, но увы…
      github.com/OLS-RU/challenge_mail_filter
    • +2
      Сорри за некропостинг, но

      > классная русская черта, прикрывацо лозунгами про ДНК
      > xderry commented 10 days ago

      А вот и мимо: Дерри монументально, сокрушительно не русский.

      (Источник: знаком лично.)
      • 0
        Ну значит он своих диких русских не может в узде держать. :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка