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

Question

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

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

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

а). найти наименьшее k, для которого i CONTENTS(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стековать, установив BASE[n] = TOP[n] = L0 а также BASE[n+1]=LInfty, Таким образом, если все "более высокие" стеки не будут заполнены, мы найдем такой k,

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

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

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