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

Это перевод статьи Джошуа Блоха «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 (а именно, если их сумма больше 2³¹-1) возникает ошибка. Их сумма становится отрицательным числом, и mid также получается отрицательным. В Си это привело бы обращению памяти за пределами массива с непредсказуемыми последствиями, а Java кидает исключение ArrayIndexOutOfBoundsException.

Эта ошибка проявляется только на очень больших массивах, больше 2³⁰ (порядка миллиарда) элементов. В 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 г. Главный инженер финского исследовательского центра Нокии Антуан Трю (Antoine Trux) сообщил, предложенное исправление для Си и C++ не гарантирует корректной работы, потому что по стандартам этих языков арифметическое переполнение при сложении даёт неопределённый результат. Теперь, когда мы исправили этот недочёт, мы точно уверены, что программа работает правильно. ;)

Ссылки:

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.