Экстренное чтиво: почти все бинарные поиски и сортировки слиянием поломаны
Я отчетливо помню первую лекцию Джона Бентли по алгоритмам в CMU, где он попросил всех нас, начинающих Ph.D, написать бинарный поиск, а затем разобрал критически одну из наших реализаций перед аудиторией. Конечно же, она была нерабочей, как и большинство наших реализаций. Это произвело на меня большое впечатление, так же как и обработка этого материала в его замечательной книге Programming Pearls (Addison-Wesley, 1986; Second Edition, 2000) Ключевой урок был в осторожном обдумывании стабильности в ваших программах.
Быстро возвращаясь к
Так в чем же дефект? Вот стандартный бинарный поиск для Java (Это тот, что я написал для java.util.Arrays):
public static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
Дефект содержится в строчке 6:
int mid =(low + high) / 2;Бентли в Programming Pearls говорит, что аналогичная строка «m задается как среднее между 1 и u, усеченная вниз к ближайшему целому.» Перед лицом этого, данное утверждение может быть и правильным, но оно неверно для больших значений int в переменных low и high. В частности, оно «падает» если сумма low и high больше чем наибольшее положительное значение int (231 — 1). Сумма переполняется к отрицательному значению, и это значение остается отрицательным, когда делиться на 2. В языке C это вызвало бы «array index out of bounds» с непредсказуемыми результатами. В Java это вызывает ArrayIndexOutOfBoundsException.
Этот дефект обнаруживается в массивах длинна которых (поэлементно) 230 или больше (грубо миллиард элементов). Это было немыслимо в
Так какой же лучший способ исправить дефект? Вот один способ:
int mid = low + ((high - low) / 2);Возможно более быстрый, и также более понятный:
int mid = (low + high) >>> 1;В C и C++ (где нет оператора >>>) вы можете сделать так:
mid = ((unsigned) (low + high)) >> 1;Сейчас мы знаем, что двоичный поиск не содержит дефектов, так? Ну, мы сильно это подозреваем, но не знаем наверняка. Не достаточно только утвердить, что программа верна, вы должны протестировать со всеми возможными значениями ввода, однако это редко осуществимо. В параллельных программах, ситуация еще хуже: вы должны протестировать для всех внутренних состояний, что для всех практических намерений — неосуществимо.
Дефект в бинарном поиске особенно применим к сортировке слиянием (mergesort) и к другим алгоритмам «разделяй и властвуй». Если у вас есть код, реализующий один из этих алгоритмов, исправьте его, прежде чем он взлетит на воздух. Общий урок, который я почерпнул из этого дефекта — это смирение: очень тяжело написать даже очень небольшой кусочек кода правильно, а наш мир работает на больших, сложных кусках кода.
Нам программистам нужна вся помощь, которую только можем получить и мы не должны даже предполагать иначе. Старательный дизайн — это хорошо. Тестирование — это хорошо. Формальные методы тоже хороши. Проверки кода — хороши. Статический анализ — это хорошо. Но ни одна из этих вещей по отдельности успешна в предотвращении дефектов. Они всегда будут с нами. Дефект может существовать половину столетия, несмотря на наши лучшие попытки искоренить его.
Мы должны программировать внимательно, предохраняясь и всегда оставаясь бдительными.
От автора перевода
Эта статья попалась мне тогда, как судьба заставила заниматься адаптацией и тестированием проекта, оригинально написанным под .NET, на Mono. К этому времени мне удалось обнаружить несколько дефектов в самой платформе Mono, что, в общем-то, не было чем-то из ряда вон, т.к. проект с виду «зеленый», open-source, с широким community и латиноамериканской тусовкой разработчиков. После прочтения статьи, первая мысль, что пришла мне в голову: «10:1, что у Mono есть такие проблемы». Сразу же решил это установить, написав такой тест кейс:<code class="csharp">using System;
class Search {
static void Main() {
int ind = 0;
byte[] array = new byte[1100000000];
array[array.Length - 1] = 1;
ind = System.Array.BinarySearch(array,1);
if (ind!=0)
Console.WriteLine("found " + ind);
else
Console.WriteLine("not found");
}
}
</code>
Написал в Notepad’е, откомпилировал с помощью CSC (.NET 1.1) с целью запустить его под Mono. Но после компиляции рука не удержалась и автоматически запустила полученный «exe-шник» в Windows. Каково же было мое искреннее удивление обнаружить проблемы подобного рода еще и у Microsoft. Уже можно и не упоминать, что тест на Mono дал подобные результаты. После я взял у mono-team исходный код класса Array.BinarySearch, затем глянул рефлектором соответствующую сборку у .NET — вся та же проблема с делением переполненного значения!
Sun, исправила этот дефект в JDK 1.6 («Mustang»). Команда Mono, надеюсь, тоже когда-то за это возьмется. А в службе поддержки Microsoft, лично для меня, все оказалось не так прозрачно, для того чтобы просто уведомить их о «баге», а не подписаться на программу beta-тестирования или чего-нибудь еще. От части поэтому, пишу я это здесь.
Для развлечения можете проверить используемые вами библиотеки классов с подобной функциональностью на наличие вышеописанного дефекта.
anonymous
mlk
Sergiy Matusevych
В'ячеслав Колдовський
Michael Shigorin
Denys Nikolayenko
15 коментарів
Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.