Дебаг и стресс тестирование

В данной теме собраны фишки и подходы отладки и стресс тестирования программы.

Компиляция кода из консоли
Для компиляции используем команду: g++ -o <executable name> <source name> -std=c++17 -O2, где <executable name> – имя исполняемого файла, в который будет скомпилирован код, а <source name> – имя файла с кодом. Чтобы это работало, нужно, чтобы путь к g++ был прописан в PATH.

При компиляции можно указать различные дополнительные параметры: -Wall -Wextra -Wshadow – включает показ большого количество warning'ов при компиляции, -DLOCAL – определяет макрос LOCAL, который в дальнейшем можно использовать в ifdef и подобных конструкциях.

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

Дебаг
Для удобства дебага выводом можно определить следующий макрос:

#ifdef LOCAL
#define debug(x) cerr << (#x) << ": " << x << endl;
#endif

C

#ifdef LOCAL

   #define debug(x) cerr << (#x) << ": " << x << endl;

#endif

Пример использования:

int x = 5, y = 10;
string s = "Hello!";

debug(x)
debug(s)
debug(x + y)
debug(s << ' ' << x << ' ' << y << ' ' << x + y)

C

int x = 5, y = 10;

string s = "Hello!";



debug(x)

debug(s)

debug(x + y)

debug(s << ' ' << x << ' ' << y << ' ' << x + y)

Вывод будет следующим:

x: 5
s: Hello!
x + y: 15
s << ' ' << x << ' ' << y << ' ' << x + y: Hello! 5 10 15

C

x: 5

s: Hello!

x + y: 15

s << ' ' << x << ' ' << y << ' ' << x + y: Hello! 5 10 15

За счет того, что LOCAL был определен при компиляции локально, в тестирующей системе данный код не скомпилируется, так как макрос debug(x) не будет определен. Если мы хотим, чтобы код компилировался и в тестирующей системе, можно написать более сложную конструкцию:

#ifdef LOCAL
#define debug(x) cerr << (#x) << ": " << x << endl;
#else
#define debug(x) ;
#endif

C

#ifdef LOCAL

   #define debug(x) cerr << (#x) << ": " << x << endl;

#else

   #define debug(x) ;

#endif

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

#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

C

#ifdef LOCAL

   freopen("input.txt", "r", stdin);

   freopen("output.txt", "w", stdout);

#endif

Выход за границы массива
При использовании vector, для гарантированного получения Runtime Error при обращении к несуществующим элементам, можно вместо оператора квадратных скобок использовать метод at.

Пример:

vector<int> a = {1, 2, 3};
cout << a[5];
cout << a.at(5);

C

vector<int> a = {1, 2, 3};

cout << a[5];

cout << a.at(5);

Второй cout гарантированно упадет с Runtime Error и напишет вполне читаемое сообщение об ошибке. Злоупотреблять этим на туре не стоит, так как at работает несколько дольше.

Также можно использовать #define _GLIBCXX_DEBUG, объявленный перед всеми include. В случае выхода за границы программа также будет падать с RE.

Увеличение размера стека
Для увеличения размера стека можно использовать следующую конструкцию:

#pragma comment(linker, "/stack:200000000")

C

#pragma comment(linker, "/stack:200000000")

Здесь 200000000 – это размер стека в байтах.

На Linux можно локально увеличить стек при помощи команды ulimit -s unlimited.

Рандом
Для использования рандома с фиксированным seed'ом, можно воспользоваться следующей конструкцией:

mt19937 rnd(seed);
cout << rnd();

C

mt19937 rnd(seed);

cout << rnd();

Вызов rnd возвращает целое 32-битное беззнаковое число. Для генерации 64-битных чисел можно использовать mt19937_64.

Для того, чтобы сделать нефиксированный заранее seed, можно воспользоваться random_device:

random_device rd;
mt19937 rnd(rd());
cout << rnd();

C

random_device rd;

mt19937 rnd(rd());

cout << rnd();

