Отладка: Вердикты и Инструменты - Язык программирования C++ для спортивного программирования
ДополнительноОтладка и Стресс-тестирование
Отладка: Вердикты и Инструменты
Продолжение недели 7: что обычно означают Wrong Answer, Runtime Error, превышение времени и памяти и Compilation Error и о чём говорит номер теста; отладочная печать под #ifdef LOCAL, assert, предупреждения с -Wall -Wextra, проверки во время работы с -D_GLIBCXX_DEBUG, -fsanitize и -ftrapv, способы найти тест с ошибкой и список действий.
Теория
Урок 1 из 3
18 мин чтения
Вопросов: 5
Неделя 7 дала способ искать неверный ответ: сделать входные данные крошечными,
вычислить правильный ответ вручную и следить за программой, пока она не
отклонится от вашего плана. Неделя 12 добавила ловушки, которые стоит проверить,
и cerr для отладочной печати. Этот урок идёт дальше. Он начинается там, где
начинается любая неудачная посылка, — с вердикта, — а потом поручает поиск
компьютеру: отладочная печать, которую проверяющая система не видит, assert и
настройки компилятора, которые останавливают программу ровно на той строке, где
она ошибается.
Что говорит вердикт
Проверяющая система никогда не показывает скрытый тест, но говорит, что именно
пошло не так. Каждый вердикт указывает на свой короткий список причин:
Вердикт
Что произошло
Что искать
Compilation Error
компилятор проверяющей системы не принял код
при отправке выбран не тот язык; заголовочный файл, который есть только на вашем компьютере, например <conio.h>; опечатка, сделанная после последнего запуска
Wrong Answer
программа завершилась, но её вывод отличается от правильного
ловушки из недели 12: переполнение, < или <=, счётчик, не обнулённый между тестами, отрицательные числа, формат вывода
Runtime Error
программа упала или main вернула не 0
деление или % на ноль; индекс за пределами вектора; top() или front() пустого стека или очереди; слишком глубокая рекурсия (неделя 9)
Time Limit Exceeded
дальше
Временная сложность на практике
Продолжение недели 4: от ограничений к допустимой сложности (n!, 2ⁿ, n³, n², n log n, n, √n, log n), точный подсчёт вложенных циклов, гармонический цикл d, 2d, 3d…, циклы с делением пополам и log n, скрытые затраты одной строки, почему push_back в среднем быстрый, почему endl медленный и как засечь время на самом большом тесте.
идея, слишком медленная для самого большого ввода (следующий урок); цикл, который никогда не заканчивается; медленный вывод с endl
Memory Limit Exceeded
программа заняла больше памяти, чем разрешено
вектор с индексами до 10⁹; таблица n × n при большом n; push_back в бесконечном цикле
Две вещи из этой таблицы удивляют многих. Программа, которая читает за
пределами вектора, падает не всегда: она может тихо прочитать то, что лежит в
памяти рядом, пройти тесты дома и получить неверный ответ — или Runtime Error —
на проверке. А огромный вектор в некоторых проверяющих системах приводит к
Runtime Error вместо Memory Limit Exceeded: программа не может получить память
раньше, чем система успевает её измерить.
Номер теста — тоже подсказка
Большинство проверяющих систем говорят ещё и то, на каком тесте случилась
первая ошибка, и это ещё сильнее сужает поиск:
Тест 1 — почти всегда пример из условия. Программа не проходит пример,
который вы видите, поэтому запустите её ровно на этих входных данных и
сравните вывод посимвольно. Обычно виновато что-то лишнее в выводе —
подсказка вроде Enter n:, отладочная строка, пропущенный пробел или перевод
строки.
Один из первых тестов после примеров: крайний случай — n = 1, все значения
равны, ответа нет совсем.
Один из последних тестов: самые большие входные данные. Wrong Answer там
наводит на мысль о переполнении; превышение времени — о том, что идея слишком
медленная.
Превышение времени на тесте 1 — это никогда не медленная идея: тест 1
крошечный. Это цикл, который не заканчивается, — часто он ждёт входных данных,
которых нет.
Вот шесть посылок, похожих на настоящие, каждая со своим вердиктом и тестом, на
котором она упала. Сначала прочитайте вердикт, потом найдите строку:
Детектив вердиктовпопробуй!
Отладочная печать, которую не видит проверяющая система
Отладочная печать — самый быстрый способ заглянуть внутрь программы и самый
опасный: одна забытая строка с cout превращает правильную программу в Wrong
Answer, и даже забытая строка с cerr внутри цикла на 10⁵ оборотов может стоить
превышения времени. Выход — сделать так, чтобы на проверке она исчезала сама.
День называется рекордным, если в этот день теплее, чем во все дни до
него; первый день всегда рекордный. Даны температуры за n дней. Посчитайте
рекордные дни.
Ввод
Вывод
Эта программа печатает на этих данных 3 вместо 2:
Посмотрите на строки между #ifdef LOCAL и #endif. Строки, которые начинаются
с #, обрабатываются ещё до того, как код увидит компилятор. #ifdef LOCAL
означает «оставить строки до #endif, только если определено имя LOCAL».
На своём компьютере вы определяете его, компилируя с -DLOCAL:
Тогда программа ещё и пишет в cerr строку о каждом дне:
День 3 такой же тёплый, как день 2, а не теплее, и всё равно посчитан:
x >= best должно быть x > best. Проверяющая система компилирует без
-DLOCAL, поэтому для неё отладочной строки нет вовсе — она не печатается и даже
не выполняется. Её можно оставить в отправленном решении. В Code::Blocks
добавьте LOCAL один раз в Settings → Compiler → Compiler settings → #defines,
и оно появится во всех программах, которые вы там собираете.
Многие идут ещё дальше и пишут для себя короткую команду:
После этого dbg(best); печатает дома best = 5, а на проверке — ничего.
#define заменяет имя текстом ещё до компиляции, а #x — это текст того, что
вы написали в скобках, поэтому dbg(a[i] + 1) печатает само выражение вместе с
его значением.
Для отладочных строк берите cerr, а не cout, ещё по одной причине: cout
копит вывод в буфере и отправляет его большими порциями. Если программа падает,
буфер пропадает, и последние напечатанные строки так и не появляются — вы ищете
место падения не там. cerr отправляет каждую строку сразу.
assert: остановка на первом нарушенном обещании
Любая программа держится на том, что вы считаете верным: позиция лежит между 1
и n, счётчик никогда не бывает отрицательным, вектор здесь не пустой. assert
превращает такое убеждение в проверку:
Пока условие выполняется, assert ничего не делает. Как только оно ложно,
программа останавливается и говорит где. Для позиций 1, 3 и 0, если собрать
программу g++ в Windows:
В Linux то же сообщение выглядит так:
Обратите внимание, чего не хватает: ответы 10 и 30, напечатанные до падения, так
и не появились. Они ещё лежали в буфере cout.
Без assert выражение a[0 - 1] прочитало бы память за пределами вектора —
может быть, программа упала бы, а может, напечатала бы какое-то число. С ним вы
получаете строку и условие. На проверке сработавший assert даёт Runtime
Error, и этим можно пользоваться нарочно: если вы подозреваете, что скрытые
тесты нарушают правило, на которое вы полагаетесь, добавьте assert и отправьте
решение. Если Wrong Answer превратился в Runtime Error, вы ошибались.
Пусть ошибки ищет компилятор
Предупреждения
Компилятор замечает многие ошибки сам, но сообщает о них, только если его
попросить. Вот три ошибки в одной короткой программе:
Если собрать её командой g++ -Wall -Wextra -O2 warnings.cpp, компилятор
ответит (сокращённо):
Это if (x = 0), которое не сравнивает, а присваивает x значение 0; sign(0),
которая доходит до конца функции, так ничего и не вернув; и zeros, у которой
нет начального значения. Для последнего предупреждения нужен -O2: компилятор
прослеживает значения так далеко, только когда оптимизирует. В Code::Blocks
отметьте Enable all common compiler warnings [-Wall] и Enable extra compiler
warnings [-Wextra] в Settings → Compiler. И читайте предупреждения до запуска
программы, а не после того, как она не прошла тесты.
Проверки во время работы программы
Некоторые ошибки видны только во время работы программы. Вот такая:
Посчитайте спуски последовательности: позиции i, где число больше
следующего за ним.
Ввод
Вывод
Цикл доходит до i = n - 1 и читает a[n] — на один элемент дальше конца. На
нашем компьютере программа напечатала 2 — правильный ответ, по счастливой
случайности. Три настройки компилятора превращают это везение в ошибку с номером
строки:
Настройка
Что ловит
Где работает
-D_GLIBCXX_DEBUG
индекс за пределами vector или string, front() или back() пустого
любой g++, в том числе Code::Blocks в Windows
-fsanitize=address,undefined
любое чтение или запись за пределами вектора или массива, переполнение int, деление на ноль и многое другое
g++ и clang в Linux и macOS (и WSL в Windows); MinGW в Windows не может его подключить
-ftrapv
переполнение int: программа останавливается, а не продолжает с неверным числом
любой g++
С -D_GLIBCXX_DEBUG программа со спусками останавливается так:
С -fsanitize=address,undefined в Linux первые строки отчёта называют вид
ошибки и строку:
А сумма трёх чисел по 10⁹ в int, которая молча печатает -1294967296, вместо
этого получает такой отчёт:
В Windows эту программу вместо этого останавливает -ftrapv (без номера строки —
насколько далеко она дошла, покажут строки cerr перед остановкой).
С этими проверками программа работает в несколько раз медленнее, поэтому они
только для проверки дома. Проверяющая система собирает ваш код по-своему, что бы
вы ни использовали.
Как найти тест, на котором программа ошибается
Скрытый тест скрыт, но сам он нужен редко — нужен какой-нибудь тест, на
котором программа ошибается. Вот как его получить:
Не набирайте входные данные заново. Сохраните их в файл и запустите
sol < in.txt (в Linux и macOS — ./sol < in.txt). Программа читает файл
так, будто вы набрали его сами, и после каждого изменения можно запустить её на
тех же данных.
Делите входные данные пополам. Если длинный ввод даёт ошибку, разрежьте его
пополам. Если одна половина всё ещё даёт ошибку, оставьте её и режьте снова.
Через несколько шагов останется тест, который можно проследить вручную. Это
работает, когда часть правильного ввода тоже правильный ввод — список запросов,
список чисел с исправленным n.
Делите программу пополам. Напечатайте переменные в середине программы.
Если они уже неверны, ошибка в первой половине; если нет — во второй. Потом
делите пополам эту половину.
Спросите проверяющую систему с помощью assert, как выше.
Пусть ищет компьютер. Перебор и генератор находят тест с ошибкой за
секунды — об этом урок Стресс-тестирование в этом модуле.
Список действий при отладке
Проверьте себя
А вы знали?
4 июня 1996 года первая ракета Ariane 5 разрушилась через 37 секунд после старта.
Программа управления, взятая от меньшей ракеты Ariane 4, переводила скорость,
хранившуюся как 64-битное число с плавающей точкой, в 16-битное целое. Ariane 5
летела быстрее, значение больше не помещалось, и преобразование не удалось.
Резервный компьютер выполнял тот же код и отказал так же — на долю секунды
раньше. Это одно из самых дорогих переполнений в истории.
Когда посылка не прошла
Прочитайте вердикт и номер теста. Они подскажут, какой список проверять.
Запустите примеры ровно в том виде, как они даны, и сравните вывод посимвольно.
Соберите с проверками — предупреждениями и -D_GLIBCXX_DEBUG — и исправьте каждое предупреждение.
Попробуйте крошечный тест на каждую ловушку, сначала вычислив ответ вручную. Если дело во времени или памяти — засеките время на самом большом тесте.
Всё ещё не получается? Сделайте стресс-тест (последний урок) или объясните код строку за строкой кому-нибудь — или утёнку.
проверь себя1 балл
Строка между #ifdef LOCAL и #endif всё равно выполняется на проверке, если она пишет в cerr.
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Посылка получила Wrong Answer на тесте 1. Что проверить в первую очередь?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Программа получила Time Limit Exceeded на тесте 1, а в тесте 1 три числа. Какая причина вероятнее всего?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
В решении есть assert(cnt > 0);. На одном скрытом тесте в этой строке cnt равен 0. Какой вердикт вы получите?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Вы работаете в Code::Blocks в Windows. Какая настройка компилятора заставит программу остановиться с сообщением об ошибке при чтении a[n] из вектора?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
4
3 5 5 2
2
g++ -DLOCAL records.cpp -o records
day 1: x = 3, records = 1
day 2: x = 5, records = 2
day 3: x = 5, records = 3
day 4: x = 2, records = 3
3
Assertion failed: 1 <= p && p <= n, file positions.cpp, line 19
positions.cpp:19: int main(): Assertion `1 <= p && p <= n' failed.
warnings.cpp:16:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
warnings.cpp:7:1: warning: control reaches end of non-void function [-Wreturn-type]
warnings.cpp:21:30: warning: 'zeros' is used uninitialized in this function [-Wuninitialized]
4
5 3 4 1
2
Error: attempt to subscript container with out-of-bounds index 4, but
container only holds 4 elements.
ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000020 ...
READ of size 4 at 0x602000000020 thread T0
#0 0x402899 in main descents.cpp:16
total.cpp:14:15: runtime error: signed integer overflow: 2000000000 + 1000000000 cannot be represented in type 'int'
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int best = 0, records = 0; for(int i = 0; i < n; i++){ int x; cin >> x; if(i == 0 || x >= best){ records++; best = x;}#ifdef LOCAL cerr << "day "<< i + 1<< ": x = "<< x << ", records = "<< records << "\n";#endif} cout << records << "\n"; return 0;}