Пользоваться такими удобными инструментами как ноутбук, планшет, телефон для получения самой разнообразной информации стало обычным делом. Обращаясь к этим гаджетам за нужной нам ссылкой, или почтовым адресом мы привычно получаем быстрый и точный ответ. Не задумываясь над тем, как наше устройство так быстро и всегда безошибочно находит нужные нам данные. В самом общем виде ответ достаточно простой – так работают алгоритмы поиска, закодированные в программных модулях поисковых систем наших умных электронных помощников. Делая ежедневно десятки, а то и сотни всевозможных запросов самых разнообразных данных, мы вправе предположить, что алгоритмов поиска должно быть тоже достаточно много. Чисто интуитивно мы понимаем, что для поиска таких различных объектов инфосферы как фотографии известных людей, номера телефонов городских больниц, названия статей по дайвингу, кулинарных рецептов со свежими овощами, каталогов автомобильных запчастей и многих, многих других должны использоваться различные алгоритмы поиска. Вполне логично предположить, что их должно быть несколько сотен, а может быть даже и тысяч. На самом деле это не так. С формальной точки зрения существует всего три базовых метода поиска – случайный, последовательный и двоичный. А в реальных поисковых системах в большинстве случаев работает только один – двоичный. Это действительно так, несмотря на то, что на сегодняшний день известно бесчисленное множество методов структурирования данных. Начиная от элементарных алгоритмов хеширования данных и заканчивая сложнейшими многоуровневыми рандомными деревьями. Структурирование данных – это процедура упорядочивания этих данных на носителе (например, на жёстком магнитном диске) неким специфическим образом. Простейший способ структурирования – это создание таблицы с записями фиксированной длины. Кроме этого могут быть использованы связанные списки, двоичные деревья, хеш-таблицы, индексные файлы и многие другие структуры данных. Суть всех этих методов сводится к одному – упорядоченному размещению данных для обеспечения быстрого доступа к ним. Так вот, быстрый поиск в любой такой структуре осуществляет адаптированный под эту структуру данных один из трёх алгоритмов поиска, анонсированных выше, либо их комбинация. Других методов поиска не существует. Давайте разбираться, в чём суть каждого из этих методов и чем они отличаются друг от друга.
Последовательный работает очень просто. Как и следует из его названия, он последовательно, начиная с первого, выбирает из произвольного массива данных элемент за элементом и сравнивает с искомым значением. Основным достоинством последовательного алгоритма поиска является его простота. Случайный алгоритм в отличие от последовательного перебирает все элементы массива в случайном порядке. Случайный и последовательный алгоритмы отличаются от двоичного тем, что могут работать с неупорядоченными данными. Например, у вас есть колода карт, которую вы тщательно перетасовали (разупорядочили) и после этого предложили трём алгоритмам найти короля трефа.
Случайный алгоритм будет наугад выбирать из колоды любую карту пока не найдёт нужную. Последовательный алгоритм начнёт перебирать все карты в колоде с первой до последней и также, рано или поздно, найдёт нужную вам карту. Двоичный алгоритм с таким простым заданием не справится. Он не сможет найти нужную карту, потому что для его работы требуется упорядоченный массив данных. Вот если вы предложите ему новую колоду карт, в которой все карты лежат по мастям и по старшинству, то в такой колоде он гарантировано найдет короля треф значительно быстрее, чем последовательный алгоритм и, скорее всего, обгонит случайный поиск. Время работы случайного алгоритма не прогнозируемо. Он может найти нужные данные с первой попытки и тогда он будет эффективнее двоичного, а может добраться до искомого значения в самом конце списка. В этом случае он будет такой же медленный, как и последовательный алгоритм поиска. Случайный поиск чаще всего применяют к очень большим неупорядоченным массивам данных, чтобы преодолеть так называемое «проклятие размерности». При этом руководствуются следующей логикой – медленнее, чем последовательный поиск всё равно не будет, но зато может быть и быстрее. Действительно, при поиске данных, размещённых во второй половине массива, случайный поиск, в среднем, всегда быстрее последовательного.
Лучшее определение двоичного алгоритма из тех, что мне попадались в печатной литературе, это описание того как поймать льва в пустыне. Берём пустыню и делим её пополам. Ту часть, в которой остался лев, делим опять пополам. И так до тех пор, пока не столкнёмся нос к носу с царём зверей.
Из этого описания становится понятно, как работает двоичный алгоритм и почему он так называется. Единственным недостатком двоичного алгоритма поиска является то, что для его работы весь массив данных должен быть отсортирован по возрастанию или убыванию, т.е. упорядочен. Потому что только упорядоченный массив, позволяет последовательно делить его пополам и, сравнивая текущее значение из середины массива с искомым значением, сужать границы поиска вниз или вверх по массиву в зависимости от результата очередного сравнения. Такой алгоритм иногда ещё называют логарифмическим, потому что он гарантировано завершает поиск любого значения в отсортированном массиве за Log2(N) итераций (где N количество записей в массиве). Справедливости ради следует упомянуть, что существует большой подкласс алгоритмов поиска основанных на идее базового двоичного алгоритма. Суть всех этих методов сводится к тому, что они делят исходный упорядоченный массив данных не пополам, а по какому-нибудь иному закону. Например, делят массив не на две равные части, а на n одинаковых частей или по экспоненциальному закону, и в этом случае такие алгоритмы поиска называют итерационными или экспоненциальными. Однако базовая идея у всех этих алгоритмов одна и та же – отсечь какую-то часть исходного массива и тем самым сузить область поиска. Такой приём сокращает время поиска, но при этом всегда требует предварительного упорядочивания данных.
Теперь, когда нам стала понятна суть базовых алгоритмов поиска, можно поговорить о методах упорядочивания или структурирования данных. И как структуры данных могут облегчать и ускорять поиск. Рассмотрим это на простом примере с уже знакомой нам колодой карт. Пусть это будет стандартная колода из 36 листов. Давайте, прежде чем начать что-либо искать в этой колоде, разделим её по мастям на 4 (четыре) равные части. Каждую часть разместим в виде отдельной стопки карт. Сверху каждой стопки положим самую старшую или самую младшую карту из этой стопки. Только что мы с вами структурировали данные для ускорения поиска. Профессиональные программисты называют это действие - сформировать разреженный индекс, а карта сверху стопки на их языке называется индексным ключом. Теперь, чтобы найти любую карту в колоде нам не нужно просматривать всю колоду. Достаточно, сравнивая искомую карту с верхней картой каждой стопки, найти стопку из 9 карт, в которой находится искомая карта и просмотреть только эту стопку. Очевидно, что поиск среди оставшихся 8 карт будет происходить быстрее, чем среди 36.
Такие манипуляции с данными могут существенно сократить время поиска, особенно если речь идет не о 36 картах, а о сотнях тысяч и миллионах записей в специализированной базе данных. Индексирование данных или создание индексных файлов – это один из самых простых и самых эффективных методов структурирования данных. В информатике и системах обработки данных есть и более сложные структуры. Например, несмотря на свою концептуальную простоту бинарные деревья, широко используемые в поисковых системах, по праву считаются одними из самых сложных в реализации структур данных. Чтобы разобраться с устройством двоичных деревьев воспользуемся ещё раз нашей колодой карт. Только теперь, разделим её на четыре равные части не только по мастям, но и по старшинству. При этом слева от десятки разместим все младшие карты (9, 8, 7, 6), а справа все старшие (В, Д, К, Т). В результате у нас получится своеобразный пасьянс из 8 стопок расположенных симметрично относительно десяток. Такая структура в информатике называется сбалансированным двоичным деревом. Корнем этого дерева является десятка черва, остальные десятки выступают в роли узлов двоичного дерева. Все остальные карты в зависимости от своего значения располагаются в левых и правых ветвях дерева.
Поиск в такой структуре данных всегда начинают с корня дерева. Далее находят узел, а потом определяют ветку, которой принадлежит искомое значение. Если мы захотим найти всё того же короля трефа, то мы должны будем спуститься по дереву от его корня до третьего узла и свернуть на его правую ветку. Здесь, применяя один из известных нам алгоритмов поиска, мы достаточно быстро найдём нужную карту. Почему спуститься – спросит дотошный читатель? Потому что двоичные деревья растут корнями вверх. Такова их особенность, с которой нужно просто смириться.
Завершая разговор об алгоритмах поиска можно отметить, что для формирования упорядоченных структур данных широко используются различные алгоритмы сортировки, которых в отличие от алгоритмов поиска придумано значительно больше. Но это уже тема отдельного разговора, который может состояться, если эта тема заинтересует вас.