Генераторы тестов

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

Что ломает решения

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

тип теста	что ловит
$n = 1$, пустой ввод	необработанный вырожденный случай
все элементы равны	деление на ноль, зацикливание, неверное сравнение
строго возрастающий и строго убывающий	худший случай быстрой сортировки, неверные границы
два различных значения	ошибки в устойчивости и в подсчётах
максимальные значения	переполнение
ответ равен нулю или границе	пропущенный крайний случай
максимальный размер	превышение времени и памяти

Случайный тест не даёт ни одного из них — кроме, может быть, последнего.

Маленький диапазон значений

Самый дешёвый способ усилить генератор — сузить значения.

for (int& value : a) value = rng() % 3;   // только 0, 1, 2

Три различных значения на массиве длины восемь гарантируют повторы, серии одинаковых элементов и совпадения — то есть все ситуации, где решение обычно и ломается. С диапазоном до $10^9$ ничего этого не будет ни разу за миллион тестов.

Полезная практика: гонять стресс двумя генераторами — одним с узким диапазоном, другим с широким.

Структурные тесты

Когда задача не про массив, случайность нужно строить осмысленно.

Дерево. Случайное дерево на $n$ вершинах — прикрепляем каждую вершину к случайной из предыдущих:

for (int v = 2; v <= n; v++) {
    int parent = rng() % (v - 1) + 1;
    cout << parent << ' ' << v << '\n';
}

Но такое дерево получается неглубоким — высота около логарифма. Отдельно нужны вырожденные формы: бамбук (parent = v - 1), где рекурсия переполняет стек, и звезда (parent = 1), где вершина имеет $n-1$ соседа.

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

Скобочная последовательность. Случайные скобки почти всегда неправильные. Правильные строят иначе: идут слева направо, поддерживая баланс, и закрывают скобку, только если баланс положителен.

Полный перебор маленьких входов

Для очень маленьких $n$ случайность вообще не нужна — можно перебрать все входы.

// все массивы длины n из значений 0..k-1
vector<int> a(n, 0);
while (true) {
    check(a);
    int i = n - 1;
    while (i >= 0 && a[i] == k - 1) a[i--] = 0;
    if (i < 0) break;
    a[i]++;
}

При $n = 6$ и $k = 3$ это $729$ тестов — доли секунды. Зато после такого прогона вы знаете не «скорее всего верно», а «на всех входах этого размера верно». Разница существенная.

Так же перебираются перестановки через next_permutation и подмножества через битовые маски.

Максимальный тест

Для проверки времени нужен отдельный генератор — на максимальные ограничения. И здесь случайность тоже часто слабее подобранного:

• быструю сортировку без рандомизации ломает отсортированный массив, а не случайный;
• хеш-таблицу unordered_map ломают ключи, кратные степени двойки;
• бинарный поиск по ответу — вход, где ответ на самой границе диапазона;
• рекурсию — вход, дающий максимальную глубину.

Правило: спросите себя, какой вход невыгоден именно вашему алгоритму, и постройте его руками.

Как воспроизвести падение

Генератор должен принимать сид и быть детерминированным.

int main(int argc, char** argv) {
    mt19937 rng(atoi(argv[1]));
    // ...
}

Тогда ./gen 4718 всегда даёт один и тот же тест, и найденное падение можно воспроизводить сколько угодно раз, в том числе после правок.

Без этого отладка превращается в угадывание: вы поправили код, запустили — прошло, но прошло ли потому, что исправили, или потому, что тест был другой, вы не знаете.

Уменьшение найденного теста

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

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

Правильная последовательность вообще такая: сначала генерировать маленькие тесты, а не сжимать большие. Но если падение нашлось только на крупном — сжатие обязательно, иначе вы будете отлаживать вслепую.