Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 103
Текст из файла (страница 103)
17.4 Динамические таблицы В некоторых приложениях заранее не известно, сколько элементов будет храниться в таблице. Может возникнуть ситуация, когда для таблицы выделяется место, а впоследствии оказывается, что его недостаточно. В этом случае приходится выделять больший объем памяти и копировать все объекты из исходной таблицы в новую, большего размера. Аналогично, если из таблицы удаляется много объектов, может понадобиться преобразовать ее в таблицу меньшего размера.
В этом разделе исследуется задача о динамическом расширении и сжатии таблицы. Методом амортизационного анализа будет показано, что амортизированная стоимость вставки и удаления равна всего лишь 0(1), даже если фактическая стоимость операции больше из-за того, что она приводит к расширению или сжатию таблицы. Более того, мы выясним, как обеспечить соблюдение условия, при котором неиспользованное пространство динамической таблицы не превышает фиксированную долю ее полного пространства. Предполагается, что в динамической таблице поддерживаются операции Тлв1.к 1мзккт и ТАвьк 13в.ктк.
В результате выполнения операции ТАвьк 1нвккт в таблицу добавляется элемент, занимающий одну ячейку (з1о1), — пространство для одного элемента. Аналогично, операцию Тлвьк 13Б.ктк можно представлять как удаление элемента из таблицы, в результате чего освобождается одна ячейка. Подробности метода, с помощью которого организуется таблица, не важны; можно воспользоваться стеком (раздел 10.1), пирамидой (глава 6) или хеш-таблицей (глава 11). Для реализации хранилища объектов можно также использовать массив или набор массивов, как это было сделано в разделе 10.3. Оказывается, достаточно удобно применить концепцию, введенную при анализе хеширования (глава 11). Определим коэффициент заполнения (1оай Гас1ог) а (Т) непустой таблицы Т как количество хранящихся в них элементов, деленное на ее размер (измеряемый в количестве ячеек).
Размер пустой таблицы (в которой нет ни одного элемента) примем равным нулю, а ее коэффициент заполнения— единице. Если коэффициент заполнения динамической таблицы ограничен снизу Часть 1У. Усовершенствованные методы разработки и анализа 496 константой, ее неиспользованное пространство никогда не превышает фиксированной части ее полного размера. Начнем анализ с динамической таблицы, в которую выполняются только вставки. Впоследствии будет рассмотрен более общий случай, когда разрешены и вставки, и удаления. 17.4.1 Расширение таблицы Предположим, что место для хранения таблицы выделяется в виде массива ячеек. Таблица становится заполненной, когда заполняются все ее ячейки или (что эквивалентно) когда ее юэффициент заполнения становится равным 1'.
В некоторых программных средах при попытке вставить элемент в заполненную таблицу не остается ничего другого, как прибегнуть к аварийному завершению программы, сопровождаемому выдачей сообщения об ошибке. Однаю мы предполагаем, что наша программная среда, подобно многим современным средам, обладает системой управления памятью, позволяющей по запросу выделять и освобождать блоки хранилища. Таким образом, когда в заполненную таблицу вставляется элемент, ее можно расигиригнь (ехрапд), вьщелив место для новой таблицы, содержащей больше ячеек, чем было в старой. Поскольку таблица всегда должна размещаться в непрерывной области памяти, для большей таблицы необходимо выделить новый массив, а затем — скопировать элементы из старой таблицы в новую.
Общепринятый эвристический подход заключается в том, чтобы в новой таблице было в два раза больше ячеек, чем в старой. Если в таблицу элементы толью вставляются, то значение ее коэффициента заполнения будет не меньше 1/2„поэтому объем неиспользованного места никогда не превысит половины полного размера таблицы. В приведенном ниже псевдокоде предполагается, что Т вЂ” объект, представляющий таблицу. Поле 1а61е [Т] содержит указатель на блок памяти, представляющий таблицу. Поле пит [Т] содержит количество элементов в таблице, а поле заве [Т] — полное юличество ячеек в таблице.
Изначально таблица пустая: пит [Т] = аззе [Т] = О. ТАВ1.Е 11чБЕКТ(Т, ш) 1 Изззе[Т] = О 2 реп Выделить память для 1а61е[Т] с 1 ячейкой 3 аале [Т] +- 1 4 и пит[Т] = аззе[Т] 5 Феп Выделить память для новой таблицы с 2 азде[Т] ячейками 'В некоторых случаях, например, при работе с хешированными таблицами с открытой адресацией может понадобиться считать таблицу заполненной, если ее юзффициент заполнения равен некоторой константе, строго меньшей 1. (См.
упражнение ! 7.4-1.) Глава 17. Амортизационный анализ 497 Вставить все элементы из гаЫе]Т] в ие!е 1аИе Освободить !аЫе 1Т] $аИе]Т] — ие!е 1аИе з)яе !Т] - 2 з1зе !Т] Вставить ж в 1аИе]Т] инги]Т] + — иитп]Т] + 1 6 7 8 9 1О 11 г если г — 1 является степенью 2, с= 1 в противном случае. Таким образом„полная стоимость выполнения п операций ТАвьв 1мзвкт равна и 1!я н) ~! с; <и+ ~~> 21 (п+2и=Зп, , — о Обратите внимание, что здесь имеется две "вставки": сама процедура тлввв 1нзвкт и операция элемеитарной вставки (е1ешеп!агу шзегйоп) в таблицу, выполняемая в строках 6 и 10. Время работы процедуры ТАвьв 1нзвкт можно проанализировать в терминах количества элементарных вставок, считая стоимость каждой такой операции равной 1.
Предполагается, что фактическое время работы процедуры Тлв!.в 1нзвкт линейно зависит от времени вставки отдельных элементов, так что накладные расходы на выделение исходной таблицы в строке 2 — константа, а накладные расходы на выделение и освобождение памяти в строках 5 и 7 пренебрежимо малы по сравнению со стоимостью переноса элементов в строке 6. Назовем расширением (ехрапз!оп) событие, при котором выполняется оператор 1йеп !строки 5-9). Проанализируем последовательность и операций Тлвье 1хзвкт, которые выполняются над изначально пустой таблицей.
Чему равна стоимость с, 1-й операции? Если в данный момент в таблице имеется свободное место (или если это первая операция), то с; = 1„поскольку достаточно выполнить лишь одну элементарную операцию вставки в строке 10. Если же таблица заполнена и нужно произвести ее расширение, то с; = г: стоимость равна 1 для элементарной вставки в строке 10 плюс 1 — 1 для элементов, которые необходимо скопировать из старой таблицы в новую (строка 6). Если выполняется п операций, то стоимость последней из них в наихудшем случае равна 0 (и), в результате чего верхняя граница полного времени выполнения п операций равна 0 (и ). Эта оценка является неточной, поскольку при выполнении п операций Тлввв 1нзвкт потребность в расширении таблицы возникает не так часто.
Точнее говоря, 1-я операция приводит к расширению, только если величина г — 1 равна степени двойки. С помощью группового анализа можно показать, что амортизированная стоимость операции в действительности равна 0 (1). Стоимость 1-й операции равна Часть!Ч. Усовершенствованные методы разработки н анализа 498 Ф (Т) = 2 пит [Т] — згяе [Т] .
(17.5) Сразу после расширения выполняется соотношение пит [Т] = згае [Т]/2, поэтому, как и требуется, Ф (Т) = О. Непосредственно перед расширением справедливо равенство пит [Т] = з1зе [Т], следовательно, как и требуется, Ф (Т) = пит [Т]. Начальное значение потенциала равно О, и поскольку таблица всегда заполнена не менее чем наполовину, выполняется неравенство пит [Т] > язе [Т]/2, из юторого следует, что функция Ф (Т) всегда неотрицательна. Таким образом, суммарная амортнзированная стоимость и операций Тлвее 1хзект является верхней границей суммарной фактичесюй стоимости.
Чтобы проанализировать амортизированную стоимость 1-й операции Тлв1е 1нзект, обозначим через пит; количество элементов, хранящихся в таблице после этой операции, через з1зе; — общий размер таблицы после этой операции, и через Ф; — потенциал после этой операции. Изначально пито = О, з1зео = О и Фо = О. поскольку стоимость не более и операций равна 1, а стоимости остальных операций образуют геометрическую прогрессию. Поскольку полная стоимость и операций Тлвье 1нзект равна Зп, амортизированная стоимость одной операции равна 3. С помощью метода бухгалтерского учета можно показать "на пальцах", что амортизированная стоимость операции Тлвье 1нзект должна быть равна 3. Интуитивно понятно, что для каждого элемента приходится трижды платить за элементарную операцию вставки: за саму вставку в текущую таблицу, за перемещение этого элемента при расширении таблицы и за перемещение еще одного элемента, юторый уже однажды был перемещен в ходе расширения таблицы.
Например, предположим, что сразу после расширения таблицы ее размер становится равным т. Тогда количество элементов в ней равно т/2 и таблице соответствует нулевой кредит. На каждую вставку начисляется по 3 грн. Элементарная вставка, которая выполняется тут же, стоит 1 грн. Еще 1 грн. зачисляется в кредит на вставляемый элемент. Третья гривня зачисляется в качестве кредита на один из уже содержащихся в таблице т/2 элементов. Для заполнения таблицы требуется т/2 — 1 дополнительных вставок, поэтому к тому времени, когда в таблице будет т элементов и она станет заполненной, каждому элементу будет соответствовать гривня, предназначенная для уплаты за его перемещение в новую таблицу в процессе расширения. Анализ последовательности из и операций Тлвье 1нзект можно выполнить и с помощью метода потенциалов.
Этим мы сейчас и займемся; кроме того, этот метод будет использован в разделе 17.4.2 для разработки операции Тлвье 0и.ете, амортизированная стоимость которой равна 0 (1). Начнем с того, что определим потенциальную функцию Ф, юторая становится равной О сразу после расширения и достигающей значения, равного размеру матрицы, к тому времени, когда матрица станет заполненной. В этом случае предстоящее расширение можно будет оплатить за счет потенциала. Одним из возможных вариантов является функция Глава 17. Амортизационный анализ 499 Если г-я операция Тливо 1нзвкт не приводит к расширению, то звве; = ввге; ~ и амортизированная стоимость операции равна с~ с4 + Ф~ ф$1 = 1+ (2 пит; — авве;) — (2. пит; з — виве; ~) = = 1+ (2 пит; — авве;) — (2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
