Про перегляд результатів конкурсу з програмування на PHP

Спасибі учасникам конкурсу з програмування за довготерпіння. Я пишу цей пост, щоб визнати і виправити серйозну помилку, яку ми допустили при підведенні підсумків.

Ми отримали безліч зауважень про методику тестування рішень. Нижче наші відповіді на ці зауваження.

Тести на коректність неповні
Спасибі двом учасникам конкурсу, що надіслали доповнення до нашого набору тестів на коректність. Завдяки цим доповненням нам вдалося виявити кілька рішень, видають неправильні результати в рідкісних випадках.

Тести на продуктивність дають спотворені результати із-за особливостей методики тестування
Ми запускали рішення учасників у «віртуальній машині», реалізованої модулем
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.

Остаточні підсумки будуть, якщо не станеться нічого несподіваного, опубліковані через два дні. Тим часом, якщо у Вас є зауваження до нової системи тестування, не розглянуті в цьому пості, прошу коментувати цей пост.

Ще раз приношу вибачення всім, кого торкнулася ця історія.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.