Компания Hola снова объявляет конкурс по программированию на JS с солидным призовым фондом:

  1. Первое место: 1500 USD
  2. Второе место: 1000 USD
  3. Третье место: 500 USD
  4. Возможно, мы решим отметить чьё-то чрезвычайно оригинальное решение специальным призом в 350 USD.
  5. Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в 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)


  1. kumekay
    13.11.2015 21:00
    +3

    при отправке пустого POST запроса с Content-Type: application/json на hola.org/challenge_mail_filter/reference в ответ 502 Bad Gateway


    1. feldgendler
      13.11.2015 21:21
      -9

      В теле запроса должен быть корректный JSON.


      1. vintage
        14.11.2015 10:23
        +4

        И тем не менее, на неверный запрос сервер должен возвращать 4** ошибку, а не 5**.


        1. feldgendler
          14.11.2015 11:51
          -22

          Мы парсим JSON на уровне express middleware, и было неудобно для этого одного урла делать исключение. Вам же это не сильно мешает пользоваться эталонной реализацией? Ну вот и славно.


          1. Aquahawk
            14.11.2015 14:00
            +28

            Если Вы подозреваете, что эталонная реализация выдаёт неверный ответ для тех или иных входных данных, пожалуйста, сообщите нам.

            При недопустимых входных данных Вы получите ответ HTTP 400 с описанием ошибки в формате text/plain.

            при отправке пустого POST запроса с Content-Type: application/json на hola.org/challenge_mail_filter/reference в ответ 502 Bad Gateway

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

            Какие правила ещё реализовать было неудобно? Может и выплаты неудобно будет делать?


  1. Antelle
    13.11.2015 21:47
    +3

    Какие регулярки быстрее — компилируемые или нет? =)
    > условие сформулировано предельно однозначно
    > победит самое быстрое
    Чтобы однозначно сформулировать, что значит быстрый, надо описать, как вы её хотите использовать:
    1. 2-3 фильтра, 1М сообщений
    2. 1M фильтров, 100 сообщений
    3. повторное использование с большей вероятностью с теми же фильтрами или с разными


    1. feldgendler
      13.11.2015 22:27

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


      1. AxVPast
        14.11.2015 01:44
        +3

        Человек как бы намекает на неудачную сигнатуру метода, который предложен в задании.
        Логичнее было бы попросить седелать метод-фабрику, который принимает правила в качестве аргумента и возвращает функцию с единстенным аргументом — сообщением. Скорость работы подобного оптимизированного решения будет наибольшей.

        Просто по требованиям сразу и сходу напрашивается решение на nools. Кстати они умеют компилироваться в 1 JS файл без лишних зависимостей. Никогда не смотрел, что оно там компилит, но уверен разобраться в коде будет трудно :). Понятное дело, что построение сети reto на каждом вызове функции решение не из самых быстрых, в результате половину решения будет составлять автодетект, что правила поменялись и нужно их перекомпилировать заново.

        Поменяйте сигнатуру метода в задании, то что есть точно не в стиле NodeJS.


        1. feldgendler
          14.11.2015 01:52
          -3

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


          1. 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) имея этот опыт, очень захотелось поучаствовать (не ради копеек, конечно), но я действительно не понимаю, чего Вы хотите добиться


            1. feldgendler
              14.11.2015 12:59
              -1

              Писем будет на несколько порядков больше, чем правил. Это всё, что я могу пока сказать.


              1. DYefimov
                14.11.2015 13:30
                +9

                Задайте порядок в 10й системе того и другого, и все будут счастливы — это всё, что я хотел спросить.


            1. AxVPast
              14.11.2015 14:01
              +2

              Судя по условиям они ищут более менее (алгоритмически) толкового джуниора, который более менее разбирается в теории построения регулярных выражений и JavaScript.
              Если у них всегда так ставят задачи в компании и такие сигнатуры методов от архитектора — то сомительно, что даже стоит пробовать участвовать в подобном конкурсе.

              P.S. Предлагаю подумать над другим вопросом — можно ли в JS перехватить сам факт создания обоих массивов до того как вызовут функцию filter. То есть достичь ситуации когда выходящий массив будет построен до вызова саомй функции :))). Наверняка время меряют по вызову самой функции фильтр не считая накалдные расходы времени на загрузку структур данных в память.


              1. DYefimov
                14.11.2015 14:05
                -5

                Вооооот!
                Жму руку, мысль доехала, как я смотрю.
                К сожалению, я немного набухался в данный момент — отвечу завтра на трезвую.


                1. DYefimov
                  14.11.2015 23:13
                  +2

                  Ладно, ладно — хватит минусовать.
                  По делу.
                  Своим постом выше, я пытался сказать, что (при нормальной реализации) затраты на «поддержание» данных намного меньше (место/время), чем то, что предложили нам в этом задании.


              1. DYefimov
                14.11.2015 14:23

                Да, замечу, что регулярки не панацея — на JS можно делать вещи намного быстрее регулярок. Была бы задача.


  1. Drag13
    13.11.2015 21:49
    +4

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


    1. feldgendler
      13.11.2015 22:26
      -4

      Да.


  1. xytop
    13.11.2015 22:11
    +3

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


    1. feldgendler
      13.11.2015 22:28
      -4

      Подумаем над тем, чтобы сделать так на следующем конкурсе.


  1. NoorBall
    13.11.2015 22:26
    +13

    Как выиграть 3000 USD?
    1. Создаешь липовую почту.
    2. Отправляешь себе приглашение на настояющую почту.
    3. Участвуешь в конкурсе и выигрываешь 1500 USD.
    4…
    5. Profit!


    1. dom1n1k
      13.11.2015 23:07
      +19

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


    1. caveeagle
      13.11.2015 23:19

      Предположим, что у тебя шанс выиграть 1:100, но ты знаешь человека, у которого такой шанс намного выше =))


    1. xenohunter
      16.11.2015 12:03
      +1

      Как выиграть 6000 USD?
      1. Создаёшь три липовых ящика.
      2. Отправляешь приглашения на три других ящика.
      3. Пишешь для конкурса три крутых реализации.
      4.…
      5. Profit!

      P.S. Вообще, я что-то не очень верю в эти конкурсы. Кажется, были уже прецеденты.


  1. Lennotoecom
    13.11.2015 23:23

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

    Спасибо.


    1. feldgendler
      14.11.2015 00:56
      -1

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


      1. g1t5
        14.11.2015 08:18
        +2

        пока хватает памяти

        т.е. память ограничена? :)


        1. feldgendler
          14.11.2015 11:49
          -2

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


  1. ionicman
    13.11.2015 23:34
    +2

    А подтверждение, что письмо у Вас — придет?


    1. feldgendler
      14.11.2015 00:57

      Да.


  1. Aquahawk
    13.11.2015 23:49
    -5

    Вам нужно написать модуль для Node.js

    Ваше решение должно состоять из единственного файла на JS.

    производительность


    1. ionicman
      13.11.2015 23:55
      +1

      Можно узнать, что не так?
      Насколько я понимаю всю суть, файл будет типа:

      function filter(...) {}
      exports.filter = filter;
      

      И все.


      1. Aquahawk
        14.11.2015 00:25
        -3

        Решение должно быть на чистом JS.

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


        1. Drag13
          14.11.2015 00:59
          +2

          Странно — да
          Весело — да :)
          Вопрос скорее всего вообще не в js :D


        1. dom1n1k
          14.11.2015 01:46
          +2

          Ясно же, что конкурс нужен для поиска JS-программистов, а не прикладного решения задачи фильтрации.


  1. Alex_At_Net
    14.11.2015 01:02
    +3

    Укажите, пожалуйста, жадность * в маске. А то непонятно, «aba» подходит "*a*b*" или нет.


    1. feldgendler
      14.11.2015 01:04
      +1

      Вы можете проверить это с помощью нашей эталонной реализации.


  1. Drag13
    14.11.2015 01:14

    А можно список имейлов (хотя бы тысяч 50) что бы тесты погонять? Или это очень нагло и надо искать самому? :(


    1. feldgendler
      14.11.2015 01:50

      У вас же, наверное, в почтовом ящике много писем.


  1. Sirion
    14.11.2015 02:40

    М… я, конечно, не гений-алгоритмист, но чем эта задача отличается от простой задачи на проверку соответствия строки маске? Тем, что придётся повторить эту операцию от M*N до 2*M*N раз, где M — количество писем, а N — количество правил? Всё равно же придётся каждое с каждым проверять. Ну, мемоизацию разве что прикрутить, на случай одинаковых адресов.


    1. mark_ablov
      14.11.2015 08:00
      +1

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


    1. feldgendler
      14.11.2015 11:47

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


  1. dangreen
    14.11.2015 07:49
    +1

    Странно что паттерн для адреса почты чувствителен к регистру, в эталонной реализации.


  1. vintage
    14.11.2015 10:32

    Не нашёл описания паттернов.


    1. feldgendler
      14.11.2015 11:47
      +1

      Маски регистрозависимые; символу * в маске удовлетворяет любое число (0 или более) любых символов, а символу? — один любой символ.


  1. 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.
    


    : ( простите за нубский вопрос


    1. feldgendler
      14.11.2015 14:02

      Я сейчас проверил, эталонная реализация работает. Проверяйте, как именно Вы делаете запрос.


    1. dangreen
      14.11.2015 16:37

      Делайте запрос с помощью curl или wget или еще чего, из браузера у вас это не получится.


      1. Lennotoecom
        14.11.2015 17:27

        спасибо :)


  1. RGB
    14.11.2015 16:45

    ? — один любой символ


    Ноль либо один или точно один?


    1. Duha666
      14.11.2015 18:05

      Ровно один


    1. feldgendler
      14.11.2015 18:07

      Вы можете воспользоваться эталонной реализацией, чтобы выяснить это.


  1. Drag13
    14.11.2015 17:19

    Есть предложение
    Брать не последний лучший результат, а лучший результат последних двух.
    Причина в том, что частота встречаемости почтовых адресов не известна. Или дать больше информации.


  1. KingOfNothing
    14.11.2015 18:11

    А можно изменять входящие объекты?


    1. feldgendler
      14.11.2015 18:13

      Можно.


  1. xytop
    14.11.2015 18:52
    +3

    Вопрос по поводу написания модуля:

    Вам нужно написать модуль для Node.js, экспортирующий одну функцию

    Это значит
    module.exports = function(m, r){ /* .. */ }
    

    или
    exports.filter = function(m, r){ /* .. */ }
    

    ?

    В первом варианте экспортируется функция, а во втором объект с этой функцией. Как правильно сделать?


    1. Methos
      14.11.2015 21:23
      +1

      module.exports


    1. feldgendler
      15.11.2015 04:31
      -1

      Второе.


      1. Aquahawk
        15.11.2015 10:37
        +3

        А может вы это в правила внесёте официально? Ибо уже наблюдаем людей введённых в заблуждение(см выше). Я всё ещё думаю участвовать или нет, и честно говоря, при интересной задаче постановка конкурса не блещет качеством, мягко говоря. Если хотите научиться конкурсы нормально проводить, почитайте как вот тут делают: russianaicup.ru


        1. feldgendler
          15.11.2015 23:48

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


      1. zBit
        15.11.2015 11:42
        +3

        Вам нужно написать модуль для Node.js, экспортирующий одну функцию
        Модуль, экспортирующий одну функцию, а не модуль, экспортирующий объект с одним методом! В задании одно, в комментариях другое. Я понял это как
        module.exports = function() {};
        


        1. feldgendler
          15.11.2015 23:49

          Мы уже решили принимать модули, сделанные и так, и эдак, раз возникли разночтения.


  1. 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*			match
    


    1. kazmiruk
      14.11.2015 21:19

      ? это не 0 или 1 символ, а строго 1 символ, поэтому первая строка и не подходит


  1. dangreen
    14.11.2015 21:07
    -1

    А входящие данные это POJO объекты?


  1. zBit
    14.11.2015 23:23
    +2

    Задание кажется каким-то не полным. Мне кажется не хватает тестовых данных и описания метода замера производительности.


    1. arusakov
      15.11.2015 00:36
      +1

      Поддерживаю, опишите хотя бы в общих чертах то, как будет производится замер. А лучше выложите ваш эталонный код для замера в opensource.


      1. zBit
        15.11.2015 01:50

        Если выложить реализацию в паблик, то остаётся только оптимизировать код, это несколько упрощает задачу. Но описать как будет определяться «самая быстрая реализация» было бы не лишним. Какие критерии будут учитываться (время выполнения, потребление памяти, количество операций, визуальный осмотр ващего гуру JS или что-нибудь ещё)?


        1. arusakov
          15.11.2015 02:53

          Не эталонную реализацию, а некоторое подобие фреймворка, с помощью которого будут производиться замеры производительности. Я это имел в виду.


      1. feldgendler
        15.11.2015 04:32
        +2

        Мы не хотим оптимизации под бенчмарк. Скажу только, что характеристики тестовых данных будут напоминать реалии электронной почты.


  1. Majestio
    15.11.2015 00:14
    -3

    Аукцион фриланса без гарантий! Лихо замутили.


  1. zBit
    15.11.2015 02:41
    +1

    Все строковые значения во входных данных непустые и содержат только символы ASCII в диапазоне от 0x20 до 0x7F включительно.
    www.bluesock.org/~willg/dev/ascii.html
    0x7F — это же del…
    И вы уверены, что прямо во всех строковых значениях во входных данных (в т.ч. и в адресах почтовых ящиков) можно использовать все эти символы?
    И как быть с ситуацией когда нужно в правилах указать наличие символа * как этого символа, а не как эквивалент любого количества любых символов? Если такие случаи надо учитывать, то реализация будет сложнее и как следствие медленнее.

    Вывод: нужно выложить «тесты на корректность», которые вы будете гонять. Вы облегчите этим себе жизнь. Или хотя бы пачку входных данных, которые используются в «тестах на корректность».


    1. Lennotoecom
      15.11.2015 03:32

      Да, действительно, эталонная проверочная балалайка на сайте (при использовании всех символов),
      при попытке поиска строки «a*b», при входных значениях «a*b» и «abb» естесственно отбирает оба.
      Так как "*" является абсолютно легитимным символом для адреса по условию задачи.

      Так что вы определили неисправность в их алгоритме и проверочной балалайке.

      похоже грядет апдейт по возможным символам в адресе до формы вида [.-@0-9a-zA-Z]


      1. feldgendler
        15.11.2015 04:37

        Никакой неисправности. Так и должно быть. Ваш код должен вести себя так же.


    1. feldgendler
      15.11.2015 04:36

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

      Символы * и? как таковые невозможно задать в маске. Такой вот несовершенный язык для фильтров.

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


      1. u1d
        15.11.2015 10:29
        +1

        А если эталонная реализация возвращает 502 или 504 на валидных по правилам аргументах, то на тесте (проверке корректности/производительности) таких аргументов точно не будет дано?


        1. feldgendler
          15.11.2015 23:46

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


  1. gandjustas
    15.11.2015 03:37

    Пустая строка в правилах from и to эквивалентна отсутствию параметра или обязательно падать при этом значении?


    1. feldgendler
      15.11.2015 04:40

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


      1. dangreen
        15.11.2015 10:40

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


        1. feldgendler
          15.11.2015 23:50

          В условии сказано:

          Эта [эталонная] реализация также строго проверяет корректность входных значений (от Вашего решения проверки входных данных не требуется).


  1. ionicman
    15.11.2015 10:58
    +6

    Господа, я вот искренне не понимаю негодующих.

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

    Но ведь никто не заставляет? Ну не нравится — можно просто пройти мимо-же, нет?

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

    Выиграю я или нет — главное я провел пару часов интересно и напрягая мозг. Я написал так, как понял и это меня вполне устраивает. ИМХО вполне нормально и понятно изложено, все остальное можно проверить на эталоне.

    Что за снобизм и перфекционизм?

    Иногда конкурс тем и интересен, что некоторое надо додумывать. Мало того, умолчание можно использовать в свою пользу (тут вон даже намеки были :)).

    Мне здесь тоже кое-что не нравится (отсутствие пакетов эталонных данных и данные о том, что модуль хотя-бы нормально запустился на тестовом стэнде — первое решается элементарно — я написал генератор и успокоился, ну а на второе — на все воля Аллаха, что делать-то :)), но это не повод наезжать на организаторов и уж тем более не повод не поучаствовать. Нормальная такая разминка для мозга.


    1. vintage
      15.11.2015 11:20

      Да и задача всё же не очень интересная. Вообще, по результатам конкурса было бы интересно почитать аналитику — кто как решал и какой профит от этого получил. Позапрошлая задача с сериализацией моментов, например, привела в итоге к написанию полезной библиотеки http://habrahabr.ru/post/263041/ где используется наиболее быстрая реализация без использования eval. C eval и код не красивый получается и доступен он не во всех окружениях, зато позволяет заинлайнить весь алгоритм в одну функцию и быстро применять её к данным.


    1. DYefimov
      15.11.2015 12:23
      -1

      ф


    1. DYefimov
      15.11.2015 12:28

      Да этот конкус выйденого яйца не стоит.
      Об этом и весь спич.
      Пойди туда не зная куда…

      Я, может, категоричен, но хочется самому приложиться.
      Но есть одно «но»: в реальных системах не оптимизируют функции, а оптимизируют подход.
      Назвали бы свой конкурс «оптимизация под v8», ни у кого бы вопросов не возникло.


  1. topa
    15.11.2015 11:47
    +8

    Если кому лень собирать данные для замеров производительности собственной реализации, я хочу поделиться своими:
    примерно 50 тыс сообщений, взял первую попавшуюся базу адресов из поисковика и наугад соединил их в пары. Имена у них тривиальные, типа msg15.
    примерно 500 правил, которые были сделаны из случайно выбранных электронных адресов путём замены нескольких символов на * или?

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


    1. zBit
      15.11.2015 12:23
      +1

      Спасибо!
      Жаль, что эталонная реализация может принимать только 10 сообщений, разницу между сообщениями и правилами как в реальности (несколько порядоков) они не учли=(


      1. feldgendler
        15.11.2015 23:53

        Эталонная реализация предназначена только для проверки корректности, для чего лимита в 10 сообщений даже многовато.


    1. cL1Nk3r
      15.11.2015 13:00

      У кого какие результаты на этих данных?
      Моя самая элементарная реализация (просто чтобы работало) показала 0.26 ops/sec используя benchmark.js


      1. topa
        15.11.2015 13:27

        Сравнивать на разных машинах несколько некорректно и весьма нерепрезентативно)
        Но это даёт хоть какой-то уровень, на который можно ориентироваться.

        На моем Core i5-2450M 2.5GHz первая пришедшая на ум реализация выполняет обработку примерно за 1,4 сек. (0.72 ops/sec по замерам с benchmark.js)


      1. gandjustas
        15.11.2015 20:00

        2,2 сек
        node 4.2.2, i7-2630QM


    1. xytop
      15.11.2015 13:12

      мой macpro за 30 секунд все обработал и ответ вернул. У кого еще какие результаты?


    1. KingOfNothing
      15.11.2015 14:49
      +3

      1. xytop
        15.11.2015 15:05

        сколько обрабатывается по времени, и какое железо?


        1. KingOfNothing
          15.11.2015 15:19

          Intel Core i7-4710HQ CPU @ 2.50GHz ? 8

          9s, node 4.2.2


          1. xytop
            15.11.2015 15:22

            у меня на 5й ноде за 14.5s
            Проц тоже i7 (2 GHz Intel Core i7) но мобильный и 4 ядра…
            Надо придумать как организовать централизованное тестирование и при этом не слить свой код )


            1. KingOfNothing
              15.11.2015 15:25

              кол-во ядер вряд ли влияет. У меня тоже мобильный — ноут.


            1. OLS
              15.11.2015 21:22

              Нужно просто создать эталонную нагрузку, запустить ее на своем ПК для сравнения коэффициента быстродействия с чужими, а потом при тестировании на своем компьютере делить/умножать на выясненный коэффициент.


        1. gandjustas
          15.11.2015 20:01

          5,5 сек
          node 4.2.2, i7-2630QM


      1. gandjustas
        15.11.2015 18:24

        Набор неадекватный, слишком много правил "*". Я не думаю что тестовый набор правил будет так выглядеть.


        1. OLS
          15.11.2015 21:30

          Более того я бы предположил, что "*" будут закрываться целые домены либо вся структура поддоменов


  1. zBit
    15.11.2015 21:53

    А с какими параметрами нода запускаться будет при тестировании производительности?


    1. feldgendler
      15.11.2015 23:54

      Всё по умолчанию.


  1. 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 и найти себя в логе. При этом данные получаются полностью анонимными.

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


    1. gandjustas
      16.11.2015 13:24

      Толку от такой таблицы не будет без эталонных тестов. Причем тестов на корректность, а не на скорость.


  1. gandjustas
    16.11.2015 13:26
    +1

    Товарищи организаторы,
    1) Дайте плз тесты на корректность, включая обработку ошибок
    2) Уточните по входным данным: будут ли from и to в сообщениях всегда содержать символ @? будут ли правила, хотябы в большинстве случаев, содержать @?


    1. feldgendler
      16.11.2015 13:34
      +2

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

      В остальном задание достаточно специфицированно для того, чтобы сделать его правильно. На олимпиадах по программированию типа ACM тесты тоже не дают.

      Никаких гарантий насчёт символа @ нет. С точки зрения этой задачи в этом символе нет ничего особенного, может встретиться несколько раз, может ни одного.


      1. Ag47
        18.11.2015 00:53
        +2

        На олимпиадах по программированию типа ACM тесты тоже не дают.


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

        P.S.
        Конкурс отличный, жалею что предыдущие ваши пропустил, отличная разрядка.


        1. feldgendler
          18.11.2015 03:38

          Здесь в комментариях уже начали обмениваться тестами. Мне кажется, это отличная идея.


  1. Aquahawk
    16.11.2015 15:46

    Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите такую же сумму, как и он.

    Выше в комментариях уже заметили, но я уточню отдельно. Если 10 человек шлют кому-то ссылку на этот конкурс, поставив ваш адрес в CC, и этот человек займёт призовое место, то каждый из этих 10 получит столько же?


    1. feldgendler
      16.11.2015 15:58

      Первый получит.


  1. topa
    16.11.2015 20:24
    +4

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

    Несколько тестов я разместил на гитхабе. Буду рад, если кто-нибудь найдет и добавит туда еще хитрые комбинации входных данных.


    1. feldgendler
      16.11.2015 20:26

      Интересная инициатива! Хотя правила и запрещают публикацию своего решения до окончания соревнования, в них ничего не сказано о других видах сотрудничества.


    1. Alex_At_Net
      17.11.2015 03:32

      Вот еще тестов немного :) pastebin.com/C6KMNsvt


  1. 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»? У вас это упоминается, но просто, может они все-таки коммутативны=)


    1. feldgendler
      18.11.2015 03:46

      1. Пожалуйста, вставляйте код сторонних библиотек, если это не нарушает их лицензии. Запрет на require обеспечивает, что решения не будут пытаться доступаться к файлам, сети и вообще нести в себе сюрпризы. Мы будем запускать его в виртуальной машине Node.js, где require вообще не будет.

      2 и 3. Если надо, лимит по памяти будем менять. Мы ещё не определились с размером входных данных. Планируем выбрать такой размер, на котором все присланные программы будут вписываться в имеющуюся в нашем распоряжении память, кроме, разве что, намеренно пытающихся съесть всю память. В общем, считайте, что у Вас хватит памяти на любые разумные предвычисления, кэши и т.п.

      4. Да, порядок действий важен.


  1. degorov
    19.11.2015 13:08

    Тут уже спрашивали, но всё же повторюсь. Не могли бы Вы озвучить характеристики набора? Просто по сути задачи, где повторяющихся наборов from-to половина, и где таких повторений (практически) нет — это РАЗНЫЕ задачи. Если неизвестны характеристики набора входных данных, то победа сводится к УГАДЫВАНИЮ характеристик Вашего конкретного тестового набора, а не к построению самого хитрого алгоритма ;)

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

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

    Разные задачи — разные решения…


    1. feldgendler
      19.11.2015 13:11
      -2

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


      1. Duha666
        19.11.2015 14:05
        +2

        И поэтому может быть сколько угодно "@" и других символов?


      1. zBit
        19.11.2015 14:55

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


        1. feldgendler
          19.11.2015 15:00

          Будет и спам, и нормальная переписка.


        1. ionicman
          19.11.2015 15:13
          +1

          Если не придираться, и чуток подумать — тестовый генератор пишется за 3 минуты.

          По-моему организатор конкурса непрозрачно намекнул в самом начале — СТАНДАРТНЫЙ почтовый ящик. ОБЫЧНЫЙ, не от техподдержки или кого-то еще. Так сложно распределение посчитать?

          Дайте тестовые данные и скажите какое распределение...
          Так может сразу алгоритм дать? :) А тогда где головой-то думать?

          Поэкспериментировать чуток — и все понятно будет. Я вот сегодня время сократил в два раза у алгоритма, прикинув статистическое распределение. А я не могу про себя сказать, что мегамозг :D

          P.S. Пока Вы тут жалуетесь, народ пишет и молчит — наверное это правильно?
          Из цикла "Пока Вы спите, Ваш враг качается!" :))


          1. degorov
            19.11.2015 15:23

            Да, и алгоритмов той же сортировки придумано уже десятки. А надо было просто прикинуть СТАНДАРТНЫЙ набор данных, ну ОБЫЧНЫЙ и посчитать распределение…

            >Я вот сегодня время сократил в два раза у алгоритма, прикинув статистическое распределение.
            А у меня есть два варианта скрипта, один из которых быстрей на этом наборе данных, а другой быстрей на вот этом. И я точно могу написать третий вариант, который будет быстрей на моём личном почтовом ящике…


            1. ionicman
              19.11.2015 15:29

              Тестовый набор неизвестен, я бы на самом универсальном остановился.


          1. zBit
            19.11.2015 15:54

            Я всего лишь отметил, что никто не знает с вероятностью 100% о том как выглядит почтовый ящик типичного пользователя :) И я не считаю свой ящик — ящиком типичного пользователя :)
            У меня скрипт с тестовыми данными выложенными выше (http://habrahabr.ru/company/hola/blog/270847/#comment_8654795) выполняется за чуть больше секунды на i5-4570 (3.2GHz).
            Хотя я думал над тем, что если знать как будет выглядеть тестовый набор данных, то можно будет ещё что-нибудь придумать и оптимизировать алгоритм ещё лучше.


            1. ionicman
              19.11.2015 15:58

              Оптимизировать под определенные данные, если данные могут быть другими — всегда плохо.

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

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


              1. zBit
                19.11.2015 16:04

                Согласен, цифра бесполезная:) Забыл затолкать всё что после первого абзаца в спойлер…
                Была бы ещё эта статистика, мне известна… Мне кажется, что если какой-то анализ входных данных проводить, то можно получить вариант медленнее, чем один алгоритм ориентированный на универсальный набор данных. Надо будет попробовать:)


              1. feldgendler
                19.11.2015 16:31

                Я бы плюсанул, если бы мне карму не слили. Не нравятся людям мои конкурсы, очевидно.

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


                1. zBit
                  19.11.2015 16:56

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


                  1. ionicman
                    19.11.2015 17:15
                    +1

                    Вот представьте себе — Вы работает в некой фирме девелопом (например).

                    Каким-то образом в фирме решают что есть деньги на конкурс (for fun, сверху или как-нибудь еще, теоретически это может быть и попытка хэдхантинга).

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

                    Конечно, если Вы уровнем mailru/яши — можно запилить команду, которая все что Вы написали забацает. При этом прожрет денег чуть ли не больше, чем выделено на конкурс + это время — мало того, даже в больших компаниях тоже все не гладко — вспомните конкурс на хабре от мейлру, где победили боты.

                    Есть вариант сделать это все на энтузиазме — но тут вопрос уже конкретно в компании и человеке. Да и редко сейчас он встречается.
                    Вот Вы, например, посвятите свое нерабочее время своей компании бесплатно? :)

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

                    Обычно на вопрос "А давай ты проведешь конкурс у нас на фирме, на него выделили деньги!" большинство нормальных людей, анализируя размер предстоящего геморроя ответят "А давай нет!" :)

                    Поэтому, ИМХО, надо радоваться, что конкурс вообще состоялся и в нем можно принять участие. Для меня — это самое главное.

                    А придраться можно до всего, как и хаять.

                    Я, если честно, вообще все это нытье не понимаю. Если я вижу, что меня что-то не устраивает, чего можно избежать просто пройдя мимо — я пройду мимо. И уж никак не буду кидаться на баррикады «В интернете опять кто-то не прав».

                    Мира Вам, господа! Относитесь ко всему легче и добрее.


                    1. zBit
                      19.11.2015 17:42
                      +1

                      Я всего лишь написал как я бы сделал :) Я перфекционист, поэтому я не буду объявлять о конкурсе пока не подготовлю всё для него и не буду уверен, что это будет удобно.

                      Согласитесь, это соревнование и как в любом соревновании надо примерно понимать где ты находишься. Когда спортсмены соревнуются в беге или прыжках в длину/высоту/глубину, устраивают гонки и ещё много в чём соревнуются, то они знают примерно где они находятся в данный момент времени в турнирной таблице (за исключением тех видов спорта где есть очередь и вы не первый кандидат). Вы бы пошли на соревнования по бегу если бы каждого из участников загоняли на стадион по очереди и заставляли бегать на время, при этом никто кроме судьи не видит и не знает о результатах и сообщает о том кто выиграл через неделю, например? Я бы не пошёл, т.к. в такой реализации нет прозрачности, нет уверенности в том, что всё проходит честно. Я думаю вы согласитесь, что намного приятнее бегать всем вместе, чтобы знать когда и на сколько нужно поднажать, чтобы вырваться вперёд.

                      Только не пишите о том, что я ною или придираюсь! :) Я тоже рад, что конкурс вообще есть, но был бы ещё рад, если бы его организовали лучшим образом. Я всего лишь пишу о том как сделал бы я на их месте и это не значит, что у текущей реализации конкурса всё плохо, может у организаторов другое представление о соревнованиях, которым они не делятся с участниками конкурса (и всем остальным миром), отсюда и негодование/непонимание/возмущения и т.п.

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

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


                  1. vintage
                    19.11.2015 17:35

                    Ну, после сливания кармы хорошей организации конкурса тем более ждать не стоит как и новых статей :-)


    1. gwer
      19.11.2015 14:07

      Ну а чего вы на рандомные данные смотрите, когда сказано, что будет типичное содержимое почтового ящика?

      Типичное содержимое в моем понимании — это однозначное повторение в каждом письме одного из немногочисленных адресов пользователя и нередкое повторение прочих адресов: уведомления от соцсетей, сайтов, переписки и с кем-либо. Хотя, конечно, есть там и адреса, появляющиеся единожды, те же спамеры могут этим разбавить содержимое.


      1. degorov
        19.11.2015 14:21

        А в моём понимании какой-нибудь работник службы техподдержки тоже является типичным пользователем и у него/неё там будет адресов тонны всяких разных и куча уникальных писем. Свой личный ящик я уже давно распарсил и да, он совпадает с Вашим пониманием, но вопрос о его ТИПИЧНОСТИ лично для меня останется открытым по крайней мере до тех пор, пока не будет проведён статистически значимый анализ нужного количества (сотен, тысяч, миллионов?) содержимого других почтовых ящиков людей с разной половой принадлежностью, профессией, возрастом, вероисповеданием итд итп :)

        С моей точки зрения было бы более правильно вообще не скрывать тестовый набор, но явно запретить правилами указание в коде любых констант хоть строковых, хоть числовых, направленных на оптимизацию под бенчмарк. А попробовать пореализовывать самому разные варианты оптимизаций и повключать/поотключать их для получения лучшего результата, как по мне, так это как раз весьма спортивно и интересно. Любые задачи в реальной работе программиста — это всегда оптимизация под бенчмарк в этом смысле.

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


        1. gwer
          19.11.2015 14:30
          -1

          Запрещать использование тех же констант — затея какая-то нелепая. Проще выложить предварительный тестовый набор, а итоги подводить на аналогичном: другие ящики, другие маски, но схожие характеристики.


          1. degorov
            19.11.2015 14:35

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

            Или разрешить присылать несколько вариантов скриптов, в зачёт идёт лучший результат, а не последний. Так как тестирование всё равно автоматическое — не вижу в этом вообще никакой проблемы.


          1. degorov
            19.11.2015 14:40

            Аналогичный по характеристикам набор — тоже вполне себе вариант при условии повторения ВСЕХ характеристик, а они совсем не ограничиваются повторением в письмах. Я бы даже сказал, что создание двух действительно схожих наборов является более сложной задачей, чем собственно, все те решения, что мы тут все изобретаем. Потому что для этого нужно знать все возможные оптимизации и подогнать/не подогнать под них всех одинаково :)