На некоторых платформах rd() может работать детерминированно, и при каждом запуске программы выдавать один и тот же seed. Чтобы этого избежать, можно использовать более сложную конструкцию:

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
cout << rnd();

C

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

cout << rnd();

Для генерации целых чисел в нужном диапазоне можно написать свою функцию, либо воспользоваться uniform_int_distribution:
[CODE=c]uniform_int_distribution<int> dist(1, 10);
cout << dist(rnd);[/CODE]Данный код выведет целое число из отрезка [1, 10].

Для генерации вещественных чисел существует uniform_real_distribution, почитать про который можно на cppreference.

Генерация случайной перестановки
[CODE=c]vector<int> p(n);
iota(p.begin(), p.end(), 1);
shuffle(p.begin(), p.end(), rnd);[/CODE]Генерация случайного дерева
Сгенерируем подвешенное дерево с корнем в вершине 0. Для этого для каждой вершины сгенерируем предка с номером, меньшим, чем номер текущей вершины:
[CODE=c]for (int i = 1; i < n; ++i) {
cout << i << ' ' << rnd() % i << '\n';
}[/CODE]Такой способ генерации не очень хорош тем, что корень дерева – всегда вершина 0, а также в дереве всегда есть ребро (0,1). Поэтому после генерации дерева можно применить случайную перестановку к номерам всех вершин.

Также при таком способе генерации средняя высота дерева будет порядка O(log n), что может быть не хорошо. Можно воспользоваться следующим хаком:
[CODE=c]for (int i = 1; i < n; ++i) {
int parent = -1;
for (int it = 0; it < 5; ++it) {
parent = max(parent, rnd() % i);
}
cout << i << ' ' << parent << '\n';
}[/CODE]Если константу вложенного цикла делать больше, то глубина дерева будет получаться больше. Аналогично, если хочется генерировать неглубокие деревья, можно вместо максимума случайных значений выбирать минимум.

Стресс тестирование в одном файле
Шаблон для стресс тестирования в одном файле выглядит следующим образом:
[CODE=c]// Делаем входные данные теста глобальными, либо передаем их аргументами в функции

int correct() {
// Здесь пишем корректное решение
}

int wrong() {
// Здесь пишем неправильное решение
}

void gen() {
// Генерируем тест каким-либо образом
}

void stress() {
for (int test = 1; ; ++test) {
cout << "Test #" << test << '\n';
gen();
if (correct() != wrong()) {
// Выводим тест на экран
break;
}
}
}[/CODE]Разумеется, иногда сравнение ответов корректного и неправильного решений выполняется не так тривиально, для этого его удобно вынести в отдельную функцию.

Стресс тестирование при помощи bash скрипта (Linux only)
Создадим несколько файлов: correct.cpp – корректное решение, wrong.cpp – неправильное решение, gen.cpp – генератор тестов. Код всех этих файлов работает со стандартным вводом и выводом.

Теперь напишем bash скрипт stress.sh для тестирования:
[CODE=code]#!/bin/bash

# Компилируем все файлы
g++ -o correct correct.cpp -std=c++17 -O2
g++ -o wrong wrong.cpp -std=c++17 -O2
g++ -o gen gen.cpp -std=c++17 -O2

for (( i = 1; i < 100000; i++ ))
do
echo "Test number: ${i}"

# Генерируем тест и записываем его в файл test.txt
./gen > test.txt

# Запускаем корректное решение и записываем ответ в correct.txt
./correct < test.txt > correct.txt

# Запускаем неверное решение и записываем ответ в wrong.txt
./wrong < test.txt > wrong.txt

# Сравниваем файлы с ответом на равенство
# Здесь можно использовать diff, либо какую-то другую утилиту на ваше усмотрение
# Можно даже написать свой чекер!
if cmp -s correct.txt wrong.txt; then
echo "OK!"
else
echo "Fail!"
break
fi
done[/CODE]Перед запуском нужно выдать права на запуск командой chmod +x stress.sh.