Лемма 12.4 Для вставки, обнаружения попаданий и промахов при последовательном поиске в таблице символов, содержащей N упорядоченных элементов, требуется выполнение приблизительно N/2 операций сравнения (в среднем).

См. лемму 2.2. И вновь эти утверждения справедливы для представлений с использованием как массивов, так и связных списков, в чем несложно убедиться, ознакомившись с реализациями (см. программу 12.5 и упражнение 12.21).

Построение упорядоченных таблиц путем последовательной вставки, по сушеству, эквивалентно выполнению алгоритма сортировки вставками, который был описан в разделе 6.2. Обшее время, необходимое для построения таблицы, связано квадратичной зависимостью с количеством элементов, поэтому вряд ли стоит использовать этот метод для построения больших таблиц. Однако при выполнении огромного количества операций search в небольшой таблице поддержка упорядоченности элементов вполне оправдана, поскольку в соответствии с леммами 12.3 и 12.4 этот подход может в два раза уменьшить время, затрачиваемое на обнаружение промахов при поиске. Если элементы с дублированными ключами не должны храниться в таблице, дополнительные затраты на поддержку упорядоченности таблицы не столь велики, как может казаться, поскольку вставка выполняется только после обнаружения промаха при поиске и, следовательно, время, затрачиваемое на вставку, пропорционально времени, затрачиваемому на поиск. С другой стороны, если элементы с дублированными ключами могут храниться в таблице, при использовании неупорядоченной таблицы время выполнения операции insert может оставаться постоянным. Использование неупорядоченной таблицы предпочтительнее для приложений, в которых выполняется огромное количество операций insert при сравнительно небольшом числе операций search.

Помимо учета этих различий, приходится, как обычно, идти на компромисс: для реализаций с использованием связных списков требуется дополнительный объем памяти для ссылок, в то время как для реализаций с использованием массивов необходимо заранее знать максимальный размер таблицы или же предусмотреть увеличение таблицы с течением времени (см. раздел 14.5). Кроме того, как упоминалось в разделе 12.5, использование связных списков обладает гибкостью, позволяюшей эффективно реализовать другие операции типа join и remove.

Эти результаты во взаимосвязи с другими алгоритмами, освешенными далее в этой главе и главах 13 и 14, обобщены в табл. 12.1. В разделе 12.4 рассматривается бинарный поиск, при котором зависимость времени поиска от количества элементов уменьшается до IgA, в связи с чем он широко используется при работе со статическими таблицами (когда вставки выполняются сравнительно редко).

Таблица 12.1 Затраты на вставку и поиск в таблицах символов

Записи в этой таблице представляют приведенное к постоянному коэффициенту время выполнения как функцию от количества элементов в таблице N и размеров таблицы М (если он отличен от N) для реализаций, в которых новые элементы можно вставлять независимо от наличия в таблице элементов с дублированными ключами. При реализации элементарных методов (первые четыре строки) время выполнения некоторых операций постоянно, а время выполнения других линейно зависит от количества элементов или размеров таблицы; более сложные методы гарантируют логарифмическую зависимость времени от количества элементов или же постоянство времени выполнения большинства или всех операций. Значения N\gN в столбце операции выбора представляют затраты на сортировку элементов - линейная

зависимость времени выполнения операции select для неупорядоченного набора элементов возможна лишь теоретически, но не на практике (см. раздел 7.8). Значения, помеченные звездочкой, относятся к крайне нежелательным худшим случаям.

В разделах 12.5-12.9 рассматриваются деревья бинарного поиска, которые обеспечивают определенную гибкость в том, что время поиска и вставки становится пропорциональным IgTV, но только в среднем. В главе 13 будут исследоваться деревья типа красное черное (red-black tree) и рандомизованные деревья бинарного поиска, которые, соответственно, гарантируют логарифмическую зависимость времени от количества элементов либо существенно увеличивают вероятность этого. В главе 14 изучаются вопросы хеширования, которое в среднем обеспечивает постоянство времени поиска и вставки, но не обеспечивает эффективную поддержку операции sort и ряда других операций. В главе 15 будут рассматриваться методы поразрядного поиска, которые аналогичны методам поразрядной сортировки, описанным в главе 10; в главе 16 исследуются методы, применимые к файлам, которые хранятся внешне.

Упражнения

> 12.16 Добавьте операцию remove в приведенную реализацию таблицы символов с использованием упорядоченного массива (программа 12.5).

t> 12.17 Создайте функции searchinsert для приведенных реализаций таблиц символов с использованием списка (программа 12.6) и массива (программа 12.5). Функции должны выполнять в таблице символов поиск элемента с заданным ключом, а затем вставлять элемент, если таковой в таблице отсутствует.

12.18 Создайте операцию select для приведенной реализации таблицы символов с использованием списка (программа 12.6).

12.19 Укажите количество операций сравнения, необходимое для помещения ключей EASYQUESTIONb первоначально пустую таблицу с использованием АТД, которые реализованы в соответствие с одним из четырех элементарных подходов: упорядоченный или неупорядоченный массив или список. Примите, что для каждого ключа выполняется поиск, а затем, в случае его отсутствия в таблице, выполняется вставка, как в упражнении 12.17.

12.20 Реализуйте операции construct, search и insert для интерфейса таблицы символов профаммы. 12.2, используя для представления таблицы символов неупорядоченный массив. Характеристики производительности профаммы должны соответствовать табл. 12.1.

о 12.21 Реализуйте операции construct, search и insert для интерфейса таблицы символов профаммы 12.2, используя для представления таблицы символов упорядоченный связный список. Характеристики производительности профаммы должны соответствовать табл. 12.1.

о 12.22 Измените представленные реализации таблицы символов с использованием списка (профамма 12.6), чтобы они поддерживали дескрипторы элемента клиента (см. упражнение 12.7); добавьте десфуктор, конструктор копирования и перефужен-ную операцию присваивания (см. упражнение 12.6); добавьте операции remove и join; создайте профамму-драйвер, тестирующую созданные интерфейс и реализацию АТД первого класса таблицы символов.

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

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

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

о 12.26 Какую реализацию таблицы символов следовало бы использовать для приложения, в котором в произвольном порядке выполняется 10 операций insert, 10 операций search и 10 * операций select ? Обоснуйте ответ.

о 12.27 (В действительности это упражнение состоит из пяти упражнений). Дайте ответ на вопрос упражнения 12.26 для пяти других вариантов сочетания операций и частоты их использования.

12.28 Алгоритм самоорганизующегося поиска - это алгоритм, которые изменяет порядок элементов так, чтобы часто запрашиваемые элементы, скорее всего, находились в начале поиска. Измените реализацию операции search для упражнения 12.20, чтобы при каждом попадании при поиске она выполняла следующее действие: помещала найденный элемент в начало списка, перемещая на одну позицию вправо все элементы, расположенные между началом списка и освободившейся позицией. Эта процедура называется эвристическим перемещением вперед.