Автор оригинала: Dasun Nirmitha.
Вступление
Будь то поиск в плейлисте вашей любимой песни или поиск по каталогу, чтобы выбрать ресторан для вашего следующего приема пищи, наша жизнь наполнена поиском вещей.
Точно так же компьютеры выполняют поисковые запросы по своим коллекциям и структурам данных. Однако, в отличие от людей, компьютерам приходится выполнять поиск в гораздо больших наборах данных в разы быстрее, чем людям.
Это побудило ученых-компьютерщиков разработать множество алгоритмов поиска, каждый из которых, как правило, более оптимален, чем некоторые другие в определенных коллекциях.
Поиск прыжков
Поиск переходов (также называемый Поиск блоков ) – это алгоритм, используемый для поиска положения целевого элемента в отсортированном наборе данных или структуре.
Вместо поиска массива по элементам (линейный поиск)- поиск по переходу оценивает блоки элементов. Вернее, так как это отсортированный массив – элемент с наибольшим значением в каждом блоке.
Если значение меньше целевого элемента, рассматривается следующий блок. Если значение выше целевого элемента, целевой элемент находится в текущем блоке. Если значение является целевым элементом – просто верните его.
Путем итеративного сдвига, или, скорее, прыжка вперед, мы либо найдем целевой элемент, либо достигнем конца коллекции, не найдя его.
Вот наглядное представление того, как работает поиск прыжков:
Очевидно, что Jump Search всегда ищет вперед по своим массивам, в отличие от методов поиска вперед и назад, таких как двоичный поиск. Такое поведение делает поиск прыжков намного более эффективным для поиска данных, хранящихся на физических дисках с вращающимися носителями.
Кроме того, еще один способ понять этот поиск – без блоков-между оцениваемыми элементами просто Разрыв перехода . Никакой реальный блок не сохраняется в памяти при выполнении алгоритма.
Реализация
Тем не менее, давайте реализуем поиск прыжков. Есть два подхода, которые вы можете использовать, без реального “победителя” между этими двумя – итеративная и рекурсивная реализация.
Выбор между этими двумя зависит от вас, и если вы не работаете над безумно огромными наборами данных, разницы в производительности быть не должно. Рекурсия приводит к более высокому использованию пространства процессора/памяти, но, как правило, более удобна для чтения и записи.
С другой стороны, если вы работаете с действительно большими наборами данных, вы, вероятно, использовали бы более эффективные, оптимизированные алгоритмы поиска.
Итеративная Реализация
Тем не менее, давайте начнем с итеративного подхода:
public static int jumpSearch(int[] arrayToSearch, int element) {
int blockSize = (int) Math.floor(Math.sqrt(arrayToSearch.length));
int currentLastIndex = blockSize-1;
// Jump to next block as long as target element is > currentLastIndex
// and the array end has not been reached
while (currentLastIndex < arrayToSearch.length && element > arrayToSearch[currentLastIndex]) {
currentLastIndex += blockSize;
}
// Find accurate position of target element using Linear Search
for (int currentSearchIndex = currentLastIndex - blockSize + 1;
currentSearchIndex <= currentLastIndex && currentSearchIndex < arrayToSearch.length; currentSearchIndex++) {
if (element == arrayToSearch[currentSearchIndex]) {
return currentSearchIndex;
}
}
// Target element not found. Return negative integer as element position.
return -1;
}
Во-первых, мы рассчитали размер блока. Как правило, квадратный корень из длины массива-это хороший размер для выбора. Это более подробно объясняется в разделе Анализ Big-O . Поиск в таком блоке, в конце концов, также будет дешевым для такого алгоритма, как линейный поиск.
Поскольку массив отсортирован, если значение нашего целевого элемента больше значения текущего элемента, то целевой элемент, безусловно, не может находиться внутри текущего блока. Поэтому мы переходим к следующему блоку и сравниваем целевой элемент со значением последнего индексного элемента нового блока.
Этот переход повторяется до тех пор, пока не будет найден блок, содержащий целевой элемент.
Если целевой элемент больше не превышает значение последнего элемента в блоке, то он должен находиться внутри блока, если он вообще существует.
Таким образом, мы найдем точное положение целевого элемента с помощью линейного поиска
Если мы дойдем до конца массива, не найдя блок, содержащий наш целевой элемент – его нет в массиве, и мы вернем -1 чтобы обозначить это.
Рекурсивная Реализация
Теперь, когда итеративная реализация устранена, давайте также рассмотрим рекурсивную реализацию:
public static int jumpSearchInit(int[] arrayToSearch, int element) {
int blockSize = (int) Math.sqrt(arrayToSearch.length);
// Hold the last index of the current block
int currentLastIndex = blockSize-1;
return jumpSearch(arrayToSearch, element, blockSize, currentLastIndex);
}
public static int jumpSearch(int[] arrayToSearch, int element, int blockSize, int currentLastIndex) {
if (currentLastIndex < arrayToSearch.length && element > arrayToSearch[currentLastIndex]) {
currentLastIndex += blockSize;
// Make recursive call to jumpSearch method
return jumpSearch(arrayToSearch, element, blockSize, currentLastIndex);
} else {
// Find accurate position of target element using linear search
for (int currentSearchIndex = currentLastIndex - blockSize + 1;currentSearchIndex <= currentLastIndex && currentSearchIndex < arrayToSearch.length; currentSearchIndex++) {
if (element == arrayToSearch[currentSearchIndex]) {
return currentSearchIndex;
}
}
}
// Target element not found. Return negative integer as element position.
return -1;
}
Рекурсивное выполнение поиска перехода работает таким же образом. Мы просто вызываем метод рекурсивно вместо цикла while .
Нам нужно использовать метод инициализатора, чтобы выполнить некоторые начальные вычисления. А именно, оптимальный размер блока и последний индекс самого первого блока.
После этого, пока наш целевой элемент больше, чем значение последнего элемента индекса текущего блока, мы рекурсивно вызываем метод поиска перехода, передавая ему параметры последующего блока.
Эта рекурсия заканчивается, как только был найден блок, содержащий целевой элемент, или если в конечном итоге был достигнут конец массива
В случае, если такой целевой блок был найден, мы выполняем линейный поиск по нему, чтобы найти положение целевого элемента.
Сравнительный анализ Поиска Прыжков
Давайте сравним поиск прыжков, запустив его с отсортированными целочисленными массивами различных размеров. Конечно, мы будем искать наихудший сценарий во всех этих (последний элемент):
| 10 | 0.3595 | 0.2267 | 0.3477 | 0.3119 |
| 10000 | 0.2210 | 0.5809 | 0.2225 | 0.3410 |
| 1000000 | 0.7754 | 0.7788 | 0.7906 | 0.7816 |
По сравнению с линейным поиском , который занимает 5,4209 мс , очевидно, что поиск прыжков значительно быстрее.
Анализ Big-O
Рассмотрим отсортированный целочисленный массив размером n с размером блока m .
В лучшем случае поиск по переходу найдет целевой элемент на краю самого первого блока, в котором он выполняет поиск. В свою очередь, это приводит к тому, что поиск переходов в лучшем случае имеет эффективность O(1) сложность в терминах Обозначения большого числа .
Напротив, учитывая наихудший случай, поиск прыжков будет последовательно переходить к самому последнему блоку поиска целевого элемента, что, в свою очередь, приведет к n/m количеству прыжков. Кроме того, если значение последнего элемента этого блока было больше, чем целевой элемент, поиск перехода выполнял бы линейный поиск с m-1 итерациями.
Git Essentials
Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!
Это приводит к тому, что поиск переходов выполняет (n/m) переходы с дополнительными m-1 итерациями. Это значение минимально при m = √n . Следовательно, оптимальный размер блока составляет √n .
Соответственно, поиск переходов поддерживает наихудшую и среднюю эффективность в случае O(√n) сложности.
Это делает примечательным отметить, что, хотя поиск по переходу очень эффективен для поиска массивов, особенно когда его поведение, направленное только на поиск, благоприятно, его средняя производительность позволяет ему находиться где-то между Двоичным поиском с его O(log n) сложностью и линейным поиском с O(n) сложностью.
Кроме того, поиск переходов последовательно требует, чтобы его массивы поиска были отсортированы в порядке возрастания заранее.
Вывод
Поиск переходов выполняется путем перехода вперед по блокам массива до тех пор, пока не будет найден блок, который может содержать данный элемент.
В этой статье мы реализовали итеративный и рекурсивный поиск переходов и сравнили алгоритм с массивами разных размеров.
Кроме того, мы провели анализ Big-O, доказывающий, как поиск прыжков достиг своей средней и наихудшей эффективности O(√n) .