Спасибо участникам конкурса по программированию за долготерпение. Я пишу этот пост, чтобы признать и исправить серьёзную ошибку, которую мы допустили при подведении итогов.
Мы получили множество замечаний о методике тестирования решений. Ниже наши ответы на эти замечания.
Тесты на корректность неполны
Спасибо двоим участникам конкурса, приславшим дополнения к нашему набору тестов на корректность. Благодаря этим дополнениям нам удалось выявить несколько решений, выдающих неправильные результаты в редких случаях.
Тесты на производительность дают искажённые результаты из-за особенностей методики тестирования
Мы запускали решения участников в «виртуальной машине», реализованной модулем vm в Node.js, чтобы предотвратить как использование require, так и другие возможные «сюрпризы» и попытки манипулировать тестовой системой. Однако оказалось, что модуль vm вносит серьёзные искажения в результаты тестирования. В частности, при использовании этого вида виртуализации доступ к глобальному пространству имён становится непропорционально медленным. Из-за этого простой перенос вспомогательных функций в тело функции filter может улучшить производительность в несколько раз. Большинство участников тестировали производительность своего кода простыми обёртками с использованием require, поэтому не оптимизировали его под особенности конкретного способа виртуализации. Мы считаем, что такой стилистический выбор, как размещение вспомогательных функций внутри или вне главной функции, не должен иметь настолько существенного влияния на результат.
Мы не знали об этой особенности модуля виртуализации Node.js, а, узнав, сочли её достаточно серьёзной для того, чтобы пересмотреть результаты. Теперь мы проводим тестирование в обычной виртуальной машине уровня ядра. Мы загружаем модули участников с помощью require и вызываем функцию filter один раз. На каждый проход теста запускается новый процесс Node.js.
К сожалению, это исправление приведёт к смене тройки лидеров. Мы приносим извинения тем, чья победа была объявлена ранее, и тем, кто изначально был лишён заслуженных призовых мест.
В тестах на производительность не встречаются символы ? в правилах
В отличие от тестов на корректность, которые призваны проверить правильность поведения программы даже в искусственно созданных редких ситуациях, тесты на производительность должны быть похожими на реальную жизнь. В частности, реальные пользователи едва ли когда-нибудь используют знак ? в правилах. Большинство правил в нашем тесте на производительность не содержат даже звёздочек, а в остальных звёздочка используется вместо всей части либо до, либо после символа @, что также отражает типичное применение этой возможности.
В тестах на производительность недостаточно много правил
Даже 100 правил — многовато для типичного продвинутого пользователя почты. В отличие от числа писем, мы не ожидаем хорошей масштабируемости при росте числа правил до таких нереалистичных чисел, как, например, 1000.
В тестах на производительность недостаточно много писем
Мы решили использовать 100 000 писем, поскольку это реалистичное число для активного пользователя за год. В порядке эксперимента мы решили увеличить это число до 800 000 — бо́льшие размеры уже начинают вызывать нехватку оперативной памяти для некоторых решений при стандартных настройках V8. Увеличенный тест можно сгенерировать скриптом generate_large_test.js с опцией xlarge. Мы прогнали на нём все корректные решения и увидели, что от увеличения объёма входных данных расстановка лидеров несколько меняется.
И 100 000, и 800 000, и промежуточные значения — в принципе одинаково достойные варианты. Мы могли бы сделать выбор в пользу увеличенного теста, или же взять некое средневзвешенное значение. Однако мы решили оставить изначальный вариант с 100 000 писем, чтобы свести к минимуму изменение методики тестирования по сравнению с изначально опубликованным. Если вышеописанная проблема с виртуализацией вносила такие чудовищные искажения, что соревнование уже нельзя было назвать честным, то размер тестовых данных мог быть свободно выбран в некотором разумном диапазоне, и тот размер, который мы решили использовать, вполне разумен.
Тесты надо было публиковать заранее
Мы не публиковали тесты в начале конкурса, чтобы не создать ситуацию, при которой участники занимались бы оптимизацией под конкретные тесты, а некоторые и вовсе пытались бы обманывать тестовую систему. Скажем, увидев, что наш скрипт, генерирующий тесты на производительность, никогда не использует знак ?, а знак * ставит только в начало или конец маски, хитрый участник мог бы написать один полностью корректный вариант алгоритма на случай тестирования на корректность (если число писем невелико), а при большом числе писем переключаться на более быстрый вариант, поддерживающий только те случаи, которые встречаются в тестах на производительность.
Тем не менее, мы решили в будущем публиковать больше информации о том, как будет проходить тестирование. Скажем, не показывая сами тестовые данные, мы могли бы объявить заранее их объём.
Итоги
Новая система тестирования опубликована в репозитории на GitHub.
Окончательные итоги будут, если не случится ничего неожиданного, опубликованы через два дня. Тем временем, если у Вас есть замечания к новой системе тестирования, не рассмотренные в этом посте, прошу комментировать этот пост.
Ещё раз приношу извинения всем, кого затронула эта история.
Автор: Hola
