Вступление
Поиск данных, хранящихся в разных структурах данных, является важной частью практически каждого отдельного приложения.
Существует множество различных алгоритмов, доступных для использования при поиске, и каждый из них имеет разные реализации и полагается на разные структуры данных для выполнения своей работы.
Возможность выбрать конкретный алгоритм для данной задачи является ключевым навыком для разработчиков и может означать разницу между быстрым, надежным и стабильным приложением и приложением, которое рушится от простого запроса.
- Операторы членства
- Линейный поиск
- Бинарный поиск
- Перейти к поиску
- Поиск Фибоначчи
- Экспоненциальный поиск
- Интерполяционный поиск
Операторы членства
Алгоритмы развиваются и оптимизируются с течением времени в результате постоянного развития и необходимости находить наиболее эффективные решения основных проблем в различных областях.
Одна из наиболее распространенных проблем в области компьютерных наук - это поиск в коллекции и определение того, присутствует ли данный объект в коллекции или нет.
Почти каждый язык программирования имеет свою собственную реализацию
базового алгоритма поиска, обычно в виде функции, которая возвращает
Boolean
значение True
или False
когда элемент обнаружен в заданном
наборе элементов.
В Python самый простой способ поиска объекта - использовать операторы членства, названные так, потому что они позволяют нам определить, является ли данный объект членом коллекции.
Эти операторы можно использовать с любой итерируемой структурой данных в 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
Операторов членства достаточно, когда все, что нам нужно сделать, это выяснить, существует ли подстрока в данной строке, или определить, пересекаются ли две строки, списки или кортежи с точки зрения содержащихся в них объектов.
В большинстве случаев нам нужна позиция элемента в последовательности, помимо определения того, существует он или нет; Операторы членства не соответствуют этому требованию.
Существует множество алгоритмов поиска, которые не зависят от встроенных операторов и могут использоваться для более быстрого и / или эффективного поиска значений. Кроме того, они могут предоставить больше информации, например положение элемента в коллекции, а не просто определить его существование.
Линейный поиск
Линейный поиск - один из простейших и самых простых для понимания
алгоритмов поиска. Мы можем думать об этом как о расширенной версии
нашей собственной реализации оператора 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
val
большей вероятностью будет лежать в основе, в зависимости от того, больше или меньше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<lys[mid]:
last = mid -1
else:
first = mid +1
return index
Если мы используем функцию для вычисления:
>>> BinarySearch([10,20,30,40,50], 20)
Получаем результат:
1
Это индекс значения, которое мы ищем.
Действие, которое алгоритм выполняет следующим на каждой итерации, является одной из нескольких возможных:
- Возврат индекса текущего элемента
- Поиск в левой половине массива
- Поиск по правой половине массива
Мы можем выбрать только одну возможность на итерацию, и наш пул возможных совпадений делится на два на каждой итерации. Это делает временную сложность двоичного поиска равной O (log n) .
Одним из недостатков бинарного поиска является то, что если в массиве несколько вхождений элемента, он возвращает не индекс первого элемента, а скорее индекс элемента, ближайшего к середине:
>>> print(BinarySearch([4,4,4,4,4], 4))
Запуск этого фрагмента кода приведет к получению индекса среднего элемента:
1
Для сравнения выполнение линейного поиска в том же массиве вернет:
0
Это индекс первого элемента. Однако мы не можем категорически сказать, что двоичный поиск не работает, если массив содержит один и тот же элемент дважды - он может работать так же, как линейный поиск и в некоторых случаях возвращать первое вхождение элемента.
Если мы выполним двоичный поиск, например, в массиве [1,2,3,4,4,5]
и
найдем 4, в результате мы получим 3
.
Двоичный поиск довольно часто используется на практике, поскольку он
эффективен и быстр по сравнению с линейным поиском. Однако у него есть
некоторые недостатки, такие как использование оператора //
Есть много
других алгоритмов поиска «разделяй и властвуй» , которые являются
производными от бинарного поиска, давайте рассмотрим некоторые из них
далее.
Перейти к поиску
Поиск с переходом похож на двоичный поиск в том, что он работает с отсортированным массивом и использует аналогичный подход «разделяй и властвуй» для поиска по нему.
Его можно классифицировать как улучшение алгоритма линейного поиска, поскольку он зависит от линейного поиска для выполнения фактического сравнения при поиске значения.
Для отсортированного массива вместо постепенного поиска по элементам
массива мы ищем скачкообразно . Итак, в нашем входном списке lys
,
если у нас есть размер прыжка для прыжка, наш алгоритм будет
рассматривать элементы в порядке lys[0]
, lys[0+jump]
,
lys[0+2jump]
, lys[0+3jump]
и т. Д. на.
При каждом переходе мы сохраняем предыдущее значение и его индекс. Когда
мы находим набор значений, где lys[i]
<element < 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 элементов, размер прыжка будет √9 = 3. - Затем мы вычисляем значение
right
, которое является минимумом длины массива минус 1, или значениеleft+jump
, которое в нашем случае будет 0 + 3 = 3. Поскольку 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 ... где каждый элемент представляет собой сложение двух чисел, непосредственно предшествующих ему.
Алгоритм работает одновременно с тремя числами Фибоначчи. Назовем три
числа fibM
, fibM_minus_1
и fibM_minus_2
где fibM_minus_1
и
fibM_minus_2
- два числа непосредственно перед fibM
в
последовательности:
fibM = fibM_minus_1 + fibM_minus_2
Мы инициализируем значения 0,1 и 1 или первые три числа в
последовательности Фибоначчи, чтобы избежать ошибки
индекса в
случае, когда наш поисковый массив lys
содержит очень небольшое
количество элементов.
Затем мы выбираем наименьший номер последовательности Фибоначчи, который
больше или равен количеству элементов в нашем поисковом массиве lys
,
в качестве значения fibM
, а два числа Фибоначчи непосредственно перед
ним в качестве значений fibM_minus_1
и fibM_minus_2
. Пока в массиве
остались элементы и значение fibM
больше единицы, мы:
- Сравните
val
со значением блока в диапазоне доfibM_minus_2
и верните индекс элемента, если он совпадает. - Если значение больше, чем элемент, который мы сейчас рассматриваем,
мы перемещаем значения
fibM
,fibM_minus_1
иfibM_minus_2
два шага вниз в последовательности Фибоначчи и сбрасываем индекс на индекс элемента. - Если значение меньше, чем элемент, который мы сейчас рассматриваем,
мы перемещаем значения
fibM
,fibM_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
Если мы используем функцию FibonacciSearch для вычисления:
>>> print(FibonacciSearch([1,2,3,4,5,6,7,8,9,10,11], 6))
Давайте посмотрим на пошаговый процесс этого поиска:
- Определение наименьшего числа Фибоначчи, большего или равного длине
списка как
fibM
; в этом случае наименьшее число Фибоначчи, отвечающее нашим требованиям, равно 13. - Значения будут присвоены как:
- fibM = 13
- fibM_minus_1 = 8
- fibM_minus_2 = 5
- индекс = -1
- Затем мы проверяем элемент
lys[4]
где 4 - минимум -1 + 5. Поскольку значениеlys[4]
равно 5, что меньше искомого значения, мы перемещаем числа Фибоначчи на один шаг вниз в последовательности, делая значения:- fibM = 8
- fibM_minus_1 = 5
- fibM_minus_2 = 3
- index = 4
- Затем мы проверяем элемент
lys[7]
где 7 - минимум 4 + 3. Поскольку значениеlys[7]
равно 8, что больше искомого значения, мы перемещаем числа Фибоначчи на два шага вниз в последовательности.- fibM = 3
- fibM_minus_1 = 2
- fibM_minus_2 = 1
- index = 4
- Теперь проверим элемент
lys[5]
где 5 - минимум 4 + 1. Значениеlys[5]
равно 6, это значение, которое мы ищем!
Результат, как и ожидалось:
5
Временная сложность поиска Фибоначчи составляет O (log n) ; то же, что и бинарный поиск. Это означает, что в большинстве случаев алгоритм работает быстрее, чем линейный поиск и поиск с переходом.
Поиск Фибоначчи можно использовать, когда у нас есть очень большое количество элементов для поиска, и мы хотим уменьшить неэффективность, связанную с использованием алгоритма, который полагается на оператор деления.
Дополнительным преимуществом использования поиска по Фибоначчи является то, что он может вместить входные массивы, которые слишком велики для хранения в кэше ЦП или ОЗУ, потому что он выполняет поиск по элементам с увеличивающимся размером шага, а не с фиксированным размером.
Экспоненциальный поиск
Экспоненциальный поиск - это еще один алгоритм поиска, который можно довольно просто реализовать в Python по сравнению с поиском с переходом и поиском Фибоначчи, которые немного сложны. Он также известен под названиями скачущего поиска, удваивая поиск и поиск Struzik.
Экспоненциальный поиск зависит от двоичного поиска для выполнения окончательного сравнения значений. Алгоритм работает:
- Определение диапазона, в котором может находиться искомый элемент.
- Использование двоичного поиска диапазона для нахождения точного индекса элемента
Реализация алгоритма экспоненциального поиска в 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
кратно двум:- index = 1,
lys[1]
равно 2, что меньше 3, поэтому индекс умножается на 2 и устанавливается равным 2. - index = 2,
lys[2]
равно 3, что равно 3, поэтому индекс умножается на 2 и устанавливается на 4. - index = 4,
lys[4]
равно 5, что больше 3; на этом этапе петля разорвана.
- index = 1,
- Затем он выполняет двоичный поиск,
разрезая
список;
arr[:4]
. В Python это означает, что подсписок будет содержать все элементы до 4-го элемента, поэтому мы фактически вызываем:
|
|
>>> BinarySearch([1,2,3,4], 3)
который вернется:
2
Это индекс элемента, который мы ищем как в исходном списке, так и в нарезанном списке, который мы передаем алгоритму двоичного поиска.
Экспоненциальный поиск выполняется за время O (log i) , где i - это индекс искомого элемента. В худшем случае временная сложность равна O (log n) , когда последний элемент - это элемент, который мы ищем ( n
- длина массива).
Экспоненциальный поиск работает лучше, чем двоичный поиск, когда искомый элемент находится ближе к началу массива. На практике мы используем экспоненциальный поиск, потому что это один из самых эффективных алгоритмов поиска для неограниченных или бесконечных массивов .
Интерполяционный поиск
Поиск с интерполяцией - это еще один алгоритм «разделяй и властвуй», похожий на бинарный поиск. В отличие от двоичного поиска, поиск не всегда начинается с середины. Поиск с интерполяцией вычисляет вероятное положение искомого элемента по формуле:
index = low + [(val-lys[low])*(high-low) / (lys[high]-lys[low])]
Где переменные:
- lys - наш входной массив
- val - элемент, который мы ищем
- index - вероятный индекс элемента поиска. Вычисляется, что это
большее значение, когда значение val ближе к элементу в конце
массива (
lys[high]
), и меньше, когда значение val ближе к элементу в начале массива (lys[low]
) - low - начальный индекс массива
- high - последний индекс массива
Алгоритм выполняет поиск, вычисляя значение index
:
- Если совпадение найдено (когда
lys[index] == val
), возвращается индекс - Если значение
val
меньшеlys[index]
, значение индекса пересчитывается с использованием формулы для левого подмассива. - Если значение
val
большеlys[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))
Наши начальные значения будут такими:
- val = 6,
- низкий = 0,
- высокий = 7,
- lys [low] = 1,
- lys [high] = 8,
- индекс = 0 + [(6-1) * (7-0) / (8-1)] = 5
Поскольку lys[5]
равно 6, то есть искомому значению, мы прекращаем
выполнение и возвращаем результат:
5
Если у нас есть большое количество элементов, и наш индекс не может быть вычислен за одну итерацию, мы продолжаем пересчитывать значения индекса после корректировки значений high и low в нашей формуле.
Временная сложность поиска с интерполяцией составляет O (log log n), когда значения распределены равномерно. Если значения не распределены равномерно, сложность по времени в наихудшем случае равна O (n) , как при линейном поиске.
Поиск с интерполяцией лучше всего работает в равномерно распределенных отсортированных массивах. В то время как двоичный поиск начинается в середине и всегда делится на две части, поиск с интерполяцией вычисляет вероятное положение элемента и проверяет индекс, что повышает вероятность нахождения элемента за меньшее количество итераций.
Зачем использовать Python для поиска?
Python хорошо читается и эффективен по сравнению со старыми языками программирования, такими как Java, Fortran, C, C ++ и т. Д. Одним из ключевых преимуществ использования Python для реализации алгоритмов поиска является то, что вам не нужно беспокоиться о приведении типов или явном типировании.
В Python большинство алгоритмов поиска, которые мы обсуждали, будут работать так же хорошо, если мы ищем строку. Имейте в виду, что нам нужно внести изменения в код для алгоритмов, которые используют элемент поиска для числовых вычислений, например, алгоритм поиска с интерполяцией.
Python - также хорошее место для начала, если вы хотите сравнить производительность различных алгоритмов поиска для вашего набора данных; создание прототипа на Python проще и быстрее, потому что вы можете делать больше с меньшим количеством строк кода.
Чтобы сравнить производительность реализованных нами алгоритмов поиска с набором данных, мы можем использовать библиотеку времени в Python:
import time
start = time.time()
# call the function here
end = time.time()
print(start-end)
Заключение
Есть много возможных способов поиска элемента в коллекции. В этой статье мы попытались обсудить несколько алгоритмов поиска и их реализации на Python.
Выбор алгоритма для использования основан на данных, которые вам нужно
найти; ваш входной массив, который мы называем lys
во всех наших
реализациях.
- Если вы хотите выполнить поиск в несортированном массиве или найти первое вхождение переменной поиска, лучшим вариантом является линейный поиск.
- Если вы хотите выполнить поиск в отсортированном массиве, существует множество вариантов, из которых самым простым и быстрым методом является двоичный поиск.
- Если у вас есть отсортированный массив, в котором вы хотите выполнить поиск без использования оператора деления, вы можете использовать поиск с переходом или поиск по Фибоначчи.
- Если вы знаете, что элемент, который вы ищете, скорее всего, находится ближе к началу массива, вы можете использовать экспоненциальный поиск.
- Если ваш отсортированный массив также равномерно распределен, самым быстрым и эффективным алгоритмом поиска будет поиск с интерполяцией.
Если вы не уверены, какой алгоритм использовать с отсортированным массивом, просто попробуйте каждый из них вместе с библиотекой времени Python и выберите тот, который лучше всего работает с вашим набором данных.