Вступление

Поиск нужных нам данных - давняя проблема до компьютеров. Как разработчики, мы создаем множество поисковых алгоритмов для эффективного извлечения данных.

Алгоритмы поиска можно разделить на две большие категории: последовательный и интервальный поиск. Последовательный поиск проверяет каждый элемент в структуре данных. Интервальный поиск проверяет различные точки данных (называемые интервалами), сокращая время, необходимое для поиска элемента с учетом отсортированного набора данных.

В этой статье вы рассмотрите Jump Search в Python - гибридную комбинацию последовательного поиска и интервального поиска по отсортированным массивам.

Перейти к поиску

С помощью Jump Search отсортированный массив данных разбивается на подмножества элементов, называемых блоками. Мы находим ключ поиска (входное значение), сравнивая кандидата на поиск в каждом блоке. Поскольку массив отсортирован, кандидат на поиск - это наивысшее значение блока.

При сравнении ключа поиска с кандидатом на поиск алгоритм может выполнить 1 из 3 действий:

1. Если поисковый кандидат меньше, чем поисковый ключ, мы проверим следующий блок.
2. Если поисковый кандидат больше, чем ключ поиска, мы выполним линейный поиск в текущем блоке.
3. Если кандидат для поиска совпадает с ключом поиска, вернуть кандидата

Размер блока выбирается как квадратный корень из длины массива. Следовательно, массивы с длиной n имеют размер блока √n , так как это в среднем дает наилучшую производительность для большинства массивов.

Было бы полезно проиллюстрировать, как это работает. Вот как Jump Search обработает значение 78 в массиве из 9 элементов:

{.ezlazyload}

В приведенном выше примере элемент находит за 5 шагов, так как в разделе линейного поиска есть две проверки.

Теперь, когда у нас есть высокоуровневое представление о том, как это работает, давайте посмотрим на псевдокодовую реализацию алгоритма.

Перейти к поисковым шагам

Входы:

• Массив / список A размера n
• Поиск по ключевому item

Выход:

• Индекс совпавшего ключа поиска или -1 если item не найден

Шаги

• Шаг 1. Найдите длину отсортированного исходного списка - n = len(A)
• Шаг 2: Определите подходящий размер блока - m = √n
• Шаг 3: Итерация начинается с индекса item в i = 0 с шагом m и продолжается до тех пор, пока окно не достигнет конца списка.
• Шаг 4. Сравните A[i+m] ( i+m - последний индекс блока) и item .
  • a) Если A[i+m] == item , вернуть i+m ; Код Выходы
  • б) Если A[i+m] > item , перейдите к линейному поиску внутри блока, известному как производный список B = A[i: i+m]
    • Итерировать и сравнить каждый элемент списка с ключом поиска и вернуть соответствующий i если он найден; Код Выходы
  • c) Если A[i+m] < item , перейдите со следующей итерации к шагу 4: arrow_clockwise:
• Шаг 5: Итерируйте элементы списка, которые не помещаются в блок, и верните соответствующий индекс i . Если совпадений не найдено, верните -1 ; Код Выходы

Теперь, когда мы понимаем, как это работает, давайте реализуем этот алгоритм на Python!

Выполнение

Зная, как работает Jump Search, давайте продолжим и реализуем его на Python:

 ''' 
 Jump Search function 
 Arguments: 
 A - The source list 
 item - Element for which the index needs to be found 
 ''' 
 import math 
 
 def jump_search(A, item): 
 print("Entering Jump Search") 
 n = len(A) # Length of the array 
 m = int(math.sqrt(n)) # Step length 
 i = 0 # Starting interval 
 
 while i != len(A)-1 and A[i] < item: 
 print("Processing Block - {}".format(A[i: i+m])) 
 if A[i+m-1] == item: # Found the search key 
 return i+m-1 
 elif A[i+m-1] > item: # Linear search for key in block 
 B = A[i: i+m-1] 
 return linear_search(B, item, i) 
 i += m 
 
 B = A[i:i+m] # Step 5 
 print("Processing Block - {}".format(B)) 
 return linear_search(B, item, i) 

Функция jump_search() принимает два аргумента - отсортированный список при оценке в качестве первого аргумента и элемент, который необходимо найти, во втором аргументе. Функция math.sqrt() используется для определения размера блока. Итерация облегчается while а приращение становится возможным за счет увеличенного i += m .

Вы могли заметить, что на Step 4b и Step 5 вызывается функция linear_search() Функция linear_search() запускается в одном из следующих сценариев.

• Step 4b - Когда есть сдвиг в сравнении . Если последний элемент блока / окна больше, чем item , запускается linear_search()

• Step 5 - Оставшиеся элементы исходного списка A которые не помещаются в блок, передаются как производный список в функцию linear_search()

linear_search() можно записать так:

 ''' 
 Linear Search function 
 Arguments: 
 B - The derived list 
 item - Element for which the index needs to be found 
 loc - The Index where the remaining block begins 
 ''' 
 
 def linear_search(B, item, loc): 
 print("\t Entering Linear Search") 
 i = 0 
 
 while i != len(B): 
 if B[i] == item: 
 return loc+i 
 i += 1 
 return -1 

На шаге 5 оставшиеся элементы исходного списка передаются в linear_search() как производный список. Сравнение выполняется с каждым элементом производного списка B

Соответствующий индекс производного списка добавляется к индексу исходного блока, чтобы обеспечить точное положение индекса элемента в исходном списке. Если совпадений не найдено, мы возвращаем -1 чтобы указать, что item не найден.

Полный фрагмент можно найти здесь .

Бенчмаркинг - поиск с переходом или линейный поиск

Время выполнения Jump Search можно сравнить с линейным поиском. Следующая визуализация показывает, как работают алгоритмы при поиске элемента в конце отсортированного массива. Чем короче полоса, тем лучше:

{.ezlazyload}

По мере увеличения количества элементов в списке поиск с переходом выполняется быстрее, чем алгоритм линейного поиска.

Анализ Big-O

Давайте проведем более общий анализ того, как работает Jump Search. Мы еще раз рассмотрим наихудший сценарий, когда искомый элемент находится в конце списка.

Для списка из n элементов и размера блока m , Jump Search в идеале выполнял бы n/m переходов. Учитывая, что размер блока равен √n , время выполнения тоже будет O(√n) .

Это помещает поиск Jump Search между линейным поиском (худший) со сложностью выполнения O(n) и двоичным поиском (лучший) со сложностью выполнения O(log n) . Следовательно, Jump Search можно использовать в местах, где двоичный поиск невозможен, а линейный поиск слишком дорог.

Заключение

В этой статье мы рассмотрели основы алгоритма Jump Search. Затем мы изучили, как Jump Search работает с псевдокодом, прежде чем реализовывать его в Python. После этого мы проанализировали, как работает Jump Search, а также его теоретические пределы скорости.