таокп, вопросы последовательного распределения

Question

Я столкнулся с несколькими проблемами при работе с последовательными выделениями tacop 2.2.2, перепаковкой раздела памяти на стр. 247.

Субъект состоит из n стеков, разделяющих общие области L0

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

а). найти наименьшее k, для которого i СОДЕРЖАНИЕ (L), для TOP [k]> = L> BASE [i + 1] в конце концов, Установите BASE [j] -> BASE [j] + 1, TOP [j] -> TOP [j] + 1, для i

вот мои вопросы:

как они находят стек, который еще не заполнен? стек к? а почему выбрали самый маленький k?

Answer 1

Чтобы найти стек, который еще не заполнен, используется основная идея:

Стек k не заполнен <==> TOP[k] < BASE[k+1]

Цикл на первом шаге алгоритма запускает k с i+1 до n, чтобы найти первый k, который удовлетворяет этому условию.

Также обратите внимание, что изначально все пространство дается последнему, n th, стеку путем установки BASE[n] = TOP[n] = L0 и BASE[n+1]=LInfty. Так что, если не заполнить все «более высокие» стеки, мы найдем такой k.

На ваш второй вопрос (почему выбирается наименьшее из таких k?) Ответ легче: алгоритм на стр. 247 - это только один способ переупаковки и простой один в тот. Как упоминает Кнут в абзаце чуть выше текста алгоритма:

Несколько способов сделать переупаковку напрашиваются сами собой; ... Мы начнем с того, что дадим самый простой из методов, и затем рассмотрим некоторые из альтернатив.

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