1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 26
Текст из файла (страница 26)
Аналогично строка 8 предполагает, что над непересекающимися множествами узлов мы можем выполнить операцию ОБЪЕДИНИТЬ. Отыскать структуру данных, на которой быстро выполняется операция ОБЪЕДИНИТЬ или НАЙТИ, довольно легко. Но здесь требуется, чтобы на одной структуре данных можно было легко реализовать обе операции ОБЪЕДИНИТЬ и НАЙТИ. Более того, поскольку выполнение операции ОБЪЕДИНИТЬ в строке 8 зависит от результата выполнения операций НАЙТИ в строке 7, требуемая последовательность операций ОБЪЕДИНИТЬ и НАЙТИ должна выполняться в префиксном режиме. Две такие структуры изучаются в равд.
4.6 и 4.7. Рассмотрим последовательность операций, выполняемых иа множестве ребер Е. В строке 6 применяется основная операция М!Н, а в строке 6 — операция УДАЛИТЬ. Хорошая структура данных для этих двух операций нам уже встречалась — сортирую- 131 гл. ь стггктггы длнных для злдлч с множвствлми щее дерево из разд. 3.4. (Хотя там с помощью сортирующего дерева разыскивался наибольший элемент, должно быть ясно, что с его помощью можно также найти и наименьший элемент.) Наконец, множество Т ребер остовного дерева нуждается только в операции ВСТАВИТЬ в строке 9 для добавления к Т нового ребра.
Здесь достаточно простого списка. (З 4.2. МЕТОД РАССТАНОВНИ Кроме вопроса о том, какие операции появляются в данной последовательности и, возникает еще один важный вопрос, связанный с выбором подходящей структуры данных для выполнения о. Это вопрос о размере базы данных (универсального множества), на которой работают операции нз и. Например, в гл. 3 мы видели, что с помощью сортировки вычерпыванием можно упорядочить последовательность из и элементов за линейное время, если элементами рассматриваемого множества являются целые числа, заключенные между подходящими границами.
Однако если эти элементы берутся из произвольного линейно упорядоченного множества, то наилучшим временем, которого мы смогли добиться, было время О (и 1ой и). В данном разделе мы исследуем задачу о том, как поддержать определенную структуру в изменяющемся множестве Я. Новые элементы будут добавляться к 5, старые — удаляться из 5, и время от времени надо будет отвечать на вопрос: "Принадлежит ли в данный момент элемент х множеству Я?" Эта задача естественно моделируется словарем; нам нужна структура данных, которая позволит добно выполнять последовательности, состоящие из операций РИНАДЛЕ)КАТЬ, ВСТАВИТЬ и УДАЛИТЬ.
Мы будем предполагать, что элементы, которые могут появиться в 5, берутся из очень большого универсального множества, так что представлять 3 в виде двоичного вектора неразумно с практической точки зрения. Пример 4.2. Транслятор или ассемблер следит за "таблицей символов" всех идентификаторов, которых он встретил в транслируемой программе. Для большинства языков программирования множество всех возможных идентификаторов очень велико. Например, в Фортране около 1,62х10' возможных идентификаторов. Поэтому нереально представить таблицу символов массивом с одним входом для каждого возможного идентификатора независимо от того, по.
является он в программе на самом деле или нет. Операции, производимые транслятором с таблицей символов, относятся к двум типам. Во-первых, надо добавлять в таблицу новые идентификаторы, когда они появляются. Эта работа включает в себя образование той ячейки в таблице, где запоминается конкретный идентификатор и где можно запомнить данные о нем (например, вещественный он или целый). Во-вторых, время от времени трансля- 431 ЬХ МЕТОД РАССТАНОВКИ О «СиисоидяяяФ О ° - слисек дял лФ 1 ° «4)мвагфзе юг) хе 1 Рвс. 4.2.
Схема расстановки. тор может затребовать информацию о каком-нибудь идентификаторе (например, имеет ли этот идентификатор тип "целое"). Таким образом, структура данных, способная обеспечить выполнение операций ВСТАВИТЬ и ПРИНАДЛЕЖАТЬ, вероятно, достаточна для реализации таблицы символов.
И действительно, структура данных, обсуждаемая в этом разделе, часто используется для реализации таблицы символов. (') Мы рассмотрим способ расстановки, обеспечивающий выполнение не только операций ВСТАВИТЬ и ПРИНАДЛЕЖАТЬ, необходимых для построения таблицы символов, но и операции УДАЛИТЬ. Известно много вариантов этого способа, ио мы обсудим здесь только основную идею. Схема расстановки показана иа рнс.
4.2.Функция расстановки й отображает элементы универсального множества (например, в случае таблицы символов все возможные идентификаторы) в множество целых чисел от О до т — !. Мы будем предполагать, что для всех элементов о значение 6(а) можно вычислить за постоянное время. Компонентами массива А размера т служат указатели на списки элементов множества 5.
Список, иа который указывает АИ, состоит из всех тех элементов о Е 5, для которых й(а)=-Ь Чтобы выполнить операцию ВСТАВИТЬ(а, 5), надо вычислить л(а) и затем просмотреть список, на который указывает А[п(а)1 Если элемента а в этом списке нет, его надо добавить к концу списка.
Чтобы выполнить операцию УДАЛИТЬ(а, 5), надо также просмотреть список А(А(а)! и удалить элемент а, если он там есть. Аналогично просматривается список А(й(а)! и в случае операции ПРИНАДЛЕЖАТЬ (а, Я). Вычислительную сложность этой схемы расстановки легко проанализировать. С точки зрения работы в худшем случае она не очень хороша. Например, допустим, что последовательность а состоит из и различных операций ВСТАВИТЬ. Может случиться, что на всех элементах, которые надлежит вставить, й принимает одинаковые значения, так что все элементы оказываются в одном и том же спис- гл.
а стаиктипы данных лля задач с множкстзами ке. В этой ситуации для выполнения 1-й операции из и требуется время, пропорциональное 1. Таким образом, чтобы добавить все и элементов к множеству 5, расстановка может потребовать времени порядка а'.. Однако в смысле среднего времени этот процесс выглядит много лучше. Если значение Й(а) с равной вероятностью может быть любым числом между О и т — 1 и вставляется паул элементов, то при вставке 1-го элемента средняя длина того списка, в который он помещается, равна (1 — 1)/гп, т. е.
всегда меньше 1. Поэтому среднее время, необходимое для вставки и элементов, есть 0(п). Если 0(п) операций УДАЛИТЬ и ПРИНАДЛЕЖАТЬ выполняются вместе с операциями ВСТАВИТЬ, то общее среднее время по-прежнему составляет 0 (и). Следует иметь в виду, что проведенный анализ предполагает, что размер гп таблицы расстановки не меньше максимального размера и множества Я, Однако л, как правило, заранее не известно. В таком случае разумнее всего подготовиться кпостроениюпоследовательностн таблиц расстановки Т,, Тп Тм.... Сначала выбирается подходящее значение и для размера исходной таблицы Т и. Затем, как только число элементов, вставленных в Т „ превзойдет т, строится новая таблица Т, размера 2т и с помощью новой функции расстановки ') все элементы, находящиеся в данный момент в Т е, перемещаются в таблицу Т,. Теперь старая таблица Т, больше не нужна.
Вставка новых элементов в Т, продолжается до тех пор, пока число элементов не превзойдет 2ле. В этот момент создается новая таблица Та размера 4т и меняется функция расстановки, чтобы переместить старые элементы из Т, в Т,. Вообще всякий раз, когда в таблице Т, оказывается 2а-'и элементов, строится таблица Тд размера 2 гп.
Процесс продолжается до тех пор, пока не будут исчерпаны все элементы. Подсчитаем среднее время, требуемое для вставки в таблицу расстановки 2аэлементов, если применять изложенную только что схему и считать и=1. Легко видеть, что этот процесс описывается рекуррентным уравнением т(1)=1, Т(2а) =Т(2а ')+2", решением которого, очевидно, служит Т(2а)=2а+' — 1. Таким образом, с помощью расстановки последовательность из а операций ВСТАВИТЬ, ПРИНАДЛЕЖАТЬ и УДАЛИТЬ можно выполнить за среднее время 0(п).
Здесь важен выбор функции расстановки й. Если элементы, добавляемые в 5, представлены целыми числами, равномерно распределенными между О и некоторым числом г~)а, то в качестве л(а) ') Эта функция принимает значения от О до зи — 1. 4.к дВОичный поиск можно взять а тод т, где и — размер таблицы расстановки в данный момент. Другие примеры функций расстановки приведены в работах, упоминаемых в конце главы.
4.3. ДВОИЧНЫЙ ПОИСК В данном разделе сравниваются три различных решения одной простой задачи поиска. Дано множество 5 из и элементов, взятых из большого универсального множества. Требуется выполнить последовательность а, состоящую только из операций ПРИНАДЛЕЖАТЬЬ. Наиболее прямым путем решения было бы запомнить элементы множества 5 в некотором списие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
