В исследовании Кембриджского университета говорится, что ошибки в программном обеспечении обходятся мировой экономике в 312 миллиардов долларов в год. Охота на жуков — сложная задача. Как писал Брайан У. Керниган: « Отладка в два раза сложнее, чем писать код в первую очередь. Поэтому, если вы пишете код настолько умно, насколько это возможно, вы, по определению, недостаточно умны для его отладки. «К сожалению, это правда. Несколько раз даже талантливые разработчики блокируются, чтобы найти ошибки. В следующих статьях « Отладка шаг за шагом …» мы дадим несколько советов, чтобы облегчить эту задачу.
Давайте предположим, что у нас есть ошибка. Какой первый шаг? Это зависит … Давайте посмотрим пример. Мы реализовали алгоритм быстрой сортировки и протестировали его с помощью чисел:
4, 12, 9, 14, 3, 10, 17, 11, 8, 7, 4, 1, 6, 19, 5, 21, 2, 3
1, 3, 2, 5, 3, 4, 4, 6, 7, 8, 9, 10, 11, 12, 14, 17, 19, 21
Таким образом, тест не прошел. Что делать сейчас? Одна из возможностей — начать отладку. Тем не менее, это не очень хорошая идея. Зачем? Поскольку выполнение содержит слишком много шагов, за которыми трудно следовать. Количество шагов выполнения равно 670, и мы должны проанализировать многие из них, пока не найдем ошибку.
Дельта-отладка — это метод сокращения ввода, в результате которого получается два набора ввода
- один вход выявляет ошибку
- другой не
для которого разница минимальна, т.е. во втором входе отсутствует только одно число из первого.
Есть довольно много ручных методов для минимизации ввода. Если наши входные данные являются однородными, то может сработать простое деление пополам. Метод прост: после размещения ввода в двух, возможно, одинаковых списках размеров мы выполняем код, и если один из них является вводом, вызванным сбоем, мы выбираем его. Мы продолжаем делить пополам, пока метод не работает. Если этого не произойдет, мы можем уменьшить оставшиеся входные данные, удалив элементы по одному. Давай сделаем это сейчас.
пример
Шаг 1. В нашем примере ввод в два раза: 4, 12, 9, 14, 3, 10, 17, 11, 8 — получение результата: 3, 12, 4, 8, 9, 10, 11, 14, 17 т.е. явно неисправен.
Шаг 2. Следующий вход: 4, 12, 9, 14 — для которого выход правильный: 4, 9, 12, 14.
Шаг 3. Мы пробуем вторую половину, которая составляет 3, 10, 17, 11, 8, получая вывод: 3, 8, 10, 11, 17 — снова правильно.
Шаг 4. Наш следующий вывод — это уменьшение нашего последнего ввода, вызванного отказом, путем вырезания двух последних чисел: 4, 12, 9, 14, 3, 10, 17. Результат также ошибочный: 4, 10, 9, 12 , 3, 14, 17.
Вырезая любые элементы, вывод остается правильным, поэтому наш минимизированный ввод: 4, 12, 9, 14, 3, 10, 17. Для этого теста количество шагов выполнения составляет 192, что составляет менее 30% от исходного.
Однако полученный нами ввод является локальным минимумом, и в некоторых случаях мы можем минимизировать ввод, вызванный сбоями, лишь немного подумав. Рассмотрим вывод для первого теста еще раз:
1 , 3, 2, 5, 3, 4, 4, 6, 7, 8, 9, 10, 11, 12, 14, 17, 19, 21
Мы видим, что кроме под-результата: 3, 2, 5, 3, 4, результат правильный. Таким образом, мы выбираем эти числа из входного набора: 4, 3, 5, 2, 3, и это работает, так как результат все еще содержит ошибку: 3, 3, 4, 2, 5. Дальнейшее сокращение не может быть достигнуто этим способом думать, хотя это не глобальный минимум либо. Тем не менее, количество шагов сокращено до 139, то есть до 20% от исходного теста.
Возвращаясь к нашему первоначальному систематическому методу и удаляя первое число 4, наш ввод: 3, 5, 2, 3 — мы получаем ошибочные 3, 3, 2, 5 — что является минимальным вызванным отказом вводом, приводящим к 111 шагам выполнения и 83% скидка.
И насколько велика экономия времени на эту минимизацию? Мы не знаем Однако, если вы поможете нам исправить ошибку, мы можем дать ответ. Неисправная версия Quicksort приведена ниже. Если ваш день рождения в месяцах 1-6, используйте оригинал, в противном случае — минимальный ввод. Просто напишите мне ([email protected]) письмо с фиксированными линиями, используемыми данными и временем, потраченным на исправление (в минутах). Я публикую результаты на нашем сайте http://4dsoft.eu/blog и последующую статью здесь. Спасибо за ваше сотрудничество.
Вывод
Дельта-отладка — это метод «разделяй и властвуй», с помощью которого наша первоначальная задача отладки упрощается за счет минимизации ввода. Отладка затем выполняется на более простой трассировке кода.
Наш опыт показал, что общее время поиска ошибок в значительной степени сокращается за счет применения дельта-отладки. Иногда мы вводим более 100 000 строк кода Java, дельта-отладка абсолютно необходима для поиска ошибок в этой среде.
Быстрая сортировка с ошибкой
import java.io.*;
import java.util.*;
public class QuickSort
{
public static void quicksort(int numbers[], int low, int high) {
int i = low, j = high;
// Get the pivot element from the middle of the list
int pivot = numbers[low + (high-low)/2];
// Divide into two lists
while (i <= j) {
while (numbers[i] < pivot) {
i++;
}
while (numbers[j] > pivot) {
j--;
}
if (i <= j) {
exchange(numbers, i, j);
}
i++;
j--;
}
// Recursion
if (low < j)
quicksort(numbers, low, j); //low
if (i < high)
quicksort(numbers, i, high);
}
private static void exchange(int numbers[], int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
int k = 1;
}
public static void main(String argv[])
{
int A[] = {4, 12, 9, 14, 3, 10, 17, 11, 8, 7, 4, 1, 6, 19, 5, 21, 2, 3};
// minimized failure-induced input
// int A[] = {3, 5, 2, 3};
quicksort(A, 0, A.length - 1);
for (int i=0 ; i < A.length ; i++) System.out.print(A[i] + " ");
System.out.println();
}