Рубрики
Без рубрики

Алгоритмы поиска в Python

Автор оригинала: Guest Contributor.

Алгоритмы поиска в Python

Вступление

Поиск данных, хранящихся в различных структурах данных, является важной частью практически каждого отдельного приложения.

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

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

  • Операторы членства
  • Линейный поиск
  • Бинарный поиск
  • Поиск прыжка
  • Поиск Фибоначчи
  • Экспоненциальный поиск
  • Интерполяционный поиск

Операторы членства

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

Одной из наиболее распространенных проблем в области информатики является поиск в коллекции и определение того, присутствует ли данный объект в коллекции или нет.

Почти каждый язык программирования имеет свою собственную реализацию базового алгоритма поиска, обычно в виде функции, которая возвращает логическое значение True или False , когда элемент найден в данной коллекции элементов.

В Python самый простой способ поиска объекта – использовать операторы Membership – названные таким образом, потому что они позволяют нам определить, является ли данный объект членом коллекции.

Эти операторы могут использоваться с любой итеративной структурой данных в Python, включая строки, Списки и кортежи.

  • in – Возвращает True , если данный элемент является частью структуры.
  • not in – Возвращает True , если данный элемент не является частью структуры.
>>> 'apple' in ['orange', 'apple', 'grape']
True
>>> 't' in 'stackabuse'
True
>>> 'q' in 'stackabuse'
False
>>> 'q' not in 'stackabuse'
True

Операторы членства достаточны, когда все, что нам нужно сделать, это найти, существует ли подстрока в данной строке, или определить, пересекаются ли две строки, списки или кортежи с точки зрения объектов, которые они содержат.

В большинстве случаев нам нужно положение элемента в последовательности, в дополнение к определению того, существует ли он или нет; операторы членства не удовлетворяют этому требованию.

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

Линейный поиск

Линейный поиск – один из самых простых алгоритмов поиска и самый простой для понимания. Мы можем думать об этом как о расширенной версии нашей собственной реализации оператора Python in .

Алгоритм состоит из итерации по массиву и возврата индекса первого вхождения элемента после его нахождения:

def LinearSearch(lys, element):
    for i in range (len(lys)):
        if lys[i] == element:
            return i
    return -1

Итак, если мы используем функцию для вычисления:

>>> print(LinearSearch([1,2,3,4,5,2,1], 2))

После выполнения кода нас встречают:

1

Это индекс первого вхождения элемента, который мы ищем, имея в виду, что индексы Python основаны на 0.

Временная сложность линейного поиска равна O(n) , что означает, что время, затраченное на выполнение, увеличивается с увеличением количества элементов в нашем входном списке lys .

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

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

Бинарный поиск

Бинарный поиск следует методологии разделяй и властвуй . Это быстрее, чем линейный поиск, но требует, чтобы массив был отсортирован до выполнения алгоритма.

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

  • Если mid – это элемент, который мы ищем (в лучшем случае), мы возвращаем его индекс.
  • Если нет, то мы определяем , на какой стороне mid | vail с большей вероятностью будет находиться val , основываясь на том, меньше или больше mid , и отбрасываем другую сторону массива. Затем мы рекурсивно или итеративно выполняем те же шаги, выбирая новое значение для
  • mid , сравнивая его с val и отбрасывая половину возможных совпадений на каждой итерации алгоритма.

Алгоритм бинарного поиска может быть записан рекурсивно или итеративно. Рекурсия обычно медленнее в Python , потому что она требует выделения новых кадров стека.

Поскольку хороший алгоритм поиска должен быть максимально быстрым и точным, давайте рассмотрим итеративную реализацию бинарного поиска:

def BinarySearch(lys, val):
    first = 0
    last = len(lys)-1
    index = -1
    while (first <= last) and (index == -1):
        mid = (first+last)//2
        if lys[mid] == val:
            index = mid
        else:
            if val

Если мы используем функцию для вычисления:

>>> BinarySearch([10,20,30,40,50], 20)

Мы получаем результат:

1

Который является индексом значения, которое мы ищем.

Действие, которое алгоритм выполняет следующим в каждой итерации, является одной из нескольких возможностей:

  • Возврат индекса текущего элемента
  • Поиск по левой половине массива
  • Поиск в правой половине массива

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

Одним из недостатков бинарного поиска является то, что если в массиве имеется несколько вхождений элемента, он возвращает не индекс первого элемента, а индекс элемента, ближайшего к середине:

>>> print(BinarySearch([4,4,4,4,4], 4))

Запуск этого фрагмента кода приведет к индексации среднего элемента:

1

Для сравнения выполнение линейного поиска по одному и тому же массиву вернет:

0

Который является индексом элемента first . Однако мы не можем категорически утверждать, что двоичный поиск не работает, если массив содержит один и тот же элемент дважды – он может работать так же, как линейный поиск, и в некоторых случаях возвращать первое вхождение элемента.

Если мы выполним двоичный поиск по массиву [1,2,3,4,4,5] например, и найдем 4, то получим 3 в результате.

Бинарный поиск довольно часто используется на практике, потому что он эффективен и быстр по сравнению с линейным поиском. Однако у него есть некоторые недостатки, такие как его зависимость от оператора ///. Существует много других алгоритмов поиска разделяй и властвуй , которые являются производными от бинарного поиска, давайте рассмотрим некоторые из них далее.

Поиск прыжка

Jump Search похож на бинарный поиск в том, что он работает с отсортированным массивом и использует аналогичный подход divide and conquer для поиска по нему.

Его можно классифицировать как усовершенствование алгоритма линейного поиска, поскольку он зависит от линейного поиска для выполнения фактического сравнения при поиске значения.

Учитывая сортированный массив, вместо того чтобы искать элементы массива постепенно, мы ищем в прыжках . Итак , в нашем входном списке list , если у нас есть размер прыжка jump , наш алгоритм будет рассматривать элементы в порядке lys[0] , lys[0+jump] , lys[0+2jump] , lys[0+3jump] и так далее.

С каждым прыжком мы сохраняем предыдущее значение, на которое смотрели, и его индекс. Когда мы находим набор значений , где lys[i] lys[i+jump] , мы выполняем линейный поиск с lys[i] в качестве самого левого элемента и lys[i+jump] в качестве самого правого элемента в нашем наборе поиска:

import math

def JumpSearch (lys, val):
    length = len(lys)
    jump = int(math.sqrt(length))
    left, right = 0, 0
    while left < length and lys[left] <= val:
        right = min(length - 1, left + jump)
        if lys[left] <= val and lys[right] >= val:
            break
        left += jump;
    if left >= length or lys[left] > val:
        return -1
    right = min(length - 1, right)
    i = left
    while i <= right and lys[i] <= val:
        if lys[i] == val:
            return i
        i += 1
    return -1

Поскольку это сложный алгоритм, давайте рассмотрим пошаговое вычисление поиска прыжка с этим входом:

>>> print(JumpSearch([1,2,3,4,5,6,7,8,9], 5))
  • Поиск прыжка сначала определит размер прыжка, вычисляя math.sqrt(len(lys)) . Поскольку у нас есть 9 элементов, размер прыжка будет равен.
  • Далее мы вычисляем значение переменной right , которое является минимумом длины массива минус 1, или значение left+jump , которое в нашем случае будет равно. Поскольку 3 меньше 8, мы используем 3 в качестве значения right .
  • Теперь мы проверяем, находится ли наш поисковый элемент 5 между lys[0] и lys[3] . Поскольку 5 не находится между 1 и 4, мы идем дальше.
  • Затем мы снова делаем вычисления и проверяем, находится ли наш поисковый элемент между lys[3] и lys[6] , где 6-3+прыжок. Поскольку 5 находится между 4 и 7, мы делаем линейный поиск по элементам между lys[3] и lys[6] и возвращаем индекс нашего элемента как:
4

Временная сложность поиска прыжка равна O(√n) , где √n – размер прыжка, а n – длина списка, помещая поиск прыжка между алгоритмами линейного поиска и бинарного поиска с точки зрения эффективности.

Единственным наиболее важным преимуществом скачкового поиска по сравнению с двоичным поиском является то, что он не полагается на оператор деления ( / ).

В большинстве процессоров использование оператора деления является дорогостоящим по сравнению с другими основными арифметическими операциями (сложение, вычитание и умножение), поскольку реализация алгоритма деления является итеративной.

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

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

Поиск Фибоначчи

Поиск Фибоначчи – это еще один алгоритм “разделяй и властвуй”, который имеет сходство как с бинарным поиском, так и с поиском прыжков. Он получил свое название потому, что использует числа Фибоначчи для вычисления размера блока или диапазона поиска на каждом шаге.

Числа Фибоначчи начинаются с нуля и следуют шаблону 0, 1, 1, 2, 3, 5, 8, 13, 21… где каждый элемент является сложением двух чисел, непосредственно предшествующих ему.

Алгоритм работает с тремя числами Фибоначчи одновременно. Назовем три числа ibm , ibm_minus_1 и ibm_minus_2 где fibM_minus_1 и ibm_minus_2 – это два числа непосредственно перед fibM в последовательности:

fibM = fibM_minus_1 + fibM_minus_2

Мы инициализируем значения 0,1 и 1 или первые три числа в последовательности Фибоначчи, чтобы избежать ошибки индекса в случае, когда наш поисковый массив lys содержит очень небольшое количество элементов.

Затем мы выбираем наименьшее число последовательности Фибоначчи , которое больше или равно числу элементов в нашем поисковом массиве lys , как значение fibM , а два числа Фибоначчи непосредственно перед ним как значения fibM_minus_1 и fibM_minus_2 . В то время как массив имеет оставшиеся элементы и значение ibm больше единицы, мы:

  • Сравните val со значением блока в диапазоне до ibm_minus_2 и верните индекс элемента , если он совпадает.
  • Если значение больше, чем элемент, на который мы сейчас смотрим, мы перемещаем значения fibM , fibM_minus_1 и fibM_minus_2 на два шага вниз в последовательности Фибоначчи и сбрасываем индекс на индекс элемента.
  • Если значение меньше, чем элемент, на который мы сейчас смотрим, мы перемещаем значения f ibM , ibm_minus_1 и fibM_minus_2 на один шаг вниз в последовательности Фибоначчи.

Давайте посмотрим на реализацию этого алгоритма на Python:

def FibonacciSearch(lys, val):
    fibM_minus_2 = 0
    fibM_minus_1 = 1
    fibM = fibM_minus_1 + fibM_minus_2
    while (fibM < len(lys)):
        fibM_minus_2 = fibM_minus_1
        fibM_minus_1 = fibM
        fibM = fibM_minus_1 + fibM_minus_2
    index = -1;
    while (fibM > 1):
        i = min(index + fibM_minus_2, (len(lys)-1))
        if (lys[i] < val):
            fibM = fibM_minus_1
            fibM_minus_1 = fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
            index = i
        elif (lys[i] > val):
            fibM = fibM_minus_2
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        else :
            return i
    if(fibM_minus_1 and index < (len(lys)-1) and lys[index+1] == val):
        return index+1;
    return -1

Если мы используем функцию поиска Фибоначчи для вычисления:

>>> print(FibonacciSearch([1,2,3,4,5,6,7,8,9,10,11], 6))

Давайте рассмотрим пошаговый процесс этого поиска:

  • Определение наименьшего числа Фибоначчи, большего или равного длине списка как ibm ; в этом случае наименьшее число Фибоначчи, удовлетворяющее нашим требованиям, равно 13.
  • Значения будут назначены следующим образом:
    • ibm
    • film_minus_1
    • ibm_minus_2
    • индекс = -1

  • Далее мы проверяем элемент lys[4] , где 4-минимум -1+5 . Поскольку значение lys[4] равно 5, что меньше искомого значения, мы перемещаем числа Фибоначчи на один шаг вниз в последовательности, делая значения:

    • ibm
    • film_minus_1
    • ibm_minus_2
    • индекс

  • Далее мы проверяем элемент lys[7] , где 7-минимум 4+3. Поскольку значение lys[7] равно 8, что больше искомого значения, мы перемещаем числа Фибоначчи на два шага вниз в последовательности.

    • ibm
    • film_minus_1
    • ibm_minus_2
    • индекс
  • Теперь мы проверяем элемент lys[5] , где 5-минимум 4+1 . Значение lys[5] равно 6, что является значением, которое мы ищем!

Результат, как и ожидалось, таков:

5

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

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

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

Экспоненциальный поиск

Экспоненциальный поиск – это еще один алгоритм поиска, который может быть реализован довольно просто в Python, по сравнению с поиском прыжка и поиском Фибоначчи, которые оба немного сложны. Он также известен под названиями галопирующий поиск , удвоенный поиск и Струзик поиск .

Экспоненциальный поиск зависит от бинарного поиска для выполнения окончательного сравнения значений. Алгоритм работает следующим образом:

  • Определение диапазона, в котором, вероятно, будет находиться искомый элемент
  • Использование двоичного поиска диапазона для поиска точного индекса элемента

Реализация алгоритма экспоненциального поиска на Python выглядит следующим образом:

def ExponentialSearch(lys, val):
    if lys[0] == val:
        return 0
    index = 1
    while index < len(lys) and lys[index] <= val:
        index = index * 2
    return BinarySearch( arr[:min(index, len(lys))], val)

Если мы используем функцию для нахождения значения:

>>> print(ExponentialSearch([1,2,3,4,5,6,7,8],3))

Алгоритм работает следующим образом:

  • Проверяя, соответствует ли первый элемент в списке искомому значению – поскольку lys[0] равен 1, а мы ищем 3, мы устанавливаем индекс равным 1 и двигаемся дальше.

  • Перебираем все элементы в списке, и пока элемент на индексной позиции меньше или равен нашему значению, экспоненциально увеличиваем значение index кратно двум:

    • индекс, lys[1] равен 2, что меньше 3, поэтому индекс умножается на 2 и устанавливается равным 2.
    • индекс, lys[2] равен 3, что равно 3, поэтому индекс умножается на 2 и устанавливается равным 4.
    • индекс, lys[4] равен 5, что больше 3; в этой точке цикл прерывается.
  • Затем он выполняет двоичный поиск путем нарезки списка; are[:4] . В Python это означает, что подсписок будет содержать все элементы вплоть до 4-го элемента, поэтому мы фактически вызываем:
>>> BinarySearch([1,2,3,4], 3)

который вернется:

2

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

Экспоненциальный поиск выполняется в O(log i) time, где i – индекс искомого элемента. В худшем случае временная сложность равна O(log n) , когда последним элементом является искомый элемент ( n – длина массива).

Экспоненциальный поиск работает лучше, чем двоичный, когда искомый элемент находится ближе к началу массива. На практике мы используем экспоненциальный поиск, потому что это один из наиболее эффективных алгоритмов поиска для неограниченных или бесконечных массивов .

Интерполяционный поиск

Интерполяционный поиск – это еще один алгоритм “разделяй и властвуй”, аналогичный бинарному поиску. В отличие от бинарного поиска, он не всегда начинается с середины. Интерполяционный поиск вычисляет вероятное положение искомого элемента по формуле:

index = low + [(val-lys[low])*(high-low) / (lys[high]-lys[low])]

Где находятся переменные:

  • lys – наш входной массив
  • вал – элемент, который мы ищем
  • индекс – вероятный индекс элемента поиска. Это вычисляется как более высокое значение, когда val ближе по значению к элементу в конце массива ( lys[high] ), и более низкое, когда val ближе по значению к элементу в начале массива ( lys[low] )
  • low – начальный индекс массива
  • high – последний индекс массива

Алгоритм осуществляет поиск путем вычисления значения индекса :

  • Если совпадение найдено (когда lys[index] ), то возвращается индекс
  • Если значение val меньше its[index] , то значение индекса пересчитывается по формуле для левого подмассива
  • Если значение val больше, чем its[index] , то значение индекса пересчитывается по формуле для правого подмассива

Давайте продолжим и реализуем интерполяционный поиск с помощью Python:

def InterpolationSearch(lys, val):
    low = 0
    high = (len(lys) - 1)
    while low <= high and val >= lys[low] and val <= lys[high]:
        index = low + int(((float(high - low) / ( lys[high] - lys[low])) * ( val - lys[low])))
        if lys[index] == val:
            return index
        if lys[index] < val:
            low = index + 1;
        else:
            high = index - 1;
    return -1

Если мы используем функцию для вычисления:

>>> print(InterpolationSearch([1,2,3,4,5,6,7,8], 6))

Наши начальные значения были бы:

  • вэл,
  • низкий,
  • высокий,
  • лис[низко],
  • лис[высокий],
  • индекс +

Поскольку lys[5] равно 6, что является искомым значением, мы прекращаем выполнение и возвращаем результат:

5

Если у нас есть большое количество элементов, и наш индекс не может быть вычислен за одну итерацию, мы продолжаем пересчитывать значения для index после корректировки значений high и low в нашей формуле.

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

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

Зачем Использовать Python Для Поиска?

Python очень удобочитаем и эффективен по сравнению со старыми языками программирования, такими как Java, Fortran, C, C++ и т. Д. Одним из ключевых преимуществ использования Python для реализации алгоритмов поиска является то, что вам не нужно беспокоиться о приведении или явном наборе текста.

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

Python также является хорошим местом для начала, если вы хотите сравнить производительность различных алгоритмов поиска для вашего набора данных; создание прототипа в Python проще и быстрее, потому что вы можете сделать больше с меньшим количеством строк кода.

Чтобы сравнить производительность наших реализованных алгоритмов поиска с набором данных, мы можем использовать библиотеку time в Python:

import time

start = time.time()
# call the function here
end = time.time()
print(start-end)

Вывод

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

Выбор того, какой алгоритм использовать, основан на данных, которые вы должны искать; ваш входной массив, который мы называли lys во всех наших реализациях.

  • Если вы хотите выполнить поиск по несортированному массиву или найти первое вхождение переменной поиска, лучшим вариантом является линейный поиск.
  • Если вы хотите выполнить поиск по отсортированному массиву, есть много вариантов, из которых самый простой и быстрый метод-двоичный поиск.
  • Если у вас есть сортированный массив, который вы хотите найти без использования оператора деления, вы можете использовать либо поиск перехода, либо поиск Фибоначчи.
  • Если вы знаете, что элемент, который вы ищете, скорее всего, будет ближе к началу массива, вы можете использовать экспоненциальный поиск.
  • Если ваш сортированный массив также равномерно распределен, то самым быстрым и эффективным алгоритмом поиска будет интерполяционный поиск.

Если вы не уверены, какой алгоритм использовать с отсортированным массивом, просто попробуйте каждый из них вместе с библиотекой времени Python и выберите тот, который лучше всего работает с вашим набором данных.

Читайте ещё по теме: