4.2. МЕТОД РАССТАНОВКИ

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

В данном разделе мы исследуем задачу о том, как поддержать определенную структуру в изменяющемся множестве Новые элементы будут добавляться к старые — удаляться из и время от времени надо будет отвечать на вопрос: "Принадлежит ли в данный момент элемент х множеству Эта задача естественно моделируется словарем; нам нужна структура данных, которая позволит удобно выполнять последовательности, состоящие из операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ. Мы будем предполагать, что элементы, которые могут появиться в берутся из очень большого универсального множества, так что представлять в виде двоичного вектора неразумно с практической точки зрения.

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

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

транслятор может затребовать информацию о каком-нибудь идентификаторе (например, имеет ли этот идентификатор тип "целое").

Таким образом, структура данных, способная обеспечить выполнение операций ВСТАВИТЬ и ПРИНАДЛЕЖАТЬ, вероятно, достаточна для реализации таблицы символов. И действительно, структура данных, обсуждаемая в этом разделе, часто используется для реализации таблицы символов.

Мы рассмотрим способ расстановки, обеспечивающий выполнение не только операций ВСТАВИТЬ и ПРИНАДЛЕЖАТЬ, необходимых для построения таблицы символов, но и операции УДАЛИТЬ. Известно много вариантов этого способа, но мы обсудим здесь только основную идею.

Схема расстановки показана на рис. 4.2. Функция расстановки отображает элементы универсального множества (например, в случае таблицы символов все возможные идентификаторы) в множество целых чисел от до Мы будем предполагать, что для всех элементов а значение можно вычислить за постоянное время. Компонентами массива А размера служат указатели на списки элементов множества Список, на который указывает состоит из всех тех элементов для которых

Чтобы выполнить операцию ВСТАВИТЬ , надо вычислить и затем просмотреть список, на который указывает Если элемента а в этом списке нет, его надо добавить к концу списка. Чтобы выполнить операцию УДАЛИТЬ , надо также просмотреть список ] и удалить элемент а, если он там есть. Аналогично просматривается список и в случае операции ПРИНАДЛЕЖАТЬ .

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

Рис. 4.2. Схема расстановки.

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

Однако в смысле среднего времени этот процесс выглядит много лучше. Если значение с равной вероятностью может быть любым числом между и и вставляется элементов, то при вставке элемента средняя длина того списка, в который он помещается, равна т. е. всегда меньше 1. Поэтому среднее время, необходимое для вставки элементов, есть Если операций УДАЛИТЬ и ПРИНАДЛЕЖАТЬ выполняются вместе с операциями ВСТАВИТЬ, то общее среднее время по-прежнему составляет

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

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

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

решением которого, очевидно, служит

Таким образом, с помощью расстановки последовательность из операций ВСТАВИТЬ, ПРИНАДЛЕЖАТЬ и УДАЛИТЬ можно выполнить за среднее время

Здесь важен выбор функции расстановки Если элементы, добавляемые в представлены целыми числами, равномерно распределенными между и некоторым числом то в качестве

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