Содержание статьи
В наши дни информация — самый ценный продукт, поэтому быстрый доступ к ней является залогом успеха. В этой статье мы обсудим основы успешного поиска информации — его алгоритмы.
Представим, что мы разрабатываем утилиту, которая мониторит куки браузера, сверяет их со списком в своем блэклисте и в случае совпадения удаляет их. Сверять мы будем по домену; если кук поставлен, например, сайтом bad-domain.com, и он есть в нашем списке плохих доменов, то мы беспощадно удаляем его из хранилища.
Более того, все это нужно делать на лету, прямо во время работы пользователя с браузером. То есть все это должно происходить быстро и безболезненно. Особенностью реализации нашей программы является то, что она не может определить, какой кукис уже проверен, а какой — нет. Утилита просто следит за хранилищем и в случае его обновления просто проверяет каждый домен на предмет вхождения его в блэклист.
Простое решение aka линейный поиск
Итак, мы садимся за написание программы и доходим до того места, где надо проверять вхождение кукиса в черный список. Не сильно напрягаясь, мы реализуем поиск домена в списке простым перебором, или, говоря языком профессионалов, линейным поиском.
Алгоритм линейного поиска заключается в следующем. Пусть мы имеем некоторое значение m и массив размерностью от 0 до n. Для того, чтобы проверить, имеется ли в массиве элемент со значением, равным m, мы просматриваем последовательно, начиная с нулевого индекса, каждую ячейку массива и сравниваем ее содержимое с m.
Перебор прекращается, если мы найдем нужный нам элемент или достигнем конца массива. В коде это будет смотреться примерно так:
Реализация алгоритма линейного поиска
int LinearSearch (int *array,
size_t arraySize, int key)
{
for (size_t i = 0; i < arraySize; i++)
if (array[i] == key)
return array[i];
// если ничего не нашли
return -1;
}
Понятно, что в худшем случае нам потребуется n сравнений, чтобы проверить наличие домена в блэклисте. Таким образом, асимптотическая сложность алгоритма — O(n). Проверим, насколько быстро в реальных условиях работает наш поиск.
Черный список включает в себя несколько тысяч сайтов. В браузере, на котором мы тестим мониторинг и удаление, у нас всего несколько кукисов. Мы побродили по паре сайтов и теперь запускаем программу, чтобы она проверяла плохие куки. Вроде бы все нормально: при заходе на очередной сайт программка сверяется со своим списком и в случае чего сигнализирует нам о заблокированном cookie.
Теперь мы решаем проверить чудо-утилиту в живой природе. Для этого запускаем рабочий браузер и начинаем бродить по Сети. Но происходит что-то странное — программа страшно тормозит.
Сообщения о заблокированных кукисах появляются спустя несколько минут. Внимательно присмотревшись, мы понимаем, что в нашей программе для серфинга Сети несколько тысяч этих самых куков. А так как мы каждый раз последовательно прогоняем доменное имя по всему блэклисту, то в итоге мы получаем несколько миллионов сравнений на каждый апдейт хранилища интернет-печенек: например, если в черном списке у нас 3000 записей, а в браузере 3000 куков, то мы получим 3000*3000=9 000 000 сравнений. Теперь совершенно ясно, почему мы имеем такие задержки в обработке, тем более что ищем и сравниваем мы не числовые значения, а строковые, что тоже довольно накладно по времени.
Бинарный поиск
Для ускорения работы программы нужно воспользоваться более быстрым алгоритмом. Им может быть алгоритм бинарного поиска. Его асимптотическая сложность равна O(log n). Применительно к нашей задаче в худшем случае мы получим около 10 431 сравнений (log(3000) * 3000 = 10431.4). Это примерно в 863 раза быстрее, чем предыдущий вариант. Неплохо, совсем неплохо! По сравнению с этим числом очередное ускорение на 20% каких-нибудь Opera или Google Chrome выглядит смешно. Но как же работает этот чудо-алгоритм?
Для начала следует отметить, что массив, по которому будет производиться поиск, должен быть отсортирован. В нашем случае элементы должны быть упорядочены лексикографически, то есть aaa < aab < baa < bba < bbb < bbc < caa... Сортировку можно проводить один раз при старте программы или сразу хранить блэклист в правильном виде.
Сам алгоритм бинарного поиска работает следующим образом. На первой итерации исходный массив разделяется на две равные части.
Значение, которое мы ищем, сравнивается с центральным элементом массива. То есть, если массив с количеством элементов равным n мы поделили на две части, то центральный элемент будет иметь индекс n/2. Если искомое значение больше значения в выбранной ячейке массива, то следующий шаг цикла будет работать со второй половиной массива, если меньше — с первой. Выбрав нужную часть массива, мы ее опять делим пополам и продолжаем сравнение. Для большей наглядности советую взглянуть на код:
Реализация алгоритма бинарного поиска
int CCookieRemover::lowerbound(const CStringArray& a,
const int& n, const CString& t)
{
int result;
int l;
int half;
int first;
int middle;
l = n;
first = 0;
while(l>0)
{
half = l/2;
middle = first+half;
if( a[middle]<t )
{
first = middle+1;
l = l-half-1;
}
else
{
l = half;
}
}
result = first;
return result;
}
С каждой итерацией мы все сильнее сокращаем область поиска. Цикл завершается, когда будет найден элемент с максимально близким значением к переменной, которую мы пытаемся найти в массиве. По завершению достаточно выполнить простое сравнение и проверить, нашелся ли нужный элемент или нет.
Как говорилось выше, скорость бинарного поиска примерно в 10 000 раз выше скорости линейного поиска. На практике, запустив нашу утилиту на рабочем браузере, мы практически не замечаем задержек. Сообщения о блокировке тех или иных куков появляются в считанные доли секунды, и ждать по несколько минут уже не приходится.
Другие алгоритмы поиска
Помимо линейного и бинарного поиска существует также троичный (тернарный) алгоритм поиска. Метод предназначен для поиска максимумов или минимумов функции, которая сначала строго возрастает, а затем строго убывает, либо наоборот. Алгоритм делит массив на три части и определяет отсутствие экстремума в первой или последней трети отрезка. После этого поиск повторяется на оставшихся двух частях. Помимо этого существует множество алгоритмов, которые оптимизированы для работы на специальных структурах данных.
Даже упомянутый выше бинарный поиск требует, чтобы исходный массив был отсортирован. Например, нашу задачу можно было бы решить с помощью двоичного дерева поиска. По сути, это обычное бинарное дерево, но с дополнительными свойствами. Оба поддерева, и левое, и правое, должны являться двоичными деревьями поиска. Кроме того, у всех узлов левого поддерева узла X значения ключей должны быть меньше значения ключа самого узла X, а у правого поддерева — больше или равны. Обычно каждый узел дерева состоит из записей вида {data, left, right}. data — данные сопоставленные с узлом, left и right — ссылки на левый и правый дочерние узлы. Очень часто для более высокой степени оптимизации в состав записи включают еще и ссылку на родительский узел. Данные data обязательно должны обладать ключом, на котором определены операции сравнения. Основным преимуществом двоичного дерева поиска является высокая эффективность операций поиска и сортировки. Например, чтобы найти узел с ключом K в дереве T надо выполнить следующие действия:
Алгоритм поиска в двоичном дереве
- Если дерево пусто, то считаем, что узел не найден, и останавливаемся;
- Если нет, то сравниваем K со значением ключа корневого узла X:
- Если K = X, возвращаем ссылку на этот узел и останавливаемся;
- Если K > X, рекурсивно ищем ключ K в правом поддереве Т;
- Если K < X, рекурсивно ищем ключ K в левом поддереве Т.
Помимо поиска можно также производить добавление элемента в
дерево и удаление его оттуда. Добавление в дерево не представляет
особой сложности, а вот удаление узла требует небольших умственных
усилий. Допустим, нам надо удалить узел с ключом K в дереве T с корнем n, тогда алгоритм будет примерно следующим:
Алгоритм удаления узла из двоичного дерева поиска
- Если дерево T пусто, останавливаемся;
- Если нет, то сравниваем K с ключом X корневого узла n;
- Если K > X, рекурсивно удаляем K из правого поддерева Т;
- Если K < X, рекурсивно удаляем K из левого поддерева Т;
- Если K = X, то надо рассматривать три случая:
- Если обоих потомков нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;
- Если одного из потомков нет, то значения полей второго потомка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;
- Если оба потомка присутствуют, то:
- Найдем узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n);
- Присвоим ссылке Left(m) значение Left(n);
- Ссылку на узел n в узле Parent(n) заменяем на Right(n);
- Освободим память, занимаемую узлом n.
Как видно, даже относительно сложная операция удаления узла выглядит не так страшно, если понимать структуру двоичного дерева поиска. Главное — правильно построить это дерево. Оно должно быть сбалансировано, то есть желательно, чтобы все пути в дереве от корня до листьев имели примерно одинаковую длину, иначе мы можем сильно потерять в производительности. Крайним случаем является ситуация, когда все узлы имеют лишь одно поддерево, левое или правое. В этом случае поиск в таком дереве будет по скорости равен поиску в списке.
Заключение
К сожалению, в одной статье невозможно рассказать достаточно подробно обо всех алгоритмах поиска и структурах данных. Для этого надо писать книгу, и не одну. Впрочем, такие книги уже есть, и правильный выбор подхода к хранению и обработке данных позволит добиться максимальной эффективности при работе с терабайтными массивами информации.
Что почитать?
Для тех, кого заинтересовала тема алгоритмов хранения и обработки данных, советую почитать книги Дональда Кнута.
Пожалуй, самым известным его трудом является серия «Искусство программирования», которая посвящена алгоритмам и структурам данных и содержит несколько томов. Эти книги считаются классикой и должны быть на полке у каждого уважающего себя кодера.
Хорошим источником знаний в области поиска и сортировки послужит книга «Фундаментальные алгоритмы на C» Роберта Седжвика. В ней рассматриваются такие вопросы, как анализ алгоритмов, структуры данных, сортировка и поиск, а также алгоритмы на графах.
