Как дебажить программу

Введение

Обычный алгоритм решения задачи выглядит так:

1. Придумать решение.

2. Написать код решения (или лучше части решения).

3. Тестировать решение на своем компьютере (или лучше потестировать часть решения)

3+) Если не работает, то дебажить, пока не заработает на всех тестах.

4. Потестировать в тестирующей системе

4+) Если не работает, то придумывать тест, на котором не работает на своем компьютере. Если не находится - напишите стресс-тестирование

4++) Если все работает - внимательно читать код, добавить проверки в опасные места, перечитывать условие задачи, пока не найдете место, где либо вы не поняли задачу, либо ваша программа работает по-разному у вас и на сервере

4+++) Спросить преподавателя. Впрочем, этим методом можно и нужно пользоваться на более ранних стадиях, если вы только начинаете заниматься программированием

Здесь будут собраны советы о том, что делать в пунктах, начиная с 2.

Про первый пункт советов не будет :( Разве что совет, что придумать решение необходимо ДО того, как писать код.

Что делать, пока пишешь код

Проследите путь каждой переменной и каждого цикла

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

Также и для каждого цикла нужно понимать * какая будет первая итерация * в какой момент он закончится * сколько всего будет итераций * нет ли где-то выхода за границы массива

Пишите по кодстайлу

• ставьте отступы
• ставьте пробелы вокруг арифметических знаков
• пишите понятные, и главное, мало похожие друг на друга названия переменных
• делите программу на логические части (про это подробнее следующий совет)
• Изучите подробности общепринятого кодстайл: TODO: ВСТАВИТЬ ССЫЛКУ НА КАКОЙ-НИБУДЬ КОДСТАЙЛ

Зачем? * увидеть ошибку в структурированном коде гораздо проще, чем в каше * чужому человеку и вам в будущем читать ваш непонятный код будет гораздо сложнее и неприятнее * в промышленном программировании именно так все и пишут, полезно привыкнуть

Делите код на функции как можно более сильно

Почему? * в длинном сплошном коде легко не заметить ошибку * отдельные функции очень просто тестировать * если функция применяется несколько раз, то не нужно копировать код, что хорошо, так как при копировании кода можно скопировать ошибку, увидеть ее, исправить в одном месте, а в другом она * в промышленном программировании именно так все и пишут, полезно привыкнуть

Вот пример, когда в программе без функций найти ошибку тяжело: (код Сережи Карпышева)

# Задача - найти точку пересечения двух прямых

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    long long x3, y3, x4, y4;
    cin >> x3 >> y3 >> x4 >> y4;
    if((x1-x2)*(y4-y3)-(y1-y2)*(x4-x3)==0){
        if((x1-x3)*(y2-y3)-(y1-y3)*(x2-x3)==0){
            cout << 2;
            return 0;
        }
        cout << 0;
        return 0;
    }
    cout << 1 << ' ';
    double a1 = y2 - y1;
    double b1 = x1 - x2;
    double c1 = x1*y2-y1*x2;
    double a2 = y4 - y3;
    double b2 = x3 - x4;
    double c2 = x4*y3-y4*x3;
    double x =(b1*c2-b2*c1)/(b2*a1-b1*a2);
    cout << x << ' ';
    cout << (c1-c2+a1*x-a2*x)/(b2-b1);

    return 0;
}

Если ты - не Сережа Карпышев в октябре 2017 года, то этот код тебе отдебажить будет очень тяжело. Что здесь можно сделать для увеличения понятности кода: * Структура Point вместо пары чисел x1, y1 * Cчитывание точки происходит 4 раза, удобно сделать для этого функцию или переопределить оператор >> * Вектор разности двух точек считается где-то 6 раз, удобно сделать для этого функцию * Векторное произведение двух векторо считается 6 раз, удобно сделать для этого функцию * Проверку на параллельность двух векторов удобно вынести в отдельную функцию * Координаты прямой a, b, c удобно вынести в отдельную функцию, считающую их по двум точкам * Возможно даже структура Line вместо тройки чисел a, b, c * Координаты пересечения двух прямых удобно считать через функцию от двух прямых, и работать там только с их координатами

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

Как дебажить, если знаешь тест, на котором не работает

TODO описать процесс и виды дебага

Самые частые ошибки, если у вас все работает, а в тестирующей системе нет

Выход за границы массива

Если у вас ошибка, особенно на C++ - это почти всегда выход за границы массива. Когда вы обращаетесь на C++ к элементу в массиве/векторе, которого не существует, ваша программа по стандарту C++ может сделать все, что угодно (хоть отформатировать диск, но вряд ли такое будет :D). Такая штука называется undefined behaviour.

Обычно при запросе к несуществующему элементу массива просто возвращается число из тех битов, которые лежат на том месте в памяти. У вас на компьютере там может быть 0, а на informatics - какое угодно другое число.

Поэтому: * C++ чаще всего не видит эту ошибку и работает дальше. * Ваша программа может работать по-разному у вас и на сервере.

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

Слишком маленький тип данных

Нужно знать, что * int содержит числа примерно от \(-2 * 10^9\) до \(2 * 10^9\) * unsigned int содержит числа примерно от \(0\) до \(4 * 10^9\) * long long содержит числа примерно от \(-9 * 10^18\) до \(9 * 10^18\) * unsigned long long содержит числа примерно от \(0\) до \(18 * 10^18\)

И всегда проверять, что когда вы * складываете * умножаете * вычитаете

числа, они все еще помещаются в выбранный вами тип.

Например, в задаче про быстрое возведение в степень, по условию гарантируется, что \(x, N, P \leq 2 * 10^9.\) Это значит, что в тип int они влезут.

НО! В ходе алгоритма вы иногда умножаете два числа. При этом, если вы все делаете правильно, вы работаете всегда только с ОСТАТКАМИ по модулю \(P\), а значит с числами до \(2 * 10^9\). Чтобы ПЕРЕМНОЖИТЬ два таких числа, они должны быть типа long long, иначе произведение двух int-ов будет до \(4 * 10^18\), что в int не влезает, произойдет переполнение. Поэтому в этой задаче обязательно нужно использовать long long, и не забывать брать после каждого действия по модулю.

Крайние случаи

Если вам дана задача и ограчение \(0 <= N <= 10^6\), и вы убедились, что программа работает верно для каких-нибудь \(3, 5, 20\), то это может значить, что программа работает, но не на всех \(N\). Например, для \(N = 0\) может быть какой-то отдельный случай, когда решение не работает. То же самое и для \(N = 1, 2\). А для \(N = 10^6\) может быть проблема с тем, что она не влезает в память или что-нибудь переполняется (как в пункте 2). Если у вас WA на каком-то тесте, а у вас “на компе все работает”, то начинайте искать тест, на котором и у вас не работает. И в первую очередь смотрите на крайние значения. Если в задаче не одно \(N\), а много сложных входных данных, то придумайте самую стрёмную ситуацию, которую сможете, и проверьте, работает ли ваша программа на ней. Если вам повезет - вы найдете тест, на котором она не работает.

Вы решаете не ту задачу

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

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

Но если вы достаточно много тестировали свою задачу, то вам может помочь стресс-тестирование

TODO