Главная » Java, Структуры данных и алгоритмы » Поисковые таблицы

0

Если имеется упорядоченный словарь D, то можно хранить его объекты в векторе S в неубывающем порядке значений ключей (см. рис. 8.7). Особо отметим, что S — вектор, а не обычная последовательность, так как упорядочение ключей в векторе S позволяет осуществлять поиск быстрее, чем применением связного списка. В дальнейшем будем ссылаться на такую векторную реализацию упорядоченного словаря D как на поисковую таблицу (look-up table).

Рис. 8.7. Реализация словаря D посредством поисковой таблицы. Показаны только ключи словаря, чтобы подчеркнуть упорядоченный характер реализации

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

13 Зак. 2456

insertItem(A;,e) в поисковой таблице занимает в худшем случае О(п) времени, так как требуется сдвинуть все объекты в векторе с ключом, большим к, чтобы освободить место для нового объекта (к,е). Так же обстоит дело и с операциями removeElement(A:) и removeAllElements(A;), так как они в худшем случае тоже требуют О(п) времени для смещения всех объектов в векторе с ключом, большим к, для закрытия «дыры», образовавшейся в результате удаления объекта (или объектов). Поисковая реализация, таким образом, уступает регистрационному файлу в смысле продолжительности операций обновления. Но, несмотря на это, операции findElement и findAllElements выполняются гораздо быстрее именно с помощью поисковой таблицы.

Бинарный поиск

Значительным преимуществом использования вектора S как массива для реализации упорядоченного словаря D с количеством объектов п является то, что доступ к элементу в S по его рангу составляет 0(1) времени. Как отмечалось в разделе 5.1, рангом элемента вектора является количество предшествующих ему элементов. Таким образом, первый элемент в S имеет нулевой ранг, а последний — ранг п – 1. Элементами S являются объекты словаря Д а так как S упорядочен, объект ранга / имеет ключ больший, чем ключи объектов ранга 0, …,/- 1, и меньший, чем ключи объектов ранга / + 1, …, п – 1. Такое наблюдение позволяет быстро «вычислять» искомый ключ к с помощью некоего подобия детской игры «большой-маленький». Объект /в Остановится кандидатом, если на данной стадии поиска нельзя точно установить, что / имеет ключ, равный к. Алгоритм хранит два параметра — «высший» и «низший», так что все объекты-кандидаты расположены между нижним и верхним рангами вектора S. Изначально low = 0, high = п – 1, а кеу(/) обозначает ключ ранга /, имеющий в качестве элемента elem(/). Затем к сравнивается с ключом медианного кандидата, то есть объекта ранга

Изначально количество объектов-кандидатов равно п. После первого вызова BinarySearch оно равняется максимум я/2. После второго вызова — уже п/4 и так далее. В принципе после /-вызова BinarySearch количество объектов-кандидатов для поиска составит максимум я/2′. В крайнем случае (при безрезультативном поиске) рекурсивные вызовы прекратятся, как только закончатся объекты-кандидаты для поиска. Следовательно, максимальное число рекурсивно выполняемых вызовов составит

где т — минимальное целое число, для которого данное неравенство верно.

Другими словами (основание логарифма, равное 2, не записывается), т > log п. Таким образом, получаем

отсюда предполагается, что BinarySearch^/^O,^ – 1), а значит, и метод findEl6ment(A:) выполняются за 0(log п) времени.

Несколько видоизмененный бинарный поиск выполняет fmdAllElements(/:) за 0(log п + s) времени, где s — количество элементов в возвращаемом итераторе. Подробности читатель имеет возможность рассмотреть, выполнив упражнение 3-8.3.

Таодм обр^зрм, для выполнения быстрого поиска по словарю можно воспользоваться поисковой таблицей, но применение ее при большом

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

В табл. 8.3 приведены сравнительные характеристики времени выполнения методов словаря, реализованного с помощью регистрационного файла и поисковой таблицы. Регистрационный файл позволяет быстро вводить элементы, но медленно выполняет поиск и удаление. В то же время поисковая таблица быстро находит, но медленно вводит и удаляет. К сожалению, хотя это специально й не отмечалось, организованная последовательность, реализованная двусвязным списком, будет медленно выполнять практически все словарные операции (это будет видно, если выполнить упражнение М-8.1).

Метод

Регистрационный файл

Поисковая таблица

size, isEmpty

0(1)

0(1)

keys, elements

m

0(n)

findElement

0(n)

0(log n)

findAIIEIements

0(и)

0(log n + s)

insertltem

0(1)

0(n)

removeElement

0{n)

0{n)

removeAllElements

Q(n)

0(n)

Таблица 8.3. Сравнительные данные выполнения методов словаря, реализованного с помощью регистрационного файла и поисковой таблицы, которые можно рассматривать так же, как реализации с помощью несортированной и сортированной последовательностей соответственно. Количество объектов в момент выполнения метода равно и, а размер возвращаемого операциями findAllElements и removeAllElements итератора равен s

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии