Комментарии 57
Всегда всем бинарный поиск (сортировку слиянием) объяснял только с такой реализацией взятия среднего: int mid = low + ((high — low) / 2); По-моему это очевидно.
Комментарий удален
Я вот подвязался попробовать, в точности, как в старой статье просили — без тестирования, с первого раза, бла-бла. Вышло почему-то вообще безо всяких low и high, если быть точным — без high. 15 минут вдумчивого письма сверху вниз в vim без черновиков и досок — ничего особенного. Не быстро, да, но я и не ACM-щик ни разу в жизни, сам бинпоиск-то второй раз пишу — первый года полтора назад был. И кажется мне, он вышел тогда каким-то совсем другим.
Статья 2006 года, может быть, вы уже были в курсе?
Чрезвычайно поучительно и удивительно, как много высокопрофессиональных программистов делают простейшие технические ошибки. Я рискую получить по лицу за неуважение к авторитетам, но всё же сформулирую свою скромную идею, которая позволяет исключить риск данной (и любой подобной) ошибки.
Мой рецепт прост: если в вашем коде хотя бы теоретически возможно возникновение чисел порядка 2^31, значит тип int32_t и даже uint32_t — не для вас. А если вы всерьёз допускаете возможность того, что числа разрастутся бесконтрольно, извольте использовать длинную арифметику — потеря в производительности в два-три раза обычно не является критичной, в отличии от подобных ошибок. Представьте себе, катастрофу какого масштаба вызовет подобное в большом и серьёзном проекте…
Мой рецепт прост: если в вашем коде хотя бы теоретически возможно возникновение чисел порядка 2^31, значит тип int32_t и даже uint32_t — не для вас. А если вы всерьёз допускаете возможность того, что числа разрастутся бесконтрольно, извольте использовать длинную арифметику — потеря в производительности в два-три раза обычно не является критичной, в отличии от подобных ошибок. Представьте себе, катастрофу какого масштаба вызовет подобное в большом и серьёзном проекте…
Экстенсивные способы решения задач мне кажутся не совсем честными. В статье речь об алгоритмической чистоте, и если оставить код неизменным, а поменять лишь типы данных, то чистота кода никак не изменится и ошибка не исчезнет. Просто вероятность её возникновения станет меньше, но нулю равна не будет.
Я предполагал, что меня заминусуют, когда писал это. Поясню, что я имею в виду.
Алгоритмическая чистота, как особая дисциплина, несомненно имеет право на жизнь. Она нужна для того, чтобы в редких случаях выжимать максимум возможностей из имеющейся технологии, но больше — для того, чтобы тренировать мозг подобными этой проблемами.
Но что мне на самом деле не нравится — это попытка решать задачи «на кончике пера». Продумать всё невозможно (и данная статья — наглядное тому подтверждение). Экстенсивное решение позволяет сэкономить нервы за счет ресурсов и, разумеется, не всегда оно годно (как и любой тип решения не является серебряной пулей). Но в данном случае замена int на long не потратила бы много ресурсов, верно? Просто спросите людей, которые пострадали от этой ошибки в реальных проектах — они, я уверен, со мной согласятся.
Еще раз: я не против идеи о том, что лучше писать чистый код. Но представьте себе на секунду, что это — не единственная ошибка переполнения в данном коде, что есть другие, но вы их пока не видите. Как думаете — стоит ждать, пока они взорвутся, или лучше оставить небольшой, как говорят инженеры, «запас прочности»?
Алгоритмическая чистота, как особая дисциплина, несомненно имеет право на жизнь. Она нужна для того, чтобы в редких случаях выжимать максимум возможностей из имеющейся технологии, но больше — для того, чтобы тренировать мозг подобными этой проблемами.
Но что мне на самом деле не нравится — это попытка решать задачи «на кончике пера». Продумать всё невозможно (и данная статья — наглядное тому подтверждение). Экстенсивное решение позволяет сэкономить нервы за счет ресурсов и, разумеется, не всегда оно годно (как и любой тип решения не является серебряной пулей). Но в данном случае замена int на long не потратила бы много ресурсов, верно? Просто спросите людей, которые пострадали от этой ошибки в реальных проектах — они, я уверен, со мной согласятся.
Еще раз: я не против идеи о том, что лучше писать чистый код. Но представьте себе на секунду, что это — не единственная ошибка переполнения в данном коде, что есть другие, но вы их пока не видите. Как думаете — стоит ждать, пока они взорвутся, или лучше оставить небольшой, как говорят инженеры, «запас прочности»?
Мой комментарий — всего лишь ответ на весьма спорное заявление о том, что у Вас есть серебряная пуля, которая
Об исключении риска в вашем способе речи не идет. Он лишь отодвигает допустимые пределы значений.
позволяет исключить риск данной (и любой подобной) ошибкиОб исключении риска в вашем способе речи не идет. Он лишь отодвигает допустимые пределы значений.
Разумеется, в таком разрезе я неправ. Однако в качестве «серебряной пули» я предлагаю не увеличение длины используемых типов, а постановку задачи, включающую в себя предельно допустимые значения.
Иными словами, если вы написали библиотеку, которая может принимать на входе произвольный int, надо ожидать, что в нее передадут INT_MAX. Можно его передать и посмотреть, что будет. Можно долго вглядываться в код, ища там подобные этой «безобидные» строки. Но лучше всего везде, где int складывается с int результат класть в long. Просто так, на всякий «пожарный». Это — не «серебряная пуля», а просто верный практический способ, продиктованный опытом.
И я надеюсь, что в реальных задачах даже те люди, которые здесь со мной спорят, всё равно делают именно так.
Иными словами, если вы написали библиотеку, которая может принимать на входе произвольный int, надо ожидать, что в нее передадут INT_MAX. Можно его передать и посмотреть, что будет. Можно долго вглядываться в код, ища там подобные этой «безобидные» строки. Но лучше всего везде, где int складывается с int результат класть в long. Просто так, на всякий «пожарный». Это — не «серебряная пуля», а просто верный практический способ, продиктованный опытом.
И я надеюсь, что в реальных задачах даже те люди, которые здесь со мной спорят, всё равно делают именно так.
А С уже гарантирует, что long будет длиннее int'а? long гарантированно 32+ бит, но никак не 64.
вообще-то, единственная гарантия в том, что long не короче int, который не короче short, который не короче char, чья длина равна 1, причем 1 байт не обязан быть равен 8 бит.
Я слышал, на некоторых специфических контроллерах все типы равны по длине, притом не 8 бит.
Я слышал, на некоторых специфических контроллерах все типы равны по длине, притом не 8 бит.
Это не совсем правда. Дополнительно к указанным требованиям существуют ещё следующие: длина char не менее 8 бит, short и int — не менее 16, long — не менее 32, long long — не менее 64 (см. стандарт, он не гарантирует, кстати, что в целочисленных типах нет неиспользуемых бит, а я это, конечно, предполагал, когда переводил диапазоны значений в битовые ширины). В действительности для большинства платформ реальные значения совпадают с минимальными, за исключением того, что int на 32- и 64-битных платформах чаще всего 32-битный и long на 64-битной — 64-битный.
Зато в C99 есть long long, который не менее 64 бит. А также есть int32_t, int64_t. Не так уж все плохо.
Просто спросите людей, которые пострадали от этой ошибки в реальных проектахНасколько я понял из поста, при всём количестве пользователей JDK, эта ошибка в JDK проявилась 1 раз за 9 лет.
Насколько разумно
А вот более разумное решение.
Есть qsort. Делаем qsort64. А далее два варианта:
1) Не очень удобный, но понятный для пользователя (в плане оценки скорости): честно пишем в документации, что qsort работает для N от 2-30 до 230 (а не 31), а дальше используйте qsort64. При вызове qsort с |N|>230 кидаем исключение «Invalid argument».
2) Удобный (но в какой-то момент пользователь может удивиться изменению скорости): при вызове qsort с |N|>230 прозрачно вызываем qsort64.
В статье речь об алгоритмической чистоте, и если оставить код неизменным, а поменять лишь типы данных, то чистота кода никак не изменится и ошибка не исчезнет. Просто вероятность её возникновения станет меньше, но нулю равна не будет.Эээ, нет. Вы не правы.
Сам алгоритм математически корректный, ошибки в нем нет.
Неверна лишь его реализация именно в контексте типов данных в ряде языков программирования.
Безусловно по любому всегда будут ограничения на объем памяти и тд (вдруг числа начнут не помещаться), но опять же, алгоритм будет чистым. А для учета ограничений ЯП или физической среды — как раз и есть исключения в ЯП.
Жёлтый заголовок и содержимое ему под стать
Заголовок и содержимое нормальные. Были в 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.
Насколько я знаю, аналогичная проблема была с динамическим массивом (ArrayList) в Java буквально до совсем недавнего времени. В функции расширения было написано что-то вроде
int newCapacity = capacity * 3 / 2;, вместо правильного int newCapacity = capacity + capacity / 2;.
Только 10% программистов способны написать двоичный поиск
Как же все-таки правильно написать двоичный поиск?
Я не могу написать бинарный поиск
Срочная новость! Подходит к концу 2013 год, а люди так и не научились смотреть Википедию перед созданием уже созданного.
Как же все-таки правильно написать двоичный поиск?
Я не могу написать бинарный поиск
Срочная новость! Подходит к концу 2013 год, а люди так и не научились смотреть Википедию перед созданием уже созданного.
Не важно, сколько у тебя памяти и прочих ресурсов, но создавать массив размера, переваливающего за int (пускай и в сложении) — это не здоровая идея. В конце концов, всегда есть сегментирование, кеши с вытеснением и пр. Массив такого размера если даже и заработает с исправленной реализацией binarySearch, подкинет проблем в другом месте.
Я хотел написать именно такой комментарий. Поэтому только дополню. Проблема на мой взгляд вообще надумана, и в реальных задачах не случалась (просто какой то ушлый тестер зарепортил). Более того, проблема по прежнему осталась. Это int для индексации, а не long. Ну то есть мы отодвинули проблему от 2^30 до 2^31 (уж лучше бы он просто заменил на long тип данных)
«Чтобы абсолютно строго доказать корректность программы, её нужно протестировать на абсолютно всех возможных входных данных». Это немного не так. Надо просто очень аккуратно записывать все пост и предусловия всех операций, и тогда во многих частных случаях можно формально и абсолютно строго доказать корректность.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
В С/C++ (где нет оператора >>>) можно написать так:
mid = ((unsigned int)low + (unsigned int)high)) >> 1;
и чем это отличается от:
int mid = (low + high) / 2;
?
Оператор
>>, примененный к беззнаковому числу, заполняет старшие разряды нулями, как и >>> в Яве.А чем тогда он заполняет старшие разряды в случае с знаковым числом?
Оператор деления на 2 (в случае беззнаковых чисел) делает ровно то же самое. А вообще проблема высосана из пальца и в основном связана с тем, что в Java нет беззнаковых чисел. Индексировать массив знаковым числом — это глупость, которая приводит к описанным здесь результатам.
именно об этом я и пытался тонко потроллить…
НЛО прилетело и опубликовало эту надпись здесь
В тексте поста пояснили уже.
Ну и вообще знаковым число должно быть ровно тогда, когда знак имеет смысл в вашей задаче.
Кроме того, немногие знают, что переполнение знаковых числел в С (а значит и в нативной арифметике некоторых процов) приводит к непредсказуемым результатам, в отличие от беззнаковых.
Ну и вообще знаковым число должно быть ровно тогда, когда знак имеет смысл в вашей задаче.
Кроме того, немногие знают, что переполнение знаковых числел в С (а значит и в нативной арифметике некоторых процов) приводит к непредсказуемым результатам, в отличие от беззнаковых.
Ну и вообще — это все в теории, а на практике проще и безопаснее использовать именно знаковое число, потому что чуть вылетаем в промежуточных вычислениях в минус -> получаем оверфлоу, и как результат операторы сравнения работают не так как ожидается.
Даже далеко ходить не надо, вот код из статьи:
Казалось бы заменить на беззнаковое? И код упадет если в массиве будет один элемент, потому что high = mid — 1; может легко стать равным -1, а вверху while c <=. Со знаковым числом будет оверфлоу, и код упадет при обращении к массиву.
И подобных мест на практике встречается куча, и вы предлагаете в голове постоянно держать будет оверфлоу или нет? Нет уж, спасибо. Я достаточно в своей практике настрелял так себе в ногу, теперь по возможности использую только знаковые числа.
Алсо помимо безопасности, в данном примере знаковость удобна тем, что можно вернуть -1 если элемент не найден или индекс элемента. Если же вы будете использовать знаковые числа — то придется либо возвращать 2 числа (буль и индекс), либо возвращать индекс равный array.length, что имхо не так удобно в том же повседневном использовании.
Даже далеко ходить не надо, вот код из статьи:
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, что имхо не так удобно в том же повседневном использовании.
И тем не менее, вы должны использовать ptrdiff_t/size_t в С++ (тут же ветка про С/C++?). А точнее, вы будете использовать типы, возращаемые итераторами, и это именно ptrdiff_t/size_t.
Что касается приведенного вами алгоритма, то общепринятым является работа с полуоткрытым диапазоном — слева включающий, а справа исключающий (как итераторы в STL — begin() принадлежит контейнеру, а end() — нет). Так вот, если перейти на эту модель, то приведенный код упрощается, а проблема исчезает т.к. high = mid — 1 превращается в high = mid.
По поводу возвращения -1, то да, есть такая проблема. Но это значит, что надо использовать знаковые числа именно в этих случаях, а не в всех. Например, сискол read() в линукс принимает size_t (беззнаковый) на вход, но возвращаетс ssize_t (знаковый) именно из-за необходимости иногда возвращать -1.
По поводу возвращения -1, то да, есть такая проблема. Но это значит, что надо использовать знаковые числа именно в этих случаях, а не в всех. Например, сискол read() в линукс принимает size_t (беззнаковый) на вход, но возвращаетс ssize_t (знаковый) именно из-за необходимости иногда возвращать -1.
Кстати проблема не исчезает ;)
Код по прежнему падает, но только при пустом массиве и сразу на входе в цикл, ибо:
high = a.length — 1;
Пример вообще ярко показывает, как можно на беззнаковых сразу же настрелять себе в ногу, и это все надо постоянно держать в голове, ибо это все валится в рантайме, и если тест вдруг не покроет — очень плохо.
Как ни крути — операции сравнения используются чаше сдвигов, и контролировать сдвиги для знаковых переменных проще.
Для себя после многих лет практики я сделал однозначный вывод: по возможности использовать знаковые типы, а если хочетсястранного беззнакового, то трижды подумай. В частности для индексации массива удобнее именно знаковый тип, потому что создание массива размером 2^30 на 32-х битных платформах и 2^62 на 64 битных — это не самая здоровая мысль. Знакового типа данных для индексации массивов на практике хватает с головой, ибо адресное пространство раньше закончится.
Код по прежнему падает, но только при пустом массиве и сразу на входе в цикл, ибо:
high = a.length — 1;
Пример вообще ярко показывает, как можно на беззнаковых сразу же настрелять себе в ногу, и это все надо постоянно держать в голове, ибо это все валится в рантайме, и если тест вдруг не покроет — очень плохо.
Как ни крути — операции сравнения используются чаше сдвигов, и контролировать сдвиги для знаковых переменных проще.
Для себя после многих лет практики я сделал однозначный вывод: по возможности использовать знаковые типы, а если хочется
Вы не поняли. Я сказал «перейти на эту модель», что также включает high=a.length, while (low < high) {...} заметьте, кода стало меньше, это почти всегда хороший знак для программиста.
Этот случай красноречиво показывает, что если вам надо, чтобы индекс был отрицательным, значит в алгоритме есть проблема, его, как минимум, можно упростить.
Этот случай красноречиво показывает, что если вам надо, чтобы индекс был отрицательным, значит в алгоритме есть проблема, его, как минимум, можно упростить.
Ок, в этом алгоритме проблема исчезла. Я же не утверждал что её невозможно избежать, просто во-первых надо постоянно помнить, что ты стоишь на краю пропасти, и шаг назад, и ты уже падаешь. Мне например удобнее осознавать, что выскочи я в -1 (даже на промежуточных вычислениях) — у меня сравнение отработает как надо. Во-вторых — не всегда можно легко и интуитивно упростить алгоритм на знаковых числах, и быть уверенным, что он действительно работает.
Так что я останусь при своем мнении (сформированным годами практики), мне легче контролировать сдвиги для знаковых, чем сравнения для беззнаковых.
Так что я останусь при своем мнении (сформированным годами практики), мне легче контролировать сдвиги для знаковых, чем сравнения для беззнаковых.
НЛО прилетело и опубликовало эту надпись здесь
Кстати, эту ошибку вполне можно рассматривать как 64-битную ошибку. Она не проявит себя в 32-битной системе. Реальная сложная программа просто не будет оперировать массивами такого размера. Ведь у неё не один массив, а множество. И каждый из них, будет меньше 2^30. Курсовые работы с одним большим массивом не в счёт.
И вот пришло время 64-битных программ и больших массивов. Программа, отлично проходящая все юнит-тесты, неожиданно начинает падать или вести себя не корректно в боевых условиях. И поди, ищи ошибку…
И ошибка здесь в том, что неправильно в Си/Си++ для индексов использовать int. Для этого есть типы ptrdiff_t, size_t, intptr_t и так далее. Те ухищрения, которые приводятся в статье, всё равно не позволят обрабатывать массивы более чем из UINT_MAX элементов.
Именно для подобных случаев и создавался анализатор Viva64. Да, он даёт много ложных срабатываний. Но тем несчастным, которые используют много памяти, он поможет. Он укажет, что для работы с указателями используются 32-битные типы данных.
И вот пришло время 64-битных программ и больших массивов. Программа, отлично проходящая все юнит-тесты, неожиданно начинает падать или вести себя не корректно в боевых условиях. И поди, ищи ошибку…
И ошибка здесь в том, что неправильно в Си/Си++ для индексов использовать int. Для этого есть типы ptrdiff_t, size_t, intptr_t и так далее. Те ухищрения, которые приводятся в статье, всё равно не позволят обрабатывать массивы более чем из UINT_MAX элементов.
Именно для подобных случаев и создавался анализатор Viva64. Да, он даёт много ложных срабатываний. Но тем несчастным, которые используют много памяти, он поможет. Он укажет, что для работы с указателями используются 32-битные типы данных.
В .net была исправлена во второй версии (2005 год). Стало:
int index3 = index1 + (index2 - index1 >> 1)
На первый взгляд всё в порядке, но для достаточно больших low и high (а именно, если их сумма больше 231-1) возникает ошибка. Их сумма становится отрицательным числом, и mid также получается отрицательным.
Да неужели?! Вот это новость, что при выходе за пределы переменной (особенно в signed типах) возникают проблемы!
Такое ощущение, что у автора такая же ошибка возникла при поиске уже написанных статей на данную тему.
НЛО прилетело и опубликовало эту надпись здесь
Эта программа и правильная, и нет. Нельзя говорить, что программа содержит ошибку, пока нет всех условий. Нужно указывать предусловия, постусловия и инварианты. Иначе кто угодно может придраться. А вдруг массив не отсортирован? А вдруг его длина больше int-а (long-а)? А что будет, если ключа не найдется или их много?
Насколько я вижу, вся соль шестой строки не в переполнении, а в том, что вычисления остаются в пределах размера массива.
Насколько я вижу, вся соль шестой строки не в переполнении, а в том, что вычисления остаются в пределах размера массива.
Можно написать шаблон с беззнаковым целым T, и потом подставлять туда uint_8, uint_16 - их-то можно проверить по всему диапазону. Ну, и останется поверить в обобщенность шаблона для uint_32 и uint_64.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка