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

http://googleresearch.blogspot.ru/2006/06/extra-extra-read-all-about-it-nearly.html
  • Перевод
Это перевод статьи Джошуа Блоха «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++ не гарантирует корректной работы, потому что по стандартам этих языков арифметическое переполнение при сложении даёт неопределённый результат. Теперь, когда мы исправили этот недочёт, мы точно уверены, что программа работает правильно. ;)

Ссылки:
Поделиться публикацией
Комментарии 56
    +22
    Всегда всем бинарный поиск (сортировку слиянием) объяснял только с такой реализацией взятия среднего: int mid = low + ((high — low) / 2); По-моему это очевидно.
      0
      Комментарий удален
        –5
        Я вот подвязался попробовать, в точности, как в старой статье просили — без тестирования, с первого раза, бла-бла. Вышло почему-то вообще безо всяких low и high, если быть точным — без high. 15 минут вдумчивого письма сверху вниз в vim без черновиков и досок — ничего особенного. Не быстро, да, но я и не ACM-щик ни разу в жизни, сам бинпоиск-то второй раз пишу — первый года полтора назад был. И кажется мне, он вышел тогда каким-то совсем другим.
          0
          Статья 2006 года, может быть, вы уже были в курсе?
          +1
          Чрезвычайно поучительно и удивительно, как много высокопрофессиональных программистов делают простейшие технические ошибки. Я рискую получить по лицу за неуважение к авторитетам, но всё же сформулирую свою скромную идею, которая позволяет исключить риск данной (и любой подобной) ошибки.

          Мой рецепт прост: если в вашем коде хотя бы теоретически возможно возникновение чисел порядка 2^31, значит тип int32_t и даже uint32_t — не для вас. А если вы всерьёз допускаете возможность того, что числа разрастутся бесконтрольно, извольте использовать длинную арифметику — потеря в производительности в два-три раза обычно не является критичной, в отличии от подобных ошибок. Представьте себе, катастрофу какого масштаба вызовет подобное в большом и серьёзном проекте…
            +4
            Экстенсивные способы решения задач мне кажутся не совсем честными. В статье речь об алгоритмической чистоте, и если оставить код неизменным, а поменять лишь типы данных, то чистота кода никак не изменится и ошибка не исчезнет. Просто вероятность её возникновения станет меньше, но нулю равна не будет.
              +4
              Я предполагал, что меня заминусуют, когда писал это. Поясню, что я имею в виду.

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

              Но что мне на самом деле не нравится — это попытка решать задачи «на кончике пера». Продумать всё невозможно (и данная статья — наглядное тому подтверждение). Экстенсивное решение позволяет сэкономить нервы за счет ресурсов и, разумеется, не всегда оно годно (как и любой тип решения не является серебряной пулей). Но в данном случае замена int на long не потратила бы много ресурсов, верно? Просто спросите людей, которые пострадали от этой ошибки в реальных проектах — они, я уверен, со мной согласятся.

              Еще раз: я не против идеи о том, что лучше писать чистый код. Но представьте себе на секунду, что это — не единственная ошибка переполнения в данном коде, что есть другие, но вы их пока не видите. Как думаете — стоит ждать, пока они взорвутся, или лучше оставить небольшой, как говорят инженеры, «запас прочности»?
                +2
                Мой комментарий — всего лишь ответ на весьма спорное заявление о том, что у Вас есть серебряная пуля, которая
                позволяет исключить риск данной (и любой подобной) ошибки
                Об исключении риска в вашем способе речи не идет. Он лишь отодвигает допустимые пределы значений.
                  0
                  Разумеется, в таком разрезе я неправ. Однако в качестве «серебряной пули» я предлагаю не увеличение длины используемых типов, а постановку задачи, включающую в себя предельно допустимые значения.

                  Иными словами, если вы написали библиотеку, которая может принимать на входе произвольный int, надо ожидать, что в нее передадут INT_MAX. Можно его передать и посмотреть, что будет. Можно долго вглядываться в код, ища там подобные этой «безобидные» строки. Но лучше всего везде, где int складывается с int результат класть в long. Просто так, на всякий «пожарный». Это — не «серебряная пуля», а просто верный практический способ, продиктованный опытом.

                  И я надеюсь, что в реальных задачах даже те люди, которые здесь со мной спорят, всё равно делают именно так.
                  +2
                  А С уже гарантирует, что long будет длиннее int'а? long гарантированно 32+ бит, но никак не 64.
                    +1
                    вообще-то, единственная гарантия в том, что long не короче int, который не короче short, который не короче char, чья длина равна 1, причем 1 байт не обязан быть равен 8 бит.

                    Я слышал, на некоторых специфических контроллерах все типы равны по длине, притом не 8 бит.
                      +2
                      Это не совсем правда. Дополнительно к указанным требованиям существуют ещё следующие: длина char не менее 8 бит, short и int — не менее 16, long — не менее 32, long long — не менее 64 (см. стандарт, он не гарантирует, кстати, что в целочисленных типах нет неиспользуемых бит, а я это, конечно, предполагал, когда переводил диапазоны значений в битовые ширины). В действительности для большинства платформ реальные значения совпадают с минимальными, за исключением того, что int на 32- и 64-битных платформах чаще всего 32-битный и long на 64-битной — 64-битный.
                      0
                      Зато в C99 есть long long, который не менее 64 бит. А также есть int32_t, int64_t. Не так уж все плохо.
                      +4
                      Просто спросите людей, которые пострадали от этой ошибки в реальных проектах
                      Насколько я понял из поста, при всём количестве пользователей JDK, эта ошибка в JDK проявилась 1 раз за 9 лет.

                      Насколько разумно обыскивать всех входящих в кинотеатр с раздеванием, потому что какой-то один дурак открыл в кинотеатре стрельбу латать такое редкое состояние, замедляя работу у всех?

                      А вот более разумное решение.
                      Есть qsort. Делаем qsort64. А далее два варианта:
                      1) Не очень удобный, но понятный для пользователя (в плане оценки скорости): честно пишем в документации, что qsort работает для N от 2-30 до 230 (а не 31), а дальше используйте qsort64. При вызове qsort с |N|>230 кидаем исключение «Invalid argument».
                      2) Удобный (но в какой-то момент пользователь может удивиться изменению скорости): при вызове qsort с |N|>230 прозрачно вызываем qsort64.
                      +3
                      В статье речь об алгоритмической чистоте, и если оставить код неизменным, а поменять лишь типы данных, то чистота кода никак не изменится и ошибка не исчезнет. Просто вероятность её возникновения станет меньше, но нулю равна не будет.
                      Эээ, нет. Вы не правы.
                      Сам алгоритм математически корректный, ошибки в нем нет.
                      Неверна лишь его реализация именно в контексте типов данных в ряде языков программирования.
                      Безусловно по любому всегда будут ограничения на объем памяти и тд (вдруг числа начнут не помещаться), но опять же, алгоритм будет чистым. А для учета ограничений ЯП или физической среды — как раз и есть исключения в ЯП.
                    +30
                    Жёлтый заголовок и содержимое ему под стать
                      +4
                      Заголовок и содержимое нормальные. Были в 2006-м году. А так все же знают давно. В FindBugs даже детектор про это есть про это:
                      IM: Computation of average could overflow (IM_AVERAGE_COMPUTATION_COULD_OVERFLOW)

                      The code computes the average of two integers using either division or signed right shift, and then uses the result as the index of an array. If the values being averaged are very large, this can overflow (resulting in the computation of a negative average). Assuming that the result is intended to be nonnegative, you can use an unsigned right shift instead. In other words, rather that using (low+high)/2, use (low+high) >>> 1

                      This bug exists in many earlier implementations of binary search and merge sort. Martin Buchholz found and fixed it in the JDK libraries, and Joshua Bloch widely publicized the bug pattern.
                      +3
                      Насколько я знаю, аналогичная проблема была с динамическим массивом (ArrayList) в Java буквально до совсем недавнего времени. В функции расширения было написано что-то вроде int newCapacity = capacity * 3 / 2;, вместо правильного int newCapacity = capacity + capacity / 2;.
                        –8
                        Ваш комментарий иллюстрирует мою точку зрения выше: наличие маленького запаса решает большинство ошибок переполнения. В практических (а не академических задачах) это очень важно.
                        +16
                        Только 10% программистов способны написать двоичный поиск

                        Как же все-таки правильно написать двоичный поиск?

                        Я не могу написать бинарный поиск

                        Срочная новость! Подходит к концу 2013 год, а люди так и не научились смотреть Википедию перед созданием уже созданного.
                          –2
                          «Срочная новость» — это перевод оригинального заголовка 2006 года.
                            +3
                            Хм, хотя в ленте Хабра такой заголовок действительно выглядит несколько странно. Сократил заголовок.
                            +3
                            Я столько «мегакрутых» статей на Хабр не написал, потому что перед написанием воспользовался поиском. Может, стоило тупо писать, как поступил автор этого топика? :-)
                            +6
                            Не важно, сколько у тебя памяти и прочих ресурсов, но создавать массив размера, переваливающего за int (пускай и в сложении) — это не здоровая идея. В конце концов, всегда есть сегментирование, кеши с вытеснением и пр. Массив такого размера если даже и заработает с исправленной реализацией binarySearch, подкинет проблем в другом месте.
                              +2
                              Я хотел написать именно такой комментарий. Поэтому только дополню. Проблема на мой взгляд вообще надумана, и в реальных задачах не случалась (просто какой то ушлый тестер зарепортил). Более того, проблема по прежнему осталась. Это int для индексации, а не long. Ну то есть мы отодвинули проблему от 2^30 до 2^31 (уж лучше бы он просто заменил на long тип данных)
                                0
                                Ну а я в свою очередь хотел написать про long :)
                              +2
                              «Чтобы абсолютно строго доказать корректность программы, её нужно протестировать на абсолютно всех возможных входных данных». Это немного не так. Надо просто очень аккуратно записывать все пост и предусловия всех операций, и тогда во многих частных случаях можно формально и абсолютно строго доказать корректность.
                                +4
                                Что-то у меня от статьи стойкое ощущение дежавю.
                                  +2
                                  Так ей семь лет уже с гаком.
                                • НЛО прилетело и опубликовало эту надпись здесь
                                    0
                                    В С/C++ (где нет оператора >>>) можно написать так:

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

                                    и чем это отличается от:
                                    int mid = (low + high) / 2;

                                    ?
                                      +1
                                      Оператор >>, примененный к беззнаковому числу, заполняет старшие разряды нулями, как и >>> в Яве.
                                        0
                                        А чем тогда он заполняет старшие разряды в случае с знаковым числом?
                                          +3
                                          Знаком.
                                          +3
                                          Оператор деления на 2 (в случае беззнаковых чисел) делает ровно то же самое. А вообще проблема высосана из пальца и в основном связана с тем, что в Java нет беззнаковых чисел. Индексировать массив знаковым числом — это глупость, которая приводит к описанным здесь результатам.
                                            0
                                            именно об этом я и пытался тонко потроллить…
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                0
                                                В тексте поста пояснили уже.

                                                Ну и вообще знаковым число должно быть ровно тогда, когда знак имеет смысл в вашей задаче.

                                                Кроме того, немногие знают, что переполнение знаковых числел в С (а значит и в нативной арифметике некоторых процов) приводит к непредсказуемым результатам, в отличие от беззнаковых.
                                                  +2
                                                  Ну и вообще — это все в теории, а на практике проще и безопаснее использовать именно знаковое число, потому что чуть вылетаем в промежуточных вычислениях в минус -> получаем оверфлоу, и как результат операторы сравнения работают не так как ожидается.

                                                  Даже далеко ходить не надо, вот код из статьи:
                                                  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.
                                                   }
                                                  

                                                  Казалось бы заменить на беззнаковое? И код упадет если в массиве будет один элемент, потому что high = mid — 1; может легко стать равным -1, а вверху while c <=. Со знаковым числом будет оверфлоу, и код упадет при обращении к массиву.
                                                  И подобных мест на практике встречается куча, и вы предлагаете в голове постоянно держать будет оверфлоу или нет? Нет уж, спасибо. Я достаточно в своей практике настрелял так себе в ногу, теперь по возможности использую только знаковые числа.

                                                  Алсо помимо безопасности, в данном примере знаковость удобна тем, что можно вернуть -1 если элемент не найден или индекс элемента. Если же вы будете использовать знаковые числа — то придется либо возвращать 2 числа (буль и индекс), либо возвращать индекс равный array.length, что имхо не так удобно в том же повседневном использовании.
                                                    0
                                                    И тем не менее, вы должны использовать ptrdiff_t/size_t в С++ (тут же ветка про С/C++?). А точнее, вы будете использовать типы, возращаемые итераторами, и это именно ptrdiff_t/size_t.
                                                      0
                                                      Вообще этот код на яве, а ptrdiff_t/size_t — это немного не по теме моего комментария. Я говорил, что по возможности надо использовать именно знаковый тип (кстати ptrdiff_t знаковый и не спроста).
                                                      +2
                                                      Что касается приведенного вами алгоритма, то общепринятым является работа с полуоткрытым диапазоном — слева включающий, а справа исключающий (как итераторы в STL — begin() принадлежит контейнеру, а end() — нет). Так вот, если перейти на эту модель, то приведенный код упрощается, а проблема исчезает т.к. high = mid — 1 превращается в high = mid.

                                                      По поводу возвращения -1, то да, есть такая проблема. Но это значит, что надо использовать знаковые числа именно в этих случаях, а не в всех. Например, сискол read() в линукс принимает size_t (беззнаковый) на вход, но возвращаетс ssize_t (знаковый) именно из-за необходимости иногда возвращать -1.
                                                        0
                                                        Кстати проблема не исчезает ;)
                                                        Код по прежнему падает, но только при пустом массиве и сразу на входе в цикл, ибо:
                                                        high = a.length — 1;
                                                        Пример вообще ярко показывает, как можно на беззнаковых сразу же настрелять себе в ногу, и это все надо постоянно держать в голове, ибо это все валится в рантайме, и если тест вдруг не покроет — очень плохо.
                                                        Как ни крути — операции сравнения используются чаше сдвигов, и контролировать сдвиги для знаковых переменных проще.

                                                        Для себя после многих лет практики я сделал однозначный вывод: по возможности использовать знаковые типы, а если хочется странного беззнакового, то трижды подумай. В частности для индексации массива удобнее именно знаковый тип, потому что создание массива размером 2^30 на 32-х битных платформах и 2^62 на 64 битных — это не самая здоровая мысль. Знакового типа данных для индексации массивов на практике хватает с головой, ибо адресное пространство раньше закончится.
                                                          +2
                                                          Вы не поняли. Я сказал «перейти на эту модель», что также включает high=a.length, while (low < high) {...} заметьте, кода стало меньше, это почти всегда хороший знак для программиста.

                                                          Этот случай красноречиво показывает, что если вам надо, чтобы индекс был отрицательным, значит в алгоритме есть проблема, его, как минимум, можно упростить.
                                                            +1
                                                            Ок, в этом алгоритме проблема исчезла. Я же не утверждал что её невозможно избежать, просто во-первых надо постоянно помнить, что ты стоишь на краю пропасти, и шаг назад, и ты уже падаешь. Мне например удобнее осознавать, что выскочи я в -1 (даже на промежуточных вычислениях) — у меня сравнение отработает как надо. Во-вторых — не всегда можно легко и интуитивно упростить алгоритм на знаковых числах, и быть уверенным, что он действительно работает.
                                                            Так что я останусь при своем мнении (сформированным годами практики), мне легче контролировать сдвиги для знаковых, чем сравнения для беззнаковых.
                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                        0
                                                        Ну тогда вы и комплексное можете взять, подходит же.
                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                              +2
                                              Кстати, эту ошибку вполне можно рассматривать как 64-битную ошибку. Она не проявит себя в 32-битной системе. Реальная сложная программа просто не будет оперировать массивами такого размера. Ведь у неё не один массив, а множество. И каждый из них, будет меньше 2^30. Курсовые работы с одним большим массивом не в счёт.

                                              И вот пришло время 64-битных программ и больших массивов. Программа, отлично проходящая все юнит-тесты, неожиданно начинает падать или вести себя не корректно в боевых условиях. И поди, ищи ошибку…

                                              И ошибка здесь в том, что неправильно в Си/Си++ для индексов использовать int. Для этого есть типы ptrdiff_t, size_t, intptr_t и так далее. Те ухищрения, которые приводятся в статье, всё равно не позволят обрабатывать массивы более чем из UINT_MAX элементов.

                                              Именно для подобных случаев и создавался анализатор Viva64. Да, он даёт много ложных срабатываний. Но тем несчастным, которые используют много памяти, он поможет. Он укажет, что для работы с указателями используются 32-битные типы данных.
                                                +2
                                                Вот только проблема в том, что в Яве нельзя для индексов использовать long, только int.
                                                +1
                                                В .net была исправлена во второй версии (2005 год). Стало:
                                                int index3 = index1 + (index2 - index1 >> 1)
                                                  +1
                                                  На первый взгляд всё в порядке, но для достаточно больших low и high (а именно, если их сумма больше 231-1) возникает ошибка. Их сумма становится отрицательным числом, и mid также получается отрицательным.

                                                  Да неужели?! Вот это новость, что при выходе за пределы переменной (особенно в signed типах) возникают проблемы!
                                                    +1
                                                    Такое ощущение, что у автора такая же ошибка возникла при поиске уже написанных статей на данную тему.
                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                        +2
                                                        В части языков это будет слишком поздно, т. к. переполнение происходит при суммировании. В этом случае можно расширять типы перед суммированием, но это тоже костыль. Проще mid = low + (high - low)/2.
                                                        +1
                                                        Эта программа и правильная, и нет. Нельзя говорить, что программа содержит ошибку, пока нет всех условий. Нужно указывать предусловия, постусловия и инварианты. Иначе кто угодно может придраться. А вдруг массив не отсортирован? А вдруг его длина больше int-а (long-а)? А что будет, если ключа не найдется или их много?

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

                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                        Самое читаемое