Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 3.06.2014 | нет комментариев
Это перевод статьи Джошуа Блоха «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 равным среднему этих чисел, округленному к ближайшему меньшему целому». На 1-й взор всё в порядке, но для довольно крупных 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;

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

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

Мы, программисты, обязаны всякими методами совершенствовать наш код.

 Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB