Экстренное чтиво: почти все бинарные поиски и сортировки слиянием поломаны

Я отчетливо помню первую лекцию Джона Бентли по алгоритмам в CMU, где он попросил всех нас, начинающих Ph.D, написать бинарный поиск, а затем разобрал критически одну из наших реализаций перед аудиторией. Конечно же, она была нерабочей, как и большинство наших реализаций. Это произвело на меня большое впечатление, так же как и обработка этого материала в его замечательной книге Programming Pearls (Addison-Wesley, 1986; Second Edition, 2000) Ключевой урок был в осторожном обдумывании стабильности в ваших программах.

Быстро возвращаясь к 2006-му. Я был глубоко потрясен, обнаружив, что программа, заявленная Бентли, как рабочая и впоследствии протестированная в главе 5 в Programming Pearls содержит дефект (bug). Как только я расскажу, в чем он состоит, вы поймете, почему ему удавалось избежать выявления в течение двух десятков лет. Чтобы вы не подумали, что я придираюсь к Бентли, давайте я расскажу, как же мне удалось обнаружить этот дефект: версия бинарного поиска, который я написал для JDK, содержал этот же дефект. О нем было заявлено Sun, как только поломалась чья-то программа, и это случилось после девяти лет выжидания.

Так в чем же дефект? Вот стандартный бинарный поиск для 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 или больше (грубо миллиард элементов). Это было немыслимо в 80-х, когда была написана Programming Pearls, но это обыденно в наши дни в Google и других местах. В Programming Pearls Бентли сказал «Хоть и бинарный поиск был опубликован впервые в 1946-м, первый бинарный поиск, который работает правильно для всех значений n — не появился раньше 1962-го» Правда в том, что очень мало правильных версий были когда-либо опубликованы, по крайней мере, на основных языках программирования.

Так какой же лучший способ исправить дефект? Вот один способ:

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-тестирования или чего-нибудь еще. От части поэтому, пишу я это здесь.

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

Ссылки

  • Популярное

15 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

@IMDagger, верно, вариант http://pastebin.com/f404370ca не уходит в бесконечный цикл.Но по умолчанию всё равно поломано.

Сергей говорит: 21.08.2007 в 18: 13 хо-хо, таки облом и в пайтонеimport sys, bisect, time

По моему, облом не в пайтоне, а в сишной реализации модуля _bisect, который исходя из bisect.py:

# Overwrite above definitions with a fast C implementation try:     from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect except ImportError:     pass

Т.к., если не подключать C-шную часть, то всё работает, как и положено;) т.к. происходит конвертация int-> long

Не знаю як ви, а я взагалі не зміг виділити стільки пам"яті... -> System.OutOfMemoryException.

В.NET 2.0 исправили, все работает. Правда, с небольшой поправкой: ind = System.Array.BinarySearch (array, (byte) 1);

хо-хо, таки облом и в пайтоне

import sys, bisect, timeclass big_array(object): def init(self, len=sys.maxint): self.len = len def getitem(self, index): print hex(index), hex(self.len) if index >= self.len: raise IndexError elif index == self.len-1: return 1 else: return 0 def len(self): return self.lenprint bisect.bisect(big_array(sys.maxint/2), 1)print '-'*40time.sleep(3)# infinite loop =(print bisect.bisect(big_array(), 1)

стоп, речь о длинах списка вообще, затупил, сорри.

Я осадке от этой конструкции =)

byte[] array = new byte[1100000000]; array[array.Length - 1] = 1;

Т.е. зачем

array.Length - 1

брать?Если я правильно понял, то в питоне этому будет аналогом:

In [12]: x = int('1100000000', 2)In [13]: import bisectIn [14]: bisect.bisect([1, x], x)Out[14]: 2In [15]: bisect.bisect([1, x], 1)Out[15]: 1

Впрочем можно было догадаться что автоматическое int -> long преобразование должно справиться

Неплохо бы имя автора и ссылку на оригинал давать в начале статьи. А то я уже было проникся — вау, аспирант из карнеги-меллона сюда пишет. ага.

До Саші: Звичайно, можна поглянути і з іншого боку — звичайно, це не недолік, а суттєва перевага, оскільки б за її відсутності складніше було знайти, чого б такого показати студентам.Взагалі лекції з програмування можна перевести до розгляду типових помилок, замість того, щоб витрачати час на вивчення програмування.Та, мабуть, і мову необхідно підібрайти пристойну, наприклад, C++ — тут буде дуже широке поле для розгляду «типових помилок». А в самій мові програмування недоліків немає, є лише в ДНК програмістів;)

Только не «поломаны», а «сломанные». Разница в основном в " [недавний] процесс" vs «состояние»; ср. «broken» vs «cracked».

Х-м, а нам цей приклад на одній з перших лекцій в університеті показували — як класичну помилку.І ніякий це не недолік сучасних мов програмування...

Ай, маладца!

Это пример одного из фундаментальных недостатков современных языков программирования.Человеку свойственно ошибаться, и чем меньше язык программирования предоставляет для этого возможностей — тем лучше.Помнится, на меня произвело большое впечатление отсутствие в Erlang каких-либо ограничений на разрядность чисел (хотя, я могу ошибаться насчет того, что там вообще нет ограничений — не сильно-то я и разобрался в Erlang). Но вот сама идея вызывает уважение. Необходимость следить за различными переполнениями регистров, памяти, округлениями — все это наследие каменного века программирования. Наряду со слежением за освобождением памяти динамических переменных пора бы избавиться и от этого.

Подписаться на комментарии