Веселые чуваки! 😎
Сегодняшняя история немного необычна, но, безусловно, интересна. Я изучал бинарные деревья поиска в Coursera когда профессор рассказывает историю, когда ошибка была обнаружена после 9 лет использования реализации двоичного поиска на Java в 2006 году. Это было обнаружено только тогда, когда кто-то использовал большие значения международных переменных low и high. Позвольте мне объяснить.
Перво-наперво! 🤓
Что такое бинарное дерево поиска?
Согласно Википедии, двоичное дерево поиска (BST) является
[…] Определенный тип контейнера: структура данных, которая хранит “элементы” в памяти. Они позволяют быстро искать, добавлять и удалять элементы и могут использоваться для реализации либо динамических наборов элементов, либо таблиц поиска, которые позволяют находить элемент по его ключу. Они хранят свои ключи в отсортированном порядке, чтобы поиск и другие операции могли использовать принцип двоичного поиска: при поиске ключа в дереве они пересекают дерево от корня до листа, сравнивая с ключами, хранящимися в узлах дерева, и на основе сравнения решают продолжить поиск в левом или правом поддеревьях. Это означает, что в среднем каждое сравнение позволяет операциям пропускать примерно половину дерева.
Хорошо, но можем ли мы подвести итоги? Конечно! Представьте себе дерево, где каждый элемент отсортирован, для поиска в нем нам нужно проверить, начиная с корня, меньше или больше элемент, чем начало. Если он меньше, мы идем налево, если больше, мы идем направо.
Давайте воспользуемся примером в gif. Нам нужно найти число 27; 21 – это корень, так что давайте начнем с этого.
- 27 больше или равно 21? Да, так что идите направо.
- 27 больше или равно 28? Нет, так что иди налево.
- 27 больше или равно 25? Нет, так что иди направо.
- 27 больше или равно 27? Да, мы нашли его!
GIF также показывает сравнение с поиском по отсортированному массиву. Мы видим, что BST намного быстрее!
Хорошо, теперь давайте посмотрим на реализацию ЛУЧШЕГО
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.
}
Это стандартный двоичный поиск в Java, это было написано в java.util. Массивы.
Глядя под разными углами, трудно найти ошибку, на самом деле, это правильно, но не на самом деле… Хорошо, позвольте мне объяснить…
Ошибка 👨 💻
Ошибка заключается в математических деталях этой строки:
int mid =(low + high) / 2;
Но почему?
Что ж, согласно Джошуа Блоху в его статье ,
В Жемчужинах программирования Бентли говорит, что аналогичная строка “устанавливает m в среднее значение l и u, усеченное до ближайшего целого числа. ” На первый взгляд это утверждение может показаться правильным, но оно терпит неудачу при больших значениях переменных int low и high. В частности, он терпит неудачу, если сумма низких и высоких значений превышает максимальное положительное значение int (231 – 1). Сумма переполняется до отрицательного значения, и значение остается отрицательным при делении на два. В C это приводит к выходу индекса массива за пределы с непредсказуемыми результатами. В Java он вызывает исключение ArrayIndexOutOfBoundsException.
Эта ошибка может проявляться для массивов, длина которых (в элементах) составляет 230 или более (примерно миллиард элементов). Это было немыслимо еще в 80-х, когда был написан Programming Pearls , но в наши дни это распространено в Google и других местах. В Programming Pearls Бентли говорит: “Хотя первый двоичный поиск был опубликован в 1946 году, первый двоичный поиск, который корректно работает для всех значений n не появлялся до 1962 года. ” Правда в том, что очень мало правильных версий когда-либо публиковалось, по крайней мере, на основных языках программирования.
ДВУ: Тип данных int имеет ограничение, при суммировании двух необычайно больших значений мы получаем переполнение, и оно имеет отрицательное значение, затем значение остается отрицательным при делении на два, вызывая ошибку.
Правильный путь 👍
Теперь давайте посмотрим, как правильно это исправить:
int mid = low + ((high - low) / 2);
теперь это предотвращает переполнение и (по крайней мере, на данный момент) делает его свободным от ошибок. По крайней мере, мы сильно подозреваем, что в нем нет ошибок.
Теперь, после этого, мы можем чувствовать себя лучше из-за того, что ошиблись в колледже, даже самые великие могут потерпеть неудачу! 😂
Увидимся позже!
Рекомендации:
Рекомендации:
Рекомендации:
Рекомендации:
Оригинал: “https://dev.to/matheusgomes062/a-bug-was-found-in-java-after-almost-9-years-of-hiding-2d4k”