Файл: Применение алгоритмов поиска в массивах.pdf

Альтернативной стратегией является использование дерева поиска для хранения динамических множеств данных. Деревья поиска хорошо работают как с первичной, так и со вторичной памятью и позволяют возвращать упорядоченные диапазоны элементов, на что не способны хеш-таблицы. Наиболее распространенным типом дерева поиска является бинарное дерево поиска (binary search tree — BST), которое состоит из узлов, как показано на рис. 3. Каждый узел содержит одно значение из множества и хранит ссылки на два (потенциальных) дочерних узла — левый (left) и правый (right).

рис. 3. Простое бинарное дерево поиска

Дерево поиска используется тогда, когда:

• требуется обход данных в возрастающем (или убывающем) порядке;

• размер множества данных неизвестен, а реализация должна быть в состоянии обработать любой возможный размер, помещающийся в памяти;

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

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

Когда значения в коллекциях являются примитивными типами (например, строками или целыми числами), ключами могут быть сами значения. В противном случае они являются ссылками на структуры, которые содержат значения [4].

Бинарное дерево поиска представляет собой непустой набор узлов, содержащих упорядоченные значения, именуемые ключами. Верхний корневой узел является предком для всех остальных узлов в BST. Каждый узел потенциально может указывать на два узла, каждый из которых является корнем BST — left и right соответственно. BST гарантирует выполнение свойства бинарного дерева поиска, а именно — того, что если k является ключом для узла, то все ключи в поддереве left не превышают значения k, а все ключи в поддереве right не меньше k. На рис. 3 показан небольшой пример BST, в котором каждый узел содержит целочисленное значение. Корень содержит значение 7; в дереве есть четыре листа со значениями 1,6, 10 и 17. Внутренний узел, например, 5, имеет родительский узел и некоторые дочерние узлы. Как видно из рисунка, поиск ключа в этом дереве требует изучения не более четырех узлов, начиная с корня.

BST может не быть сбалансированным; при добавлении элементов одни ветви могут оказаться относительно короткими, в то время как другие — более длинными. Это приводит к субоптимальному поиску по более длинным ветвям. В худшем случае структура BST может выродиться и превратиться в список. На рис. 4 показано вырожденное дерево с теми же значениями, что и дерево на рис. 3. Хотя структура такого дерева и соответствует строгому определению BST, фактически она представляет собой связанный список, так как правое поддерево каждого узла является пустым.

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

рис. 4. Вырожденное бинарное дерево поиска

2. РЕАЛИЗАЦИЯ И АНАЛИЗ АЛГОРИТМОВ

2.1 Последовательный поиск. Реализация. Анализ

Обычно реализация последовательного поиска тривиальна. В примере ниже

показана реализация на примере последовательного поиска из 20 значений:

