Pull to refresh

Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка

Reading time 3 min
Views 53K
Original author: Joshua Bloch
Это перевод статьи Джошуа Блоха «Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken» 2006 года.

Я живо помню первую лекцию Джона Бентли в университете Карнеги-Меллон, на которой он попросил нас, свежеиспечённых аспирантов, написать функцию двоичного поиска. Он взял одно из решений и разобрал его на доске, и, разумеется, в нём оказалась ошибка, как и во многих других наших попытках. Этот случай стал для меня наглядной демонстрацией к его книге «Жемчужины программирования». Мораль в том, чтобы внимательно расставлять инварианты в программе.

И вот, теперь 2006 год. Я был потрясён, узнав, что программа двоичного поиска, корректность которой Бентли доказывал формально и тестами, содержит ошибку. Не подумайте, что я придираюсь; по правде сказать, такая ошибка вполне может ускользать от тестеров десятилетиями. Более того, двоичный поиск, который я написал для 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.
 }

Ошибка в шестой строке:

    int mid = (low + high) / 2;

В «Жемчужинах программирования» Бентли на счёт аналогичной строки пишет, что она «устанавливает m равным среднему этих чисел, округленному к ближайшему меньшему целому». На первый взгляд, всё в порядке, но для достаточно больших low и high (а именно, если их сумма больше 231-1) возникает ошибка. Их сумма становится отрицательным числом, и mid также получается отрицательным. В Си это привело бы обращению памяти за пределами массива с непредсказуемыми последствиями, а Java кидает исключение ArrayIndexOutOfBoundsException.

Эта ошибка проявляется только на очень больших массивах, больше 230 (порядка миллиарда) элементов. В 80-х годах, когда книга увидела свет, это было бы невозможным, но теперь у нас в Google (да и вообще в любом проекте) это обычное дело. В «Жемчужинах программирования» Бентли пишет: «хотя первая версия двоичного поиска была опубликована в 1946 году, корректный код, обрабатывающий все значения n, появился лишь в 1962-м». На самом деле, корректный код до сих пор почти не встречался даже в самых популярных реализациях языков.

Так как же правильно написать этот код? Шестую строку можно переписать так:

    int mid = low + ((high - low) / 2);

Хотя, возможно, быстрее и проще такой вариант:

    int mid = (low + high) >>> 1;

В С/C++ нет оператора >>>, но можно написать так:

    mid = ((unsigned int)low + (unsigned int)high)) >> 1;

Ну уж теперь-то мы точно знаем, что ошибок больше нет, правда? Ну… скорее всего. Чтобы абсолютно строго доказать корректность программы, её нужно протестировать на абсолютно всех возможных входных данных, но на практике это почти никогда не осуществимо. А для параллельных вычислений всё ещё хуже: вам придётся тестировать программу для всех возможных внутренних состояний. Даже и не пытайтесь.

Эта ошибка может вылезти в сортировке слиянием и в других алгоритмах типа «разделяй и властвуй». Если вы реализовывали такие алгоритмы, перепроверьте их, пока ошибка не привела к неприятным последствиям. Лично меня эта ошибка научила быть чуточку скромнее и не полагаться на очевидность даже небольшого и привычного куска кода, не говоря уже о действительно сложных системах, которыми мы пользуемся каждый день.

Мы, программисты, должны любыми способами совершенствовать наш код. Аккуратное проектирование архитектуры — это хорошо. Тестирование и формальный анализ алгоритмов — ещё лучше. Статический анализ и ревизия кода — просто замечательно. Но ничто из этого по отдельности не спасёт нас от неуловимых багов, которые будут жить по полвека, несмотря на любые наши усилия. Мы должны практиковать аккуратное защитное программирование и быть неусыпно бдительными.

Апдейт 17 февраля 2008 г. Главный инженер финского исследовательского центра Nokia Антуан Трю (Antoine Trux) сообщил, что предложенное исправление для Си и C++ не гарантирует корректной работы, потому что по стандартам этих языков арифметическое переполнение при сложении даёт неопределённый результат. Теперь, когда мы исправили этот недочёт, мы точно уверены, что программа работает правильно. ;)

Ссылки:
Tags:
Hubs:
+36
Comments 57
Comments Comments 57

Articles