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

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

Требования

  • Решение Brute Force, которое может быть медленным, но оптимальным
  • Генератор для создания случайных тестов
  • Проверка для одновременной проверки правильных и неправильных решений. Создание чекера может быть немного сложным, когда у проблемы есть несколько решений, в противном случае мы можем использовать инструмент diff в Linux.

Как реализовать

Основная идея состоит в том, чтобы генерировать случайные тесты с использованием псевдослучайных чисел и запускать на них как правильное (решение грубой силы), так и неправильное решение (оригинальное решение, которое вы стремитесь оптимизировать). Затем мы сравниваем результаты обоих решений и ищем несоответствие. Если есть несоответствие, у нас есть тестовый пример, в котором наше решение не работает :).

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

Лучшим способом является использование скрипта для обработки генератора проверки и записи, грубой силы и фактических решений в разных файлах. Давайте воспользуемся bash для написания такого скрипта и найдем способ отладки следующей проблемы.

Пример проблемы

Дан массив натуральных чисел, найти максимальное попарное произведение. Пример пусть массив будет [10, 20, 12, 50]. Здесь ответ будет 1000, так как [20,50] — это пара, которая даст максимальный продукт.

Грубая сила

Давайте теперь напишем решение грубой силы для решения проблемы.

Неверное решение

Предположим, это решение, которое мы пытаемся отладить.

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

Генератор

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

Стресс-тестирование Bash-скрипта

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

Запуск стресс-теста

Сначала мы делаем скрипт bash исполняемым, запустив

$ chmod +x stress_tesh.sh

После этого, когда все файлы будут готовы, запускаем стресс-тест.

./stress_test.sh testing.cpp brute.cpp generator.cpp 1000

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

Пример результата

Running tests...
[-] Wrong Answer
[+] 443 Accepted, failed at
Input:
8
1 1 6 4 2 3 8 8
Output:
48
Expected:
64

Теперь у нас есть тестовый пример, в котором наше решение не работает 😄

Заключение

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

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