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

о 16.43 Экспериментально определите количество случайных чисел, которые предположительно будут сгенерированы прежде, чем будет найдено более М чисел с одинаковыми d начальными разрядами, при Л/ = 10, 100 и 1000 и при 1 < < 20.

16.44 Измените хеширование с раздельным связыванием (программа 14.3), чтобы в нем использовалась хеш-таблица размером 2М, а элементы хранились на страницах размером 2М. Другими словами, когда страница заполняется, она связывается с новой пустой страницей, чтобы каждая запись хеш-таблицы указывала на связный список страниц. Экспериментально определите среднее количество зондирований, необходимое для выполнения поиска после построения таблицы из N элементов со случайными ключами, при М= 10, 100 и 1000 и = 10\ \(f, 10 и 10

о 16.45 Измените двойное хеширование (программа 14.6), чтобы в нем использовались страницы размером 2М при интерпретации обрашений к полным страницам в качестве коллизий . Экспериментально определите среднее количество зондирований, необходимое для выполнения поиска после построения таблицы из элементов со случайными ключами, при Л/ = 10, 100 и 1000 и N= 10 Ю, 10 и 10 при начальном размере таблицы равном 2>N/2M.

16.5 Перспективы

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

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

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

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

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

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

Упражнения

16.46 Разработайте реализацию таблицы символов с использованием В-деревьев, которая включает в себя деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции construct, count, search, insert, remove и join для АТД первого класса таблицы символов с обеспечением поддержки дескрипторов клиента (см. упражнения 12.6 и 12.7).

16.47 Разработайте реализацию таблицы символов с использованием расширяемого хеширования, которая включает в себя деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции construct, count, search, insert, remove и join для АТД первого класса таблицы символов с обеспечением поддержки дескрипторов клиента (см. упражнения 12.6 и 12.7).

16.48 Модифицируйте реализацию В-дерева, приведенную в разделе 16.3 (программы 16.1 - 16.3), чтобы в ней для ссылок на страницы использовался абстрактный тип данных.

16.49 Модифицируйте реализацию расширяемого хеширования, приведенную в разделе 16.4 (программы 16.5-16.8), чтобы в ней для ссылок на страницы использовался абстрактный тип данных.

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

16.51 Оцените среднее количество зондирований, затрачиваемое на каждый поиск в расширяемой хеш-таблице, для модели кэш-памяти, описанной в упражнении 16.50.

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

16.53 Реализуйте АТД очереди с приоритетами, который поддерживает операцию construct для очень большого количества элементов, за которой следует очень большое количество операций insert, remove и maximum (см. главу 9).

16.54 Разработайте АТД внешней таблицы символов, основанной на применении представления В-деревьев в виде списка пропусков (см. упражнение 13.80).

16.55 Если используемая система поддерживает виртуальную память, проведите эксперименты с целью определения значения Л/, обеспечивающего наименьшее время выполнения для реализации В-дерева, которое поддерживает случайные операции insert в очень большой таблице символов. (Прежде чем выполнять подобные эксперименты, которые могут потребовать больших затрат, возможно, стоит изучить основные характеристики используемой системы.)

16.56 Модифицируйте реализацию В-дерева, приведенную в разделе 16.3 (программы 16.1-16.3), чтобы она работала в среде, в которой таблица размещается на внешнем устройстве хранения информации. Если система допускает произвольный доступ к файлам, поместите всю таблицу в один (очень большой) файл и в структуре данных вместо указателей используйте смещение внутри файла. Если система допускает непосредственное обращение к страницам на внешних устройствах, в структуре данных вместо указателей используйте адреса страниц. Если система допускает оба вида доступа, выберите подход, который, по вашему мнению, наиболее подходит для реализации очень большой таблицы символов.

16.57, Модифицируйте реализацию расширяемого хеширования, приведенную в разделе 16.4 (программы 16.5-16.8), чтобы она работала в среде, в которой таблица размещается на внешнем устройстве хранения информации. Поясните причины выбранного подхода к распределению каталога и страниц по файлам (см. упражнение 16.56).

Литература, использованная в части 4

Основными источниками для этого раздела являются книги Кнута (Knuth); Баеца-Ятса (Baeza-Yates) и Гонне (Gonnet); Мехлхорна (Mehlhom); Кормена (Gormen), Лейзерзона (Leiserson) и Ривеста (Rivest). В этих книгах подробно рассматриваются многие из приведенных в этой части алгоритмов, вместе с математическим анализом и предложениями по практическому применению. Классические методы подробно изложены в книге Кнута. Более новые методы описаны в других книгах, в них же приводятся ссылки на другую литературу. В этих четырех источниках, а также в книге Седжвика (8е(1зе\у1ск)-Флажолета (Flajolet) описан практически весь материал, который упоминается, как выходящий за рамки этой книги .

Материал, приведенный в главе 13, взят из статьи Роура (Roura) и Мартинеца (Martinez) 1996 г., статьи Слеатора (Sleator) и Тарьяна (Tarjan) 1985 г. и статьи Гюи-