Компания
56,27
рейтинг
13 ноября 2015 в 19:10

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

UPDATE: Опубликованы итоги конкурса.

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

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

Мы ищем талантливых программистов, поэтому авторы интересных решений будут приглашены на собеседования.



Правила


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

Условия конкурса на английском языке размещены на нашем сайте. Ниже — перевод на русский язык.

  • Отправляйте решения на challengejs+habrahabr@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.

Желаем удачи всем участникам!
Автор: @feldgendler
Hola
рейтинг 56,27

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

  • +3
    при отправке пустого POST запроса с Content-Type: application/json на hola.org/challenge_mail_filter/reference в ответ 502 Bad Gateway
    • –9
      В теле запроса должен быть корректный JSON.
      • +4
        И тем не менее, на неверный запрос сервер должен возвращать 4** ошибку, а не 5**.
        • –22
          Мы парсим JSON на уровне express middleware, и было неудобно для этого одного урла делать исключение. Вам же это не сильно мешает пользоваться эталонной реализацией? Ну вот и славно.
          • +28
            Если Вы подозреваете, что эталонная реализация выдаёт неверный ответ для тех или иных входных данных, пожалуйста, сообщите нам.

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

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

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

            Какие правила ещё реализовать было неудобно? Может и выплаты неудобно будет делать?
  • +3
    Какие регулярки быстрее — компилируемые или нет? =)
    > условие сформулировано предельно однозначно
    > победит самое быстрое
    Чтобы однозначно сформулировать, что значит быстрый, надо описать, как вы её хотите использовать:
    1. 2-3 фильтра, 1М сообщений
    2. 1M фильтров, 100 сообщений
    3. повторное использование с большей вероятностью с теми же фильтрами или с разными
    • 0
      Повторного использования не будет, перед каждым запуском мы будем загружать Ваш модуль в свежей виртуальной машине. Сообщений будет на несколько порядков больше, чем фильтров, как это и бывает в реальных почтовых системах.
      • НЛО прилетело и опубликовало эту надпись здесь
        • –3
          Я понимаю, о чём Вы. Вы можете сделать все оптимизации, которые задумали, в рамках нынешнего условия. Обработайте правила как хотите и применяйте их затем к письмам. Писем будет много.
          • +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
              Писем будет на несколько порядков больше, чем правил. Это всё, что я могу пока сказать.
              • +9
                Задайте порядок в 10й системе того и другого, и все будут счастливы — это всё, что я хотел спросить.
            • НЛО прилетело и опубликовало эту надпись здесь
              • –5
                Вооооот!
                Жму руку, мысль доехала, как я смотрю.
                К сожалению, я немного набухался в данный момент — отвечу завтра на трезвую.
                • +2
                  Ладно, ладно — хватит минусовать.
                  По делу.
                  Своим постом выше, я пытался сказать, что (при нормальной реализации) затраты на «поддержание» данных намного меньше (место/время), чем то, что предложили нам в этом задании.
              • 0
                Да, замечу, что регулярки не панацея — на JS можно делать вещи намного быстрее регулярок. Была бы задача.
  • +4
    Сторонние библиотеки использовать запрещено, все велосипеды своими руками. Правильно?
    • –4
      Да.
  • +3
    Хорошо было бы иметь страницу, куда можно было бы отправлять свое решение и оно бы подсчитывало скорость и добавляло это в какую-нибудь онлайн таблицу результатов. Это хорошо стимулирует на оптимизацию :)
    • –4
      Подумаем над тем, чтобы сделать так на следующем конкурсе.
  • +13
    Как выиграть 3000 USD?
    1. Создаешь липовую почту.
    2. Отправляешь себе приглашение на настояющую почту.
    3. Участвуешь в конкурсе и выигрываешь 1500 USD.
    4…
    5. Profit!
    • +19
      Имеет смысл переслать это письмо туда-обратно много раз, чтобы в каналах образовалась стоячая волна из долларов.
    • 0
      Предположим, что у тебя шанс выиграть 1:100, но ты знаешь человека, у которого такой шанс намного выше =))
    • +1
      Как выиграть 6000 USD?
      1. Создаёшь три липовых ящика.
      2. Отправляешь приглашения на три других ящика.
      3. Пишешь для конкурса три крутых реализации.
      4.…
      5. Profit!

      P.S. Вообще, я что-то не очень верю в эти конкурсы. Кажется, были уже прецеденты.
  • 0
    Пожалуйста подскажите если позволяют правила,
    какие минимальные параметры теста нужно использовать при отладке,
    количество messages, количество rules, максимальное время выполнения при таких условиях,
    чтобы, так сказать, чувствовать где планка.

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

        т.е. память ограничена? :)
        • –2
          Память ограничена у любого физического компьютера, на котором мы могли бы запускать тесты. Мы не хотим, чтобы память была ограничивающим фактором, и постараемся сделать так, чтобы её всем хватило.
  • +2
    А подтверждение, что письмо у Вас — придет?
  • –5
    Вам нужно написать модуль для Node.js

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

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

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

      И все.
      • –3
        Решение должно быть на чистом JS.

        В случае если код планируется гонять на сервере, и он критичен к скорости, то гораздо производительнее будет сделать нативный модуль.
        А в такой постановке устраивать игрища с js имхо странно.
        • +2
          Странно — да
          Весело — да :)
          Вопрос скорее всего вообще не в js :D
        • +2
          Ясно же, что конкурс нужен для поиска JS-программистов, а не прикладного решения задачи фильтрации.
  • +3
    Укажите, пожалуйста, жадность * в маске. А то непонятно, «aba» подходит "*a*b*" или нет.
    • +1
      Вы можете проверить это с помощью нашей эталонной реализации.
  • 0
    А можно список имейлов (хотя бы тысяч 50) что бы тесты погонять? Или это очень нагло и надо искать самому? :(
    • 0
      У вас же, наверное, в почтовом ящике много писем.
  • 0
    М… я, конечно, не гений-алгоритмист, но чем эта задача отличается от простой задачи на проверку соответствия строки маске? Тем, что придётся повторить эту операцию от M*N до 2*M*N раз, где M — количество писем, а N — количество правил? Всё равно же придётся каждое с каждым проверять. Ну, мемоизацию разве что прикрутить, на случай одинаковых адресов.
    • +1
      наверно, это задание скорее на знание того, как оптимизировать js-код для v8, а не про алгоритмическую оптимизацию.
    • 0
      Надеюсь, мы увидим наглядный ответ на этот вопрос при подведении итогов, когда все решения будут опубликованы.
  • +1
    Странно что паттерн для адреса почты чувствителен к регистру, в эталонной реализации.
  • 0
    Не нашёл описания паттернов.
    • +1
      Маски регистрозависимые; символу * в маске удовлетворяет любое число (0 или более) любых символов, а символу? — один любой символ.
  • 0
    Пытаюсь протестироваться у вас на сайте по ссылке через ajax,
    все время получаю ошибку
    Response to preflight request doesn't pass access control check: No 'Access-Control-Allow-Origin' header is present on the requested resource.
    


    : ( простите за нубский вопрос
    • 0
      Я сейчас проверил, эталонная реализация работает. Проверяйте, как именно Вы делаете запрос.
    • 0
      Делайте запрос с помощью curl или wget или еще чего, из браузера у вас это не получится.
      • 0
        спасибо :)
  • 0
    ? — один любой символ


    Ноль либо один или точно один?
    • 0
      Ровно один
    • 0
      Вы можете воспользоваться эталонной реализацией, чтобы выяснить это.
  • 0
    Есть предложение
    Брать не последний лучший результат, а лучший результат последних двух.
    Причина в том, что частота встречаемости почтовых адресов не известна. Или дать больше информации.
  • 0
    А можно изменять входящие объекты?
    • 0
      Можно.
  • +3
    Вопрос по поводу написания модуля:
    Вам нужно написать модуль для Node.js, экспортирующий одну функцию

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

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

    ?

    В первом варианте экспортируется функция, а во втором объект с этой функцией. Как правильно сделать?
    • +1
      module.exports
    • –1
      Второе.
      • +3
        А может вы это в правила внесёте официально? Ибо уже наблюдаем людей введённых в заблуждение(см выше). Я всё ещё думаю участвовать или нет, и честно говоря, при интересной задаче постановка конкурса не блещет качеством, мягко говоря. Если хотите научиться конкурсы нормально проводить, почитайте как вот тут делают: russianaicup.ru
        • 0
          После некоторого размышления мы решили принимать решения, написанные и так, и эдак (касательно способа экспорта функции), поскольку нет никаких проблем научить нашу тестилку понимать оба варианта.
      • +3
        Вам нужно написать модуль для Node.js, экспортирующий одну функцию
        Модуль, экспортирующий одну функцию, а не модуль, экспортирующий объект с одним методом! В задании одно, в комментариях другое. Я понял это как
        module.exports = function() {};
        
        • 0
          Мы уже решили принимать модули, сделанные и так, и эдак, раз возникли разночтения.
  • 0
    Как работают эталонные регэкспы:
    '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
    
    • 0
      ? это не 0 или 1 символ, а строго 1 символ, поэтому первая строка и не подходит
  • –1
    А входящие данные это POJO объекты?
  • +2
    Задание кажется каким-то не полным. Мне кажется не хватает тестовых данных и описания метода замера производительности.
    • +1
      Поддерживаю, опишите хотя бы в общих чертах то, как будет производится замер. А лучше выложите ваш эталонный код для замера в opensource.
      • 0
        Если выложить реализацию в паблик, то остаётся только оптимизировать код, это несколько упрощает задачу. Но описать как будет определяться «самая быстрая реализация» было бы не лишним. Какие критерии будут учитываться (время выполнения, потребление памяти, количество операций, визуальный осмотр ващего гуру JS или что-нибудь ещё)?
        • 0
          Не эталонную реализацию, а некоторое подобие фреймворка, с помощью которого будут производиться замеры производительности. Я это имел в виду.
      • +2
        Мы не хотим оптимизации под бенчмарк. Скажу только, что характеристики тестовых данных будут напоминать реалии электронной почты.
  • –3
    Аукцион фриланса без гарантий! Лихо замутили.
  • +1
    Все строковые значения во входных данных непустые и содержат только символы ASCII в диапазоне от 0x20 до 0x7F включительно.
    www.bluesock.org/~willg/dev/ascii.html
    0x7F — это же del…
    И вы уверены, что прямо во всех строковых значениях во входных данных (в т.ч. и в адресах почтовых ящиков) можно использовать все эти символы?
    И как быть с ситуацией когда нужно в правилах указать наличие символа * как этого символа, а не как эквивалент любого количества любых символов? Если такие случаи надо учитывать, то реализация будет сложнее и как следствие медленнее.

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

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

      похоже грядет апдейт по возможным символам в адресе до формы вида [.-@0-9a-zA-Z]
      • 0
        Никакой неисправности. Так и должно быть. Ваш код должен вести себя так же.
    • 0
      В данном случае неважно, что можно, а что нельзя использовать в реальной электронной почте. Ваша функция должна быть готова к появлению в том числе символа 0x7F.

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

      Если Вы сомневаетесь в том, допустимы ли те или иные исходные данные, воспользуйтесь эталонной реализацией. Если она отвечает 200 OK, то Ваш код должен быть готов к таким значениям аргументов, и должен выдавать то, что вернула эталонная реализация.
      • +1
        А если эталонная реализация возвращает 502 или 504 на валидных по правилам аргументах, то на тесте (проверке корректности/производительности) таких аргументов точно не будет дано?
        • 0
          Это означает, что у нас проблемы на сервере, попробуйте ещё раз через некоторое время. Если проблемы продолжаются, пришлите мне входные данные.
  • 0
    Пустая строка в правилах from и to эквивалентна отсутствию параметра или обязательно падать при этом значении?
    • 0
      Пустая строка недопустима и поэтому в наших тестах на корректность и производительность не попадётся. Неважно, падает ли Ваш код при таких входных данных, потому что мы это тестировать не будем.
      • 0
        Но в эталонной реализации пустые строки отлавливаются. То есть нам их ловить не обязательно? Так же эталонная реализация проверяет объекты на посторонние свойства, но в правилах об этом ничего, то есть и это нам можно не реализовывать?
        • 0
          В условии сказано:

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

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

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

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

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

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

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

    Мне здесь тоже кое-что не нравится (отсутствие пакетов эталонных данных и данные о том, что модуль хотя-бы нормально запустился на тестовом стэнде — первое решается элементарно — я написал генератор и успокоился, ну а на второе — на все воля Аллаха, что делать-то :)), но это не повод наезжать на организаторов и уж тем более не повод не поучаствовать. Нормальная такая разминка для мозга.
    • 0
      Да и задача всё же не очень интересная. Вообще, по результатам конкурса было бы интересно почитать аналитику — кто как решал и какой профит от этого получил. Позапрошлая задача с сериализацией моментов, например, привела в итоге к написанию полезной библиотеки http://habrahabr.ru/post/263041/ где используется наиболее быстрая реализация без использования eval. C eval и код не красивый получается и доступен он не во всех окружениях, зато позволяет заинлайнить весь алгоритм в одну функцию и быстро применять её к данным.
    • –1
      ф
    • 0
      Да этот конкус выйденого яйца не стоит.
      Об этом и весь спич.
      Пойди туда не зная куда…

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

    Сохранена разница в 2 порядка между числом сообщений и числом правил, как и указывалось выше в коментах.
    Правила фильтрации в этих данных бестолковые, составленные случайным образом. Правильного ответа (от референсной модели) на эти данные нет, я готовил их исключительно для замеров производительности. При желании можете сами их собрать.
    • +1
      Спасибо!
      Жаль, что эталонная реализация может принимать только 10 сообщений, разницу между сообщениями и правилами как в реальности (несколько порядоков) они не учли=(
      • 0
        Эталонная реализация предназначена только для проверки корректности, для чего лимита в 10 сообщений даже многовато.
    • 0
      У кого какие результаты на этих данных?
      Моя самая элементарная реализация (просто чтобы работало) показала 0.26 ops/sec используя benchmark.js
      • 0
        Сравнивать на разных машинах несколько некорректно и весьма нерепрезентативно)
        Но это даёт хоть какой-то уровень, на который можно ориентироваться.

        На моем Core i5-2450M 2.5GHz первая пришедшая на ум реализация выполняет обработку примерно за 1,4 сек. (0.72 ops/sec по замерам с benchmark.js)
      • 0
        2,2 сек
        node 4.2.2, i7-2630QM
    • 0
      мой macpro за 30 секунд все обработал и ответ вернул. У кого еще какие результаты?
    • +3
      У меня тут 100000/1000 www.dropbox.com/s/5lu2gdzn68xecx0/test1.json?dl=0
      • 0
        сколько обрабатывается по времени, и какое железо?
        • 0
          Intel Core i7-4710HQ CPU @ 2.50GHz × 8

          9s, node 4.2.2
          • 0
            у меня на 5й ноде за 14.5s
            Проц тоже i7 (2 GHz Intel Core i7) но мобильный и 4 ядра…
            Надо придумать как организовать централизованное тестирование и при этом не слить свой код )
            • 0
              кол-во ядер вряд ли влияет. У меня тоже мобильный — ноут.
            • 0
              Нужно просто создать эталонную нагрузку, запустить ее на своем ПК для сравнения коэффициента быстродействия с чужими, а потом при тестировании на своем компьютере делить/умножать на выясненный коэффициент.
        • 0
          5,5 сек
          node 4.2.2, i7-2630QM
      • 0
        Набор неадекватный, слишком много правил "*". Я не думаю что тестовый набор правил будет так выглядеть.
        • 0
          Более того я бы предположил, что "*" будут закрываться целые домены либо вся структура поддоменов
  • 0
    А с какими параметрами нода запускаться будет при тестировании производительности?
    • 0
      Всё по умолчанию.
  • +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 и найти себя в логе. При этом данные получаются полностью анонимными.

    А особо интересующиеся, я уверен, через несколько часов сформируют и турнирную таблицу, обновляющуюся и отсортированную по убыванию длительности исполнения кода.
    • 0
      Толку от такой таблицы не будет без эталонных тестов. Причем тестов на корректность, а не на скорость.
  • +1
    Товарищи организаторы,
    1) Дайте плз тесты на корректность, включая обработку ошибок
    2) Уточните по входным данным: будут ли from и to в сообщениях всегда содержать символ @? будут ли правила, хотябы в большинстве случаев, содержать @?
    • +2
      В условии сказано, что Ваша реализация не обязана проверять ошибки. Мы не будем тестировать её на некорректных входных данных.

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

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


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

        P.S.
        Конкурс отличный, жалею что предыдущие ваши пропустил, отличная разрядка.
        • 0
          Здесь в комментариях уже начали обмениваться тестами. Мне кажется, это отличная идея.
  • 0
    Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите такую же сумму, как и он.

    Выше в комментариях уже заметили, но я уточню отдельно. Если 10 человек шлют кому-то ссылку на этот конкурс, поставив ваш адрес в CC, и этот человек займёт призовое место, то каждый из этих 10 получит столько же?
    • 0
      Первый получит.
  • +4
    По поводу тестирования корректности функции. Предлагаю немного скооперироваться и подобрать некоторые тесты, которые должна проходить разработанная функция.

    Несколько тестов я разместил на гитхабе. Буду рад, если кто-нибудь найдет и добавит туда еще хитрые комбинации входных данных.
    • 0
      Интересная инициатива! Хотя правила и запрещают публикацию своего решения до окончания соревнования, в них ничего не сказано о других видах сотрудничества.
    • 0
      Вот еще тестов немного :) pastebin.com/C6KMNsvt
  • +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»? У вас это упоминается, но просто, может они все-таки коммутативны=)
    • 0
      1. Пожалуйста, вставляйте код сторонних библиотек, если это не нарушает их лицензии. Запрет на require обеспечивает, что решения не будут пытаться доступаться к файлам, сети и вообще нести в себе сюрпризы. Мы будем запускать его в виртуальной машине Node.js, где require вообще не будет.

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

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

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

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

    Разные задачи — разные решения…
    • –2
      Набор будет весьма похож на содержимое почтового ящика типичного пользователя.
      • +2
        И поэтому может быть сколько угодно "@" и других символов?
      • 0
        У всех почтовый ящик выглядит по-разному. Кто-то получает тоннами спам с разных адресов, а кто-то очень активно переписывается с несколькими людьми и не получает спам.
        • 0
          Будет и спам, и нормальная переписка.
        • +1
          Если не придираться, и чуток подумать — тестовый генератор пишется за 3 минуты.

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

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

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

          P.S. Пока Вы тут жалуетесь, народ пишет и молчит — наверное это правильно?
          Из цикла "Пока Вы спите, Ваш враг качается!" :))
          • 0
            Да, и алгоритмов той же сортировки придумано уже десятки. А надо было просто прикинуть СТАНДАРТНЫЙ набор данных, ну ОБЫЧНЫЙ и посчитать распределение…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


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

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


                        Спасибо, не надо нам такой работы, которую делает фрилансер за $300. Халтура обычно обходится не дешевле, а дороже нормальной работы, если учитывать ещё и затраты на разгребание. Скажем, представляете себе, какой хай поднялся бы здесь же, если бы измерялка неправильно измеряла?

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

                        Да, это всё преодолимо, но конкретно в этом случае мы решили делать тестирование полуавтоматическим. Это означает, что система тестирования будет в основном автоматической, но она будет запускаться под контролем человека, а не автоматически на сервере при засылке решения. Когда имеешь дело с такими хитрыми существами, как люди, то от мысли об автоматическом, без присмотра, запуске присланного кода, пусть даже в виртуальной машине, делается не по себе.
                  • 0
                    Ну, после сливания кармы хорошей организации конкурса тем более ждать не стоит как и новых статей :-)
                    • +4
                      Да нет, мне как-то всё равно. Ну забрали возможность голосовать за комментарии, значит, не буду за них голосовать. Лично моё самоуважение никак не связано с численными показателями на том или ином сайте.
                      • –1
                        Давайте всё же без лицемерия, хорошо? :-)
                        • +3
                          Ну вот конкретно Хабр для меня рабочий инструмент, которым я пользуюсь по заданию работодателя. Если бы от меня все отписались на Фейсбуке, меня бы это больше задело.
                          • –2
                            Мой комментарий касался исключительно ублюдочной механики кармы на хабре :-)

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

                            Я смотрю, кармы вам уже накидали и теперь вы сможете провести и следующий конкурс :-)
                            • +2
                              Я его и при карме 4.0 мог провести, так как возможность голосовать за комментарии для этого не критична. Поэтому и не понял, к чему относился Ваш комментарий, ведь статьи писать мне не запретили.
                              • –1
                                А, ну значит вам карму ещё и не сливали даже :-)
                                • 0
                                  Слили достаточно, чтобы не мог плюсовать комментарии, о чём и написал.
                  • +4
                    Я Вас уверяю, если бы это было сделано, были бы недовольны чем-нибудь другим. Ну там, что форма неудобная, или что условие задачи плохо написано, или просто что «заставляют» писать код забесплатно (да-да, были такие комментарии). Всем не угодишь. Мы делаем так, как хватает ресурсов, поскольку кроме организации конкурсов мы всё-таки занимаемся производством софта.
                    • 0
                      Да просто разрешите отправлять несколько решений и всё. При этом можно запретить одному человеку занимать несколько призовых мест. И всё. Это же не займёт никаких дополнительных ресурсов — какая разница сколько вариантов проверялке подсовывать? :) Тогда каждый сможет перебрать сколько хочет вариантов оптимизаций и можно будет с чистой совестью сказать, что у конкурсантов были все возможности подстроиться под любые данные, начиная от полного рандома, заканчивая вариантом, где 99% сообщений одинаковые…
                      • 0
                        Подумаем о таком. В предыдущем конкурсе, кстати, принималось к участию по нескольку вариантов от одного автора. В любом случае мы не будем менять правила уже идущего конкурса, поэтому все советы, которые здесь высказывают, мы принимаем как пищу для размышления к следующему разу.
                        • 0
                          Ок, будем ждать!
                • 0
                  Да отличный конкурс. Обычно вообще предлагается что-нибудь уровня сфоткаться с продуктом компании — нечего обсуждать даже ;)

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

                  Карму уже плюсовал, больше не могу…
                  • 0
                    У меня есть одна мысль, как можно сохранять эффективность при неизвестных частотных характеристиках во входных данных. Но высказывать её здесь, в глубокой ветке комментариев, было бы нечестно по отношению к остальным участникам. Если по окончанию конкурса я увижу у кого-то такой подход, то напишу об этом при подведении итогов.
                    • 0
                      Да и не в глубокой ветке тоже нечестно :) Если не увидите у участников этот подход, всё равно опишите, пожалуйста — это же самое интересное!
            • 0
              Я свой вариант тестировал на разных процессорах, очень сильно влияет объём кэша процессора, потом, но уже меньше, частота. Количество ядер ожидаемо вообще не влияет никак.
    • 0
      Ну а чего вы на рандомные данные смотрите, когда сказано, что будет типичное содержимое почтового ящика?

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

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

        При текущей постановке задачи я, вероятно, буду пытаться отрабатывать максимально общий случай и не буду рисковать подцеплять более хитрые штуки в расчёте на то, что тестовый набор будет соответствовать Вашему пониманию в том числе, ибо в общем случае они всегда вредны, как ни крути.
        • –1
          Запрещать использование тех же констант — затея какая-то нелепая. Проще выложить предварительный тестовый набор, а итоги подводить на аналогичном: другие ящики, другие маски, но схожие характеристики.
          • 0
            Констант в том ключе, чтобы в коде не было предварительно рассчитанных значений. Так как исходники всех решений открыты — в этом ничего нелепого я не вижу.

            Или разрешить присылать несколько вариантов скриптов, в зачёт идёт лучший результат, а не последний. Так как тестирование всё равно автоматическое — не вижу в этом вообще никакой проблемы.
          • 0
            Аналогичный по характеристикам набор — тоже вполне себе вариант при условии повторения ВСЕХ характеристик, а они совсем не ограничиваются повторением в письмах. Я бы даже сказал, что создание двух действительно схожих наборов является более сложной задачей, чем собственно, все те решения, что мы тут все изобретаем. Потому что для этого нужно знать все возможные оптимизации и подогнать/не подогнать под них всех одинаково :)
  • 0
    У меня вопрос: Будет ли учитываться порядок actions в результате? Т.е. если вместо ответа:
    {
        msg1: ['folder jack', 'forward to jill@elsewhere.com'],
        msg2: ['tag spam', 'forward to jill@elsewhere.com'],
        msg3: ['tag work']
    }
    

    придёт
    {
        msg3: ['tag work'],
        msg1: ['forward to jill@elsewhere.com', 'folder jack'],
        msg2: ['tag spam', 'forward to jill@elsewhere.com']
    }
    

    То тест на корректность будет пройден или нет?
    • 0
      Кажется выше автор писал, что порядок важен. Должны быть в порядке их перечисления в Rules.
      • 0
        Странное правило… Хоть бы аргументировали как-нибудь почему важен порядок…
        • 0
          Согласен. Но на вскидку — сперва правило на прогон через модный спам-фильтр, а потом на пересылку на нужный адрес. Порядок будет важен :)
          • 0
            Ну да, логика есть, к сожалению…
        • +1
          Почему условие задачи нуждается в аргументации? Оно такое, какое есть.

          А вообще, если бы это была реальная почтовая система с реальными действиями, то для некоторых действий порядок может быть важен.
      • 0
        А свойства объекта на выходе, надеюсь, не должны быть в том же порядке в котором приходят?
        • 0
          А Вы не можете задать порядок свойств в объекте. В ES3 было чётко сказано, что порядок не обязан соблюдаться, в ES6 вроде бы порядок определён, но его задаёте не Вы — там что-то типа сначала числа, потом строки потом символы, как-то так.
          • –1
            Порядок будет такой как вы его зададите. Вопрос в том как будет проводиться тест на корректность…
            Так:
            JSON.stringify(filter(messages, rules)) === JSON.stringify(idealResult);
            

            или так:
            var result = filter(messages, rules);
            Object.keys(result).forEach((key) => JSON.stringify(result[key]) === JSON.stringify(idealResult[key]));
            

            К сожалению, есть разница
            • 0
              Нет, не будет. При чём тут JSON.stringify? Вот эта вот штука → Object.keys не обязана выдавать ключи в том порядке, в котором Вы их в объект вставили. Я полагаю, что проверка будет проводиться чем-то типа _.isEqual…
              • 0
                Ок, забыл уточнить, что при использовании в качестве ключа не числового значения (а у нас как раз такое) порядок будет таким каким он задаётся в подавляющем большинстве случаев [99.(99)%]. Да не гарантируется, да порядок может поменяться! Но вы сами сталкивались хоть раз с такой ситуацией, чтобы _не числовые_ ключи возвращались вам отсортированными просто так, без каких либо усилий с вашей стороны (или с другим порядком)? Вообще, я где-то читал, что даже есть правило о том, что ключи объекта должны перебираться в том порядке в котором были созданы, оно не задокументировано в стандарте, но так работает.

                Хорошо, если будет deepEqual, но всякое может быть. Просто решил уточнить.
                А JSON.stringify тут притом, что я не догадался, что можно тут можно использовать сторонние решения :D
                • 0
                  Я не хочу думать о том, сломается ли мой код в очередной версии ноды или нет. Поэтому раз сказано что порядок не определён, значит не определён.

                  Сторонние решения использовать где? В проверялке можно использовать что угодно, я себе проверялку вообще на питоне написал, чтобы не зависеть в том числе от вот таких вот нюансов.
                  • 0
                    Это было нечто вроде сарказма, насчёт сторонних решений :)
                    В той ссылке что вы дали написано, кстати, что
                    integer indexes(*) in ascending order и strings in creation order
                    Ещё раз повторюсь, вопрос не в том как это работает (это известно), а в том как будут проверять :) А проверять можно по-разному, можно, например, не учесть некоторых деталей.
        • +1
          Объекты считаются неупорядоченными, порядок не сравнивается.
    • +1
      Ответ на Ваш вопрос содержится в условии задачи.
      • –1
        Просто решил уточнить, вдруг я понял неправильно.
  • +1
    Возник ещё один вопрос.
    Время инициализации присланного вам модуля будет учитываться или вы будете учитывать только время выполнения фильтрации?
    • +1
      Время инициализации будет входить в зачёт. Перед каждым тестовым запуском Ваш код будет заново инициализирован в новой виртуальной машине.
  • 0
    Ещё один вопрос.
    Можно ли изменять входные данные? Т.е. если его изменить таким образом, что его повторное использование будет не возможно, то это нормально?
    • 0
      Можно.
  • 0
    Выше в комментариях писали, что набор тестовых данных будет похож на содержимое почтового ящика типичного пользователя. Означает ли это, что в большинстве писем, еcли не во всех, будет фигурировать один и тот же адрес (в качестве from либо to)?
    • 0
      Или несколько. У пользователя может быть более одного личного адреса.
  • 0
    Наткнулся на итоги вашего прошлого конкурса. Скажите, пожалуйста, а начисление баллов в этот раз будет только на основании затраченного времени или и в этот раз будут разнообразные критерии для начисления дополнительных баллов, которые, вы, возможно, предпочитаете пока держать в секрете?
    • 0
      Баллов не будет. Будут миллисекунды.
      • 0
        Хорошо, спасибо
  • 0
    Подскажите, пожалуйста, а как будет происходить тестирование производительности? В том плане, что допустим берете набор данных и прогоняете N раз, а в зачет идет среднее или лучшее? Может вы посчитаете среднее, но как-то учтете стандартное отклонение. Или может вы возьмете M наборов данных самых разных, для каждого из них составите рейтинговую таблицу, а потом уже по сумме мест?
    • 0
      Ещё не решили. Но данные будут похожи на реальную почту.
  • 0
    feldgendler, оповещаете ли вы каким-нибудь образом о получении решения? У меня есть опасения, что js-файлам небезопасно путешествовать почтовыми вложениями из-за охоты за ними антиспам- и антивирусных систем.
    • +1
      Мы отвечаем на каждое письмо.
    • 0
      Уже выше отвечали, что оповещают. Меня оповестили в день отправки через несколько часов.
  • 0
    Уважаемые организаторы, озвучьте пожалуйста несекретную информацию о текущем ходе конкурса?
    Принято Х заявок, не прошли контрольные тесты Y заявок, может быть что-то еще интересное у Вас есть…
    Хоть какой-то update темы… — либо здесь либо на сайте конкурса
    • +3
      Приём работ окончен. Работы прислали 238 участников (это именно число участников, а не отдельных попыток). Результаты будут опубликованы 8 января.
      • 0
        8 января :)
        где результаты?

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

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