cout << endl << endl << "Введите ключ : "; cin >> key; // считываем ключ

   for (int i = 0; i < 20; i++) {

    if (arr[i] == key) { // проверяем равен ли arr[i] ключу

      ans[h++] = i;

    }

  }

   if (h != 0) { // проверяем были ли совпадения

    for (int i = 0; i < h; i++) {

      cout << "Ключ " << key << " находится в ячейке " << ans[i] << endl; //выводим все индексы

    }

Полный листинг в приложении А.

Если запрашиваемый элемент принадлежит коллекции и равновероятно может быть найден в любом из индексируемых местоположений (или, в качестве альтернативы, если он с одинаковой вероятностью может быть возвращен итератором в любой позиции), то в среднем последовательный поиск проверяет n/2 + 1/2. Таким образом, для каждого искомого элемента, имеющегося в коллекции, будет проверяться около всех половины элементов, так что производительность поиска оказывается равной О(n). В наилучшем случае, когда запрашиваемый элемент является первым элементом коллекции, производительность оказывается равной O(1). В среднем и наихудшем случаях алгоритм последовательного поиска обладает производительностью 0(n). Если размер коллекции вырастает в два раза, то и время, затрачиваемое на поиск в ней, примерно удваивается.

2.2 Бинарный поиск. Реализация. Анализ

Реализация бинарного поиска на примере поиска из 10 значений в отсортированном массиве:  

cout << endl << "Введите ключ: ";

   cin >> key; // считываем ключ

   bool flag = false;

  int l = 0; // левая граница

  int r = 9; // правая граница

  int mid;

   while ((l <= r) && (flag != true)) {

    mid = (l + r) / 2; // считываем срединный индекс отрезка [l,r]

     if (arr[mid] == key) flag = true; //проверяем ключ со серединным элементом

    if (arr[mid] > key) r = mid - 1; // проверяем, какую часть нужно отбросить

    else l = mid + 1;

  }

Полный листинг в приложении Б.

Производительность этого кода зависит от количества итераций цикла while. Для достижения большей производительности бинарный поиск может быть немного усложнен. Сложность увеличивается, если коллекция хранится не в виде структуры данных в памяти, такой как массив. Большая коллекция может потребовать размещения во вторичной памяти, такого, как в файле на диске. В таком случае доступ к i-му элементу осуществляется по смещению его местоположения в файле. При использовании вторичной памяти во времени, необходимом для поиска элемента, преобладают затраты на доступ к памяти; таким образом, может быть целесообразным использование других решений, связанных с бинарным поиском [3].

Двоичный поиск на каждой итерации уменьшает размер задачи примерно в два раза. Максимальное количество делений пополам для коллекции размером n равно |log n|+l. Если одной операции достаточно, чтобы определить, равны ли два элемента, меньше или больше один другого, то достаточно выполнить только |log n|+1 сравнений. Таким образом, алгоритм можно классифицировать как имеющий производительность O(log n).

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

Значение –(р+1) представляет собой индекс позиции, в которую следует вставить искомый элемент. Естественно, что при вставке следует перенести все значения с большими индексами, чтобы освободить место для нового элемента.

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

Из 100 испытаний по 524288 поисков элемента, хранящегося в коллекции размера n размещенной в памяти (размер коллекции колеблется в диапазоне от 4096 до 524288 элементов) с вероятностью наличия искомого элемента, равной р (и принимающей значения 1,0, 0,5 и 0,0) получаем результаты в табл. 1.

Табл.1 Сравнение времени выполнения бинарных поисков в памяти с последовательным поиском таб. 1

В табл. 2 показано время выполнения 524288 поисков в коллекции, хранящейся на локальном диске. Выполнялись два варианта поиска — имеющегося в коллекции элемента (р = 1,0) и элемента, которого там нет (поиск значения -1 в коллекции [0, n)). Данные представляли собой просто файл возрастающих целых чисел, в котором каждое целое число упаковано в четыре байта. Доминирование времени обращения к диску очевидно, так как результаты в табл. 2 почти в 400 раз медленнее, чем в табл. 1. Так, как время поиска увеличивается на фиксированную величину при удвоении размера, это является четким подтверждением того факта, что производительность бинарного поиска — O(log n).

Табл. 2. Бинарный поиск во вторичной памяти

2.3 Поиск на основе Хеша. Реализация. Анализ

Поиск на основе Хеша можно рассмотреть на примере полиноминального хеширования, при котором хеш-функция вычисляется как перевод из n-ичной системы в десятичную. В этом случае хеширование строк позволяет эффективно отвечать на вопрос о равенстве строк, сравнивая их хеш-коды. Хеш-код – целое число, вычисляемое по символам строки. Если две строки равны, то их хеш-коды тоже равны. Например, если есть строка s, основание BASE и кольцо вычетов по модулю MOD, то хеш-код строки будет вычисляться следующим образом: (s[0] * BASE0 + s[1] * BASE1 + ... + s[n – 1] * BASE(n-1)) % MOD. Или же наоборот: (s[0] * BASE(n-1) + s[1] * BASE(n-2) + .. + s[n – 1] * BASE0) % MOD.

Выбор направления расстановки степеней не принципиален. Главное – использовать такое простое основание BASE, чтобы оно было взаимно простым с MOD, и его значение было больше количества символов в алфавите. MOD также должен быть простым, как правило, он равен 109 + 7 или 109 + 9.

Для получения индекса символа s[i] в алфавите выполняется следующее решение: (int)s[i] – 'a' + 1. Но чтобы не загрязнять код, поступают проще, например, используют приведение к signed char, который вернёт значение от 0 до 255. При этом необходимо понимать, что основание должно быть больше максимального значения возвращаемого кода, поэтому берется BASE = 2011 или 2017.

Чтобы иметь возможность получать хеш любой подстроки s[l..r] строки s за O(1), используется хеш-функциея на префиксах. Пример: пусть максимальная длина строки – 106. Заведём массив hash[SIZE], хранящий 64-битовые числа. Далее заполняем массив простейшей динамикой по вышеописанным формулам. Приложение В.

Также понадобится массив степеней выбранного BASE. Заводится powers[SIZE], хранящий 64-битовые числа и заполняется по динамике: powers[i] = powers[i – 1] * BASE % MOD. Приложение В.

Для хеша подстроки, принцип получения такой же, как и при запросе суммы на диапазоне. От хеша с индексом r отнимается хеш с индексом l, умноженный на BASE в степени разности r и l. Приложение В.

Работа алгоритма хеширования рассмотрена на примере программы, сравнивающей две строки. Приложение В.

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

Избавиться от коллизий при длине строк ~106 невозможно, потому что количество различных строк больше количества различных хеш-кодов. Вероятность коллизии можно свести к минимуму (почти к нулю), если написать ещё один хеш, т. е. написать первый хеш с основанием 2011 по модулю 109 + 7, а второй хеш – с основанием 2017 по модулю 109 + 9 и использовать оба хеша в сравнениях. [3]