Взгляд на бинарный поиск и indexOf с тестами для сравнения различий в производительности
Чем больше данных у нас есть, тем более производительным мы хотим или хотим, чтобы наш поиск был для определенной части этих данных. В худшем случае мы не хотим, чтобы наше приложение работало медленно из-за неэффективного поиска. Давайте сначала рассмотрим простейшую форму поиска indexOf, а затем перейдем к двоичному поиску и тому, как они реализованы.
индекс
indexOf() может быть вашим первым выбором при попытке найти элемент в массиве. Это часть встроенного JavaScript, поэтому реализовать его будет проще всего / быстрее всего. Однако это может быть не лучшим выбором, если у вас есть массив из 100 000 элементов.
indexOf() - это линейный поиск, то есть он начинается с самого первого элемента в массиве и перебирает остальные, по одному элементу за раз, пока не найдет то, что ищет. Этот метод выполняется за O (n) времени, где n - длина массива.
Бинарный поиск
Бинарный поиск сокращает много времени за счет использования средних точек в массиве. Он работает, сравнивая значение поиска со средним элементом массива. Если значение поиска больше, все элементы справа от этой начальной средней точки используются для выполнения второго поиска. Затем рассчитывается новая средняя точка из правильного набора элементов. Процесс продолжается до тех пор, пока не будет найдено значение поиска. Это имеет сложность O (log n). (Примечание: я пару раз ссылался на Big O Notation, поэтому, если вы хотите узнать больше по этой теме, это отличные ресурсы: Видео HackerRank и Статья Hackernoon).
Гифка ниже представляет собой идеальную визуализацию того, как это работает по сравнению с линейным поиском:
Возможно, вы уже заметили, что двоичный поиск можно использовать только для отсортированных массивов. Это потенциальный недостаток. Если вы планируете выполнять только один поиск в несортированном массиве, использовать двоичный поиск не стоит. Дополнительная операция первой сортировки данных займет гораздо больше времени, чем простой линейный поиск в несортированном массиве. Еще один недостаток заключается в том, что это намного медленнее с меньшими наборами данных, как показано в примерах ниже.
Контрольные точки
Для каждого из тестовых примеров ниже я использовал сайт под названием JSBench.Me. Весь код, помещенный в настройку, запускается перед любым кодом тестового примера.
Настраивать
Сначала я создал функцию binarySearch:
Затем мне нужно было сгенерировать массу данных для поиска:
Теперь можно добавить несколько тестовых примеров. Обратите внимание, что для каждого тестового примера я также немного изменяю настройку.
Тестовый пример 1: большой отсортированный набор данных (100 000 элементов)
Для этого тестового примера я сначала добавил пару вещей в настройку:
array.sort((a, b) => a > b ? 1 : -1)
let findEl = array[getRandomNumber()]Переменная findEl гарантирует, что оба метода ищут один и тот же элемент, что делает сравнение справедливым. Полученные результаты:
Как видите, двоичный поиск выполняется значительно быстрее (в данном случае на 99,98%).
Тестовый пример 2: небольшой отсортированный набор данных (100 элементов)
Как и в предыдущем тестовом примере, array.sort() и переменная findEl добавляются в настройку. Однако на этот раз я помещаю в массив только 100 элементов. Полученные результаты:
В этом случае было бы проще использовать indexOf().
Тестовый пример 3: Большой несортированный набор данных (100 000 элементов)
В этом случае я убрал array.sort() из настройки и включил его в binarySearch() тестовый пример. Этот тест просто показывает, что если вы хотите выполнить только один поиск, не стоит сортировать массив непосредственно перед использованием двоичного поиска. Полученные результаты:
Заключение
Используете ли вы двоичный поиск или indexOf, это полностью зависит от того, как организованы ваши данные, чего вы пытаетесь достичь и нужно ли вообще учитывать производительность. Если у вас огромный набор отсортированных данных, можно использовать двоичный поиск. Если данных мало, возможно, будет проще / лучше реализовать indexOf. Если у вас много данных, но они не отсортированы и вы выполняете только один поиск, вам может быть лучше просто использовать indexOf. Надеюсь, это дало представление о плюсах и минусах каждого метода. Спасибо за прочтение!
