Автор оригинала: Sathiya Sarathi Gunasekaran.

Перейти Поиск в Python

Вступление

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

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

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

Поиск прыжка

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

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

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

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

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

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

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

Перейти К Шагам Поиска

Входные:

• Массив/список A размера n
• Ключ поиска элемент

Выход:

• Индекс совпадающего ключа поиска или -1 если элемент не найден

Шаги

• Шаг 1: Найдите длину отсортированного исходного списка – n(A)
• Шаг 2: Определите подходящий размер блока – m = √n
• Шаг 3: Итерация начинается с индекса элемента at i с шагом m и продолжается до тех пор, пока окно не достигнет конца списка.

• Шаг 4: Сравните A[i+m] ( i+m – последний индекс блока) и элемент

  • a) If A[i+m] , Return i+m ; Код Выходит

  • b) Если A[i+m] > item , перейдите к линейному поиску внутри блока, известного как производный список | B[i: i+m] Итерация и сравнение каждого элемента списка с ключом поиска и возврат совпадения

    • i если найдено; Выход кода c)
  • Если A[i+m] < item , перейдите к следующей итерации к шагу 4:arrows_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 .

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

• Шаг 4b – Когда есть сдвиг в сравнении . Если последний элемент блока/окна больше элемента , то срабатывает функция linear_search () .

• Шаг 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 чтобы указать, что пункт не был найден.

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

Бенчмаркинг – Скачковый поиск против линейного поиска

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

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

Анализ Big-O

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

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

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

Вывод

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