Д. Кнут - Искусство программирования том 1 (1119450), страница 68
Текст из файла (страница 68)
(10) ВАЯВ[!+ 1] является базовым адресом (1 + 1)-го стека. Условие ТОР[1] = ВАЯЕ[1] означает,что стек ]пуст. В алгоритме (9) условие избытка ОЧЕВРЬОЧ уже не является таким критичным, как прежде. Теперь можно "переупаковать память", предоставляя больше свободного пространства для переполняющейся таблицы за счет незанятого пространства из незаполненных таблиц. Можно использовать сразу несколько способов переупаковки, причем некоторые из них будут рассмотрены подробно, так как они очень важны для организации последовательного упорядочения линейных списков.
Сначала рассмотрим наиболее простые способы, а затем — некоторые альтернативные им варианты. Предположим, что существует и стеков и что значения ВАБЕ[1] и ТОР [Л обрабатываются согласно алгоритмам (9) и (10), Предполагается также, что эти стеки совместно используют общую область памяти, состояшую из 1. ячеек, удовлетворяющих условию Ьв < Ь < Ь . (Здесь Ьо и 1.
— константы, которые задают общий размер доступной памяти в словах.) Начнем с рассмотрения случая, когда все стеки пусты, т. е. ВАБЕ[у] = ТОР[у] = Ье для 1 < ] < п. Предположим также, что ВАЯЕ[я+ 1] = 1., и тогда алгоритм (9) будет применим для? = и. При переполнении (ОЧЕЕРЬОЫ) стека? возможны три варианта развития событий.
а) Найдем наименьшее А, для которого 1 < А < и и ТОР[А] < ВАЯЕ[А+ 1], если такое к существует. Теперь переместим все элементы на один узел вверх: СОМТЕМТБ(1. + 1) г- СОМТЕМТБ(1.) для ТОР[К > 1. > ВАБЕ[1 + Ц . (Во избежание утраты информации это следует делать в порядке убывания, а не возрастания значений Ь.
Если ТОР[А] = ВАБЕ[1 + 1], такие перемещения выполнять не потребуется.) Наконец, ВАЯВ[у] ~ — БАБЕ[у] + 1 и ТОРИ гТОР 5] + 1 для 1 < у < й. Ь) Допустим, что ни одно А не удовлетворяет условию (а), но существует такое наибольшее А, для которого 1 < А < 1 и ТОРЯ] < ВАЯЕ[к + 1]. Переместим все элементы на один узел вниз: СОМТЕМТБ[Ь вЂ” 1) <†СОМТЕМТБ[Ь) для БАБЕ[А + 1] < Ь < ТОРЫ .
(Это нужно сделать только в порядке возрастания значений Ь.) Затем ВАБЕ[у] <†ВАЯЕ[у] — 1 и ТОР[у] < — ТОР[у] — 1 для Й < у < ю'. с) Допустим, что ТОР[/с] = ВАБЕ[А + 1] для всех Й ~ 1. Тогда очевидно. что для нового элемента стека нельзя найти свободное пространство, и поэтому работу программы придется прервать. На рис. 4 показан пример конфигурации памяти для случая, когда а = 4, 1.е = О, Ьь, = 20, по окончании последовательного выполнения действий (12) 1~ ?~ ?4 ?т П ~ 1з ?~ ?~ ?т 14 ?]з Пы (Здесь 1з и 01 относятся к операциям вставки и удаления в стеке у] а звездочка обозначает переполнение (ОЧЕЕРЬОМ).
При этом предполагается, что в начальный момент для стеков 1-3 пространство в памяти не выделялось.) Ясно что в начальный момент многих ситуаций переполнения стеков можно избежать, если выбрать оптимальные начальные условия вместо выделения сразу всего доступного пространства в памяти для и-го стека, как предлагается в условии (11).
Например, если предполагается, что размеры всех стеков равны, то следует 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 18 17 18 19 20 сч о ° ы о и ч й3 ч ч 'э ы а ю и а и ь Ф ОЭ 03 4'4 о СР $ Ю ОЗ ч й3 выбрать следующие начальные условия: Вша~а =тОР1л=[( — )а — ~)]~а !ГГГ . ао Очевидно, что, обладая определенным опытом работы с некоторой программой. можно предложить более подходящие начальные значения.
Однако независимо от типа начального распределения таким образом можно избежать лишь незначительного фиксированного количества событий переполнения, причем этот эффект будет заметен только на начальных стадиях работы программы (см. упр. 17). Другой возможный способ усовершенствования рассматриваемого метода основан на выделении при каждой переупаковке памяти объема свободного пространства, достаточного для размещения более чем одного нового элемента таблицы. Эта идея была использована й.
В. Гарвиком, который предложил полностью переупаковывать память при каждом событии переполнения на основе изменения хая~лого стека по окончании последней переупаковки, В его алгоритме используется дополнительный массив значений ОЕВТОР[7], 1 < ] < и, которые равны значениям ТОР [у] сразу после предыдущего выделения памяти.
В исходном состоянии таблицы выглядят так же, как и прежде, т. е. 01.ВТОР [2] = ТОР [у]. Этот алгоритм состоит из следующих шагов. Алгоритм С (Перераспределение последовательных таблиц). Предположим, что переполнение (ОЧЕЕРЕОУ) произошло в стеке 1 согласно условиям (9). После выполнения алгоритма 6 либо будет исчерпана емкость памяти, либо память будет переупо.
рядочена таким образом, что сможет быть выполнена операция ИООЕ(ТОР [4] ) э — Т (Обратите внимание, что значение ТОР [г] увеличено в (9) еще до применения алгоритма С.) С1. [Инициализация.] Пусть ЕОИ с — 1. — 1.о, 1ИС < — О. Выполним шаг С2 для 1 < у < и. (В результате ЕОИ будет равно общему размеру доступного пространства в памяти, а 1ИС вЂ” общему количеству последовательных увеличений размеров стеков по завершении последнего распределения памяти.) Выполнив эти действия, перейдем к шагу СЗ.
С2. [Сбор статистических данных.] Пусть БОИ +- БОМ вЂ” (ТОР[]] — ВАЗЕ[]]). Если ТОР[Я > О1.ВТОР[1], то В[]] +- ТОР[]] — ОЕВТОР[у] и 1ИС < — 1ИС+ В[2]; в противном случае В[у] < — О. СЗ. [Ресурсы памяти исчерпаны?] Если БОИ < О работа не может быть продолжена. Рнс. 4. Пример конфягурапии памяти после выполнения нескольких операций вставки в удаленяя. С4. [Вычисление показателей перераспределения памяти.] Пусть о е- 0.1 х БОМ/и, Я е — 0.9 х БОМ/1ИО. (Здесь о и,б — дробные, а не целые числа, которые необходимо вычислить с заданной точностью. На следующем этапе доступное пространство будет равпределено среди отдельных списков следующим образом: приблизительно 10% доступной памяти будет распределено поровну среди и стеков, а оставшиеся 90% будут разделены пропорционально увеличению размера стеков со времени предыдущего распределения памяти.) СЯ. [Вычисление новых базовых адресов.] Пусть ИЕИВАЯЕ[1] +- ВАЯВ[1] и о е — 0; тогда для у = 2, 3,..., и установим такие значения: т < — о + о + О [) — 1] д, ИЕЧВАБЕ[у] < — ИЕЧВАЯЕ[у — 1] + ТОР [у — Ц вЂ” ВАЯЕ[,1 — П + [т] — [о] н о е — т.
Сб. [Переупаковка.] Пусть ТОР И е- ТОР [1] — 1. (Таким образом задается истинный размер г'-го стека для того, чтобы не предпринимались попытки переместить информацию за его пределами.) Выполните приведенный ниже алгоритм К, а затем установите ТОР[1] < — ТОР[1] + 1. Наконец, установите 01ОТОР[1] ~— ТОР[]] для 1 < у < п. 1 Вероятно, наиболее интересной частью всего этого алгоритма является сам процесс перераспределения, который описывается ниже.
Он не совсем тривиален, поскольку одни фрагменты памяти смещаются вниз, а другие — вверх. Очевидно, что очень важно не наложить перемещаемый фрагмент памяти на другую полезную информацию, после чего она может быть полностью утрачена. Алгоритм К (Перемещение последовагпельнмх таблиц). Для 1 < 1 < и информация, заданная с помощью адресов ВАЯЕ [у] и ТОР [у] в соответствии с указанными выше соглашениями, перемещается на новое место, задаваемое с адресами ИЕИВАЯЕ [Я, а сами величины ВАЯЕ [1] и ТОР [у] после этого принимают новые значения. Данный алгоритм основан на легко проверяемом условии, что перемещаемые вниз данные не должны пересекаться с любыми другими перемещаемыми вверх данными, а также с любыми неперемещаемыми данными.
К1. [Инициализация.] Установить ] < — 1. В2. [Поиск начала перемещения.] [Теперь все перемещаемые вниз стеки'с 1- до у'-го перемещены в новое место.) Будем последовательно увеличивать значение у с шагом 1 до тех пор, пока не выполнится одно из перечисленных ниже условий: а) ИЕИВАЯЕ[]] < ВАЯЕ[Д: перейти к шагу ВЗ; Ь) у > и: перейти к шагу Н4. ЙЛ. [Перемещение списка вниз.] Установить Б < — ВАЯЕ [у] — ИЕИВАЯЕ [у].
Установить СОИТЕИТЯ(1 — б) е — СОИТЕИТЯ(1) для 1. = ВАЯВ[)] + 1, ВАБЕ[1] + 2,..., ТОР[у] (Возможен вариант, когда значение ВАБЕ [у] равно ТОР [у]; тогда никаких действий предпринимать не следует.) Установить БАБЕ[у] е — ИЕИВАЯЕ[у], ТОР [у] +- ТОР [у] — б. Вернуться к шагу В.2. К4. [Поиск начала перемещения.] (Теперь все перемещаемые вниз стеки с 1'-го по п-й перемещены в нужное место.) Будем последовательно уменьшать значение у с шагом 1 до тех пор, пока не выполнится одно из перечисленных ниже условий: а) ИЕИВАЯЕ[у] > ВАЯВ[)]; перейти к шагу Вб; Ъ) у = 1: прервать выполнение алгоритма. На основе этого анализа можно сделать следующий вывод: при значительном количестве операций встайки элементов в таблицы количество перемещений может быть очень большим.
Это своеобразная компенсация за возможность компактной упаковки большого количества последовательных таблиц. Для анализа алгоритма С до снх пор не предложено ни одной теоретической модели, и маловероятно, что какая-либо простая теория сможет адекватно описать характеристики реальных таблиц при таких условиях работы. Однако в упр. 18 предлагается анализ самого неблагоприятного случая с оценкой времени выполнения, которое будет не таким большим, если память исчерпана не полностью. Как показывает опыт, при заполнении памяти наполовину (т. е. когда доступная область занимает половину всей памяти) с помощью алгоритма С перераспределение памяти нужно выполнить лишь в незначительной степени. Здесь важно отметить, что этот алгоритм эффективен при заполнении памяти наполовину, а при практически полном заполнении, по крайней мере, можно достоверно оценить его эффективность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
