Поиск информации, хранящейся в различных структурах данных, является важной частью практически каждого приложения.
Существует множество различных алгоритмов, которые можно использовать для поиска. Каждый из них имеет разные реализации и напрямую зависит от структуры данных, для которой он реализован.
Умение выбрать нужный алгоритм для конкретной задачи является ключевым навыком для разработчиков. Именно правильно подобранный алгоритм отличает быстрое, надежное и стабильное приложение от приложения, которое падает от простого запроса.
В этой статье:
Алгоритмы развиваются и оптимизируются в результате постоянной эволюции и необходимости находить наиболее эффективные решения для основных проблем в различных областях.
Одной из наиболее распространенных проблем в области компьютерных наук является поиск в коллекции и определение того, присутствует ли данный объект в коллекции или нет.
Почти каждый язык программирования имеет свою собственную реализацию базового алгоритма поиска. Обычно — в виде функции, которая возвращает логическое значение True
или False
, когда элемент найден в данной коллекции элементов.
В Python самый простой способ поиска объекта — использовать операторы членства. Их название связано с тем, что они позволяют нам определить, является ли данный объект членом коллекции.
Эти операторы могут использоваться с любой итерируемой структурой данных в Python, включая строки, списки и кортежи.
in
— возвращает True
, если данный элемент присутствует в структуре данных.not in
— возвращает True
, если данный элемент не присутствует в структуре данных.>>> 'apple' in ['orange', 'apple', 'grape'] True >>> 't' in 'pythonist' True >>> 'q' in 'pythonist' False >>> 'q' not in 'pythonist' True
Операторов членства достаточно, если нам нужно только определить, существует ли подстрока в данной строке, или пересекаются ли две строки, два списка или кортежа с точки зрения содержащихся в них объектов.
В большинстве случаев помимо определения, наличествует ли элемент в последовательности, нам нужна еще и позиция (индекс) элемента. Используя операторы членства, мы не можем получить ее.
Существует множество алгоритмов поиска, которые не зависят от встроенных операторов и могут использоваться для более быстрого и/или эффективного поиска значений. Кроме того, они могут дать больше информации (например, о позиции элемента в коллекции), а не просто определить, есть ли в коллекции этот элемент.
Линейный поиск — это один из самых простых и понятных алгоритмов поиска. Мы можем думать о нем как о расширенной версии нашей собственной реализации оператора in
в Python.
Суть алгоритма заключается в том, чтобы перебрать массив и вернуть индекс первого вхождения элемента, когда он найден:
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 начинается с нуля.
Временная сложность линейного поиска равна O(n). Это означает, что время, необходимое для выполнения, увеличивается с увеличением количества элементов в нашем входном списке lys
.
Линейный поиск не часто используется на практике, потому что такая же эффективность может быть достигнута с помощью встроенных методов или существующих операторов. К тому же, он не такой быстрый и эффективный, как другие алгоритмы поиска.
Линейный поиск хорошо подходит для тех случаев, когда нам нужно найти первое вхождение элемента в несортированной коллекции. Это связано с тем, что он не требует сортировки коллекции перед поиском (в отличие от большинства других алгоритмов поиска).
Бинарный поиск работает по принципу «разделяй и властвуй». Он быстрее, чем линейный поиск, но требует, чтобы массив был отсортирован перед выполнением алгоритма.
Предполагая, что мы ищем значение val
в отсортированном массиве, алгоритм сравнивает val
со значением среднего элемента массива, который мы будем называть 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))
После выполнения этого фрагмента кода будет возвращен индекс среднего элемента:
2
Для сравнения: выполнение линейного поиска по тому же массиву вернет индекс первого элемента:
0
Однако мы не можем категорически утверждать, что двоичный поиск не работает, если массив содержит дубликаты. Он может работать так же, как линейный поиск, и в некоторых случаях возвращать первое вхождение элемента. Например:
>>> print(BinarySearch([1,2,3,4,4,4,5], 4)) 3
Бинарный поиск довольно часто используется на практике, потому что он эффективен и быстр по сравнению с линейным поиском. Однако у него есть некоторые недостатки, такие как зависимость от оператора //
. Существует много других алгоритмов поиска, работающих по принципу «разделяй и властвуй», которые являются производными от бинарного поиска. Некоторые из них мы рассмотрим далее.
Jump Search похож на бинарный поиск тем, что он также работает с отсортированным массивом и использует аналогичный подход «разделяй и властвуй» для поиска по нему.
Его можно классифицировать как усовершенствованный алгоритм линейного поиска, поскольку он зависит от линейного поиска для выполнения фактического сравнения при поиске значения.
В заданном отсортированном массиве мы ищем не постепенно по элементам массива, а скачкообразно. Если у нас есть размер прыжка, то наш алгоритм будет рассматривать элементы входного списка 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
.lys[0]
и lys[3]
. Поскольку 5 не находится между 1 и 4, мы идем дальше.lys[3]
и lys[6]
, где 6 — это 3 + jump. Поскольку 5 находится между 4 и 7, мы выполняем линейный поиск по элементам между lys[3]
и lys[6]
и возвращаем индекс нашего элемента:4
Временная сложность jump search равна O(√n), где √n — размер прыжка, а n — длина списка. Таким образом, с точки зрения эффективности jump search находится между алгоритмами линейного и бинарного поиска.
Единственное наиболее важное преимущество jump search по сравнению с бинарным поиском заключается в том, что он не опирается на оператор деления (/
).
В большинстве процессоров использование оператора деления является дорогостоящим по сравнению с другими основными арифметическими операциями (сложение, вычитание и умножение), поскольку реализация алгоритма деления является итеративной.
Стоимость сама по себе очень мала, но когда количество искомых элементов очень велико, а количество необходимых операций деления растет, стоимость может постепенно увеличиваться. Поэтому jump search лучше бинарного поиска, когда в системе имеется большое количество элементов: там даже небольшое увеличение скорости имеет значение.
Чтобы ускорить jump search, мы могли бы использовать бинарный поиск или какой-нибудь другой алгоритм для поиска в блоке вместо использования гораздо более медленного линейного поиска.
Поиск Фибоначчи — это еще один алгоритм «разделяй и властвуй», который имеет сходство как с бинарным поиском, так и с jump search. Он получил свое название потому, что использует числа Фибоначчи для вычисления размера блока или диапазона поиска на каждом шаге.
Числа Фибоначчи — это последовательность чисел 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 или первые три числа в последовательности Фибоначчи. Это поможет нам избежать IndexError
в случае, когда наш массив 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
index = -1
lys[4]
, где 4 — это минимум из двух значений — index + fibM_minus_2
(-1+5) и длина массива минус 1 (11-1). Поскольку значение lys[4]
равно 5, что меньше искомого значения, мы перемещаем числа Фибоначчи на один шаг вниз в последовательности, получая следующие значения:fibM = 8
fibM_minus_1 = 5
fibM_minus_2 = 3
index = 4
lys[7]
, где 7 — это минимум из двух значений: index + fibM_minus_2
(4 + 3) и длина массива минус 1 (11-1). Поскольку значение lys[7]
равно 8, что больше искомого значения, мы перемещаем числа Фибоначчи на два шага вниз в последовательности, получая следующие значения: fibM = 3
fibM_minus_1 = 2
fibM_minus_2 = 1
index = 4
lys[5]
, где 5 — это минимум из двух значений: index + fibM_minus_2
(4+1) и длина массива минус 1 (11-1) . Значение lys[5]
равно 6, и это наше искомое значение!Получаем ожидаемый результат:
5
Временная сложность поиска Фибоначчи равна O(log n). Она такая же, как и у бинарного поиска. Это означает, что алгоритм в большинстве случаев работает быстрее, чем линейный поиск и jump search.
Поиск Фибоначчи можно использовать, когда у нас очень большое количество искомых элементов и мы хотим уменьшить неэффективность, связанную с использованием алгоритма, основанного на операторе деления.
Дополнительным преимуществом использования поиска Фибоначчи является то, что он может вместить входные массивы, которые слишком велики для хранения в кэше процессора или ОЗУ, потому что он ищет элементы с увеличивающимся шагом, а не с фиксированным.
Экспоненциальный поиск — это еще один алгоритм поиска, который может быть достаточно легко реализован на Python, по сравнению с jump search и поиском Фибоначчи, которые немного сложны. Он также известен под названиями galloping search, doubling search и Struzik search.
Экспоненциальный поиск зависит от бинарного поиска для выполнения окончательного сравнения значений. Алгоритм работает следующим образом:
Реализация алгоритма экспоненциального поиска на 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( lys[:min(index, len(lys))], val)
Используем функцию, чтобы найти значение:
>>> print(ExponentialSearch([1,2,3,4,5,6,7,8],3))
Рассмотрим работу алгоритма пошагово.
lys[0]
равен 1, а мы ищем 3, мы устанавливаем индекс равным 1 и двигаемся дальше.lys[1]
равно 2, что меньше 3, поэтому значение index умножается на 2 и переменной index
присваивается значение 2.lys[2]
равно 3, что равно 3, поэтому значение index
умножается на 2 и переменной index
присваивается значение 4.lys[4]
равно 5, что больше 3. Условие выполнения цикла больше не соблюдается и цикл завершает свою работу.lys[: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[high]
), и более низкое, когда значение val ближе по значению к элементу в начале массива (lys[low]
).Алгоритм осуществляет поиск путем вычисления значения индекса:
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,
low = 0,
high = 7,
lys[low] = 1,
lys[high] = 8,
index = 0 + [(6-1)*(7-0)/(8-1)] = 5
Поскольку lys[5]
равно 6, что является искомым значением, мы прекращаем выполнение и возвращаем результат:
5
Если у нас большое количество элементов и наш индекс не может быть вычислен за одну итерацию, то мы продолжаем пересчитывать значение индекса после корректировки значений high и low.
Временная сложность интерполяционного поиска равна O(log log n), когда значения распределены равномерно. Если значения распределены неравномерно, временная сложность для наихудшего случая равна O(n) — так же, как и для линейного поиска.
Интерполяционный поиск лучше всего работает на равномерно распределенных, отсортированных массивах. В то время как бинарный поиск начинает поиск с середины и всегда делит массив на две части, интерполяционный поиск вычисляет вероятную позицию элемента и проверяет индекс, что повышает вероятность нахождения элемента за меньшее количество итераций.
Python очень удобочитаемый и эффективный по сравнению с такими языками программирования, как Java, Fortran, C, C++ и т. д. Одним из ключевых преимуществ использования Python для реализации алгоритмов поиска является то, что вам не нужно беспокоиться о приведении или явной типизации.
В Python большинство алгоритмов поиска, которые мы обсуждали, будут работать так же хорошо, если мы ищем строку. Имейте в виду, что понадобится внести изменения в код для алгоритмов, которые используют искомый элемент для числовых вычислений, например алгоритм интерполяционного поиска.
Python также подходит, если вы хотите сравнить производительность различных алгоритмов поиска для вашего dataset’а. Создание прототипа на Python проще и быстрее, потому что вы можете сделать больше с меньшим количеством строк кода.
Чтобы сравнить производительность наших реализованных алгоритмов, в Python мы можем использовать библиотеку time:
import time start = time.time() # вызовите здесь функцию end = time.time() print(start-end)
Существует множество возможных способов поиска элемента в коллекции. В этой статье мы обсудили несколько алгоритмов поиска и их реализации на Python.
Выбор используемого алгоритма зависит от данных, с которыми вы будете работать. Это ваш входной массив, который мы называли lys
во всех наших реализациях.
Если вы не уверены, какой алгоритм использовать для отсортированного массива, просто протестируйте каждый из них при помощи библиотеки time и выберите тот, который лучше всего работает с вашим dataset’ом.
Pydantic - это мощная библиотека проверки данных и управления настройками для Python, созданная для повышения…
Python предлагает набор библиотек, удовлетворяющих различные потребности в визуализации, будь то академические исследования, бизнес-аналитика или…
В Python для представления данных в двоичной форме можно использовать байты. Из этой статьи вы…
В этой статье рассказывается о том, что такое Werkzeug и как Flask использует его для…
При работе с датами часто возникает необходимость прибавлять к дате или вычитать из нее различные…
В этом руководстве мы рассмотрим, как добавить социальную аутентификацию с помощью GitHub и Google в…