Стресс-тестирование - Алгоритмика
Стресс-тестирование

Стресс-тестирование

авторы Сергей Слотин Константин Амеличев
опубликовано 2019
обновлено авг. 25, 2021

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

  1. Правильное, но медленное.
  2. Быстрое, но неправильное.

Он особенно полезен на соревнованиях формата IOI — когда есть много времени и/или когда уже написано решение на маленькие подгруппы.

Более подробно:

  1. Есть решение smart — быстрое, но в котором есть баг, который мы хотим найти.
  2. Пишем решение stupid — медленное, но точно корректное.
  3. Пишем генератор gen — печатает какой-то корректный тест, сгенерированный случайно.
  4. Кормим всё в скрипт checker, который $n$ раз генерирует тест, даёт его на ввод stupid и smart, сравнивает выводы и останавливается, когда они отличаются.

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

#Конкретный пример

Задача. Есть массив чисел $1 \le a_1 … a_n \le 10^9$. Найдите значение минимального элемента.

Приведем код решения stupid, который будем использовать в качестве эталонного:

int a[maxn];

void stupid() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 1e9;
    for (int i = 0; i < n; i++)
        ans = min(ans, a[i]);
    cout << ans;
}

Пусть у нас есть решение smart, которое содержит ошибку в границах цикла:

int a[maxn];

void smart() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 1e9;
    for (int i = 1; i < n; i++)
        ans = min(ans, a[i]);
    cout << ans;
}

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

#Inline-тестирование

Примечание. Автор не рекомендует так делать, но многим такой подход кажется проще для понимания.

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

Генератор должен куда-то записать один случайный тест. Из самых простых вариантов:

  • в свое возвращаемое значение;
  • в переменные, переданные по ссылке;
  • в глобальные переменные.

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

int a[maxn];
int n;

int stupid() {
    int n;
    cin >> n;
    int ans = 1e9;
    for (int i = 0; i < n; i++)
        ans = min(ans, a[i]);
    return ans;
}

int smart() {
    int n;
    cin >> n;
    int ans = 1e9;
    for (int i = 1; i < n; i++)
        ans = min(ans, a[i]);
    return ans;
}

void gen() {
    n = rand() % 10 + 1;
    for (int i = 0; i < n; i++)
        a[i] = rand();
}

int main() {
    for (int i = 0; i < 100; i++) {
        gen();
        if (smart() != stupid()) {
            cout << "WA" << endl;
            cout << n << endl;
            for (int j = 0; j < n; j++)
                cout << a[j] << ' ';
            break;
        }
        cout << "OK" << endl;
    }
    return 0;
}

Этот подход универсален, но у него есть много недостатков:

  • Нужно дублировать много кода для тестирования разных задач.
  • Нельзя написать генератор или эталонное решение на другом языке (часто бывает проще и быстрее написать их на каком-нибудь скриптовом языке, вроде Python).
  • Исходный код становится более раздутым, и в нем сложнее ориентироваться.
  • Нужно быть аккуратным в плане использования глобальных переменных.
  • Нужно как-то переключаться между режимами «стресс-тестирование» и обычного «ввод из консоли».

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

#Тестирование внешним скриптом

Суть в следующем:

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

Файлы stupid.cpp, smart.cpp и gen.py содержат уже понятный нам код. Вот примерный код скрипта checker.py:

import os, sys

_, f1, f2, gen, iters = sys.argv
# первый аргумент это название программы, "checker.py",
# поэтому "забудем" его с помощью "_"

for i in range(int(iters)):
    print('Test', i + 1)
    os.system(f'python3 {gen} > test.txt')
    v1 = os.popen(f'./{f1} < test.txt').read()
    v2 = os.popen(f'./{f2} < test.txt').read()
    if v1 != v2:
        print("Failed test:")
        print(open("test.txt").read())
        print(f'Output of {f1}:')
        print(v1)
        print(f'Output of {f2}:')
        print(v2)
        break

Автор обычно запускает его командой python3 checker.py stupid smart gen.py 100, предварительно скомпилировав stupid и smart в ту же директорию, что и сам checker.py. При желании можно также прописать компиляцию прямо внутри скрипта.

Скрипт написан под Linux / Mac. Для Windows нужно убрать ./ во внешних командах и вместо python3 писать python.

Не забывайте, что если хотя бы одна из программ не выводит перевод строки в конце файла, то чекер посчитает, что вывод разный.

#Вариации

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

Если задача подразумевает неоднозначный вывод (к примеру, вывести индекс минимума — таких уже может быть несколько), то вместо stupid-решения и v1 != v2 следует использовать сторонний скрипт-чекер, который считывает тест и вывод решения и проверяет его, выводя yes / no.

Интерактивные задачи можно тестировать, написав интерактор, вывод из которого перенаправляется в решение и наоборот. Под Linux это делается так:

mkfifo fifo
./solution < fifo | ./interactor > fifo

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

Есть много чего ещё, что может быть полезным:

  • полноценная поддержка интерактивных задач,
  • многопоточное тестирование,
  • поддержка лимитов по памяти и времени,
  • автопрогон ручных тестов,
  • детекция изменения исходного кода и автоматическое перетестирование,
  • парсинг тестов из тестирующих систем,
  • цветной diff вывода и прочие кастомные выводы для чекеров.

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