Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

var

i : integer;

begin

inherited Create;

{функция сравнения не может быть nil}

if not Assigned(aCompare) then

slError(tdeSkpLstNoCompare, 'Create');

{создать диспетчеры узлов}

slGetNodeManagers;

{выделить начальный узел}

FHead := slAllocNode (pred( tdcMaxSkipLevels));

FHead^.sknData := nil;

{выделить конечный узел}

FTail := slAllocNode (0);

FTail^.sknData := nil;

{задать прямые и обратные указатели для начального и конечного узлов}

for i := 0 to pred(tdcMaxSkipLevels) do

FHead^.sknNext[i] := FTail;

FHead^.sknPrev := nil;

FTail^.sknNext[0] :=nil;

FTail^.sknPrev := FHead;

{установить курсор на начальный узел}

FCursor := FHead;

{сохранить функцию сравнения и процедуру dispose}

FCompare := aCompare;

FDispose :=aDispose;

{создать генератор случайных чисел}

FPRNG := TtdMinStandardPRNG.Create(0);

end;

destructor TtdSkipList.Destroy;

begin

Clear;

slFreeNode(FHead);

slFreeNode(FTail);

FPRNG.Free;

inherited Destroy;

end;

Конструктор использует функцию сравнения, что позволяет корректно выбирать позицию вставляемых узлов (конечно, функция сравнения не может быть nil). Кроме того, в качестве входного параметра присутствует процедура dispose. Если она содержит nil, список с пропусками не является владельцем хранящихся в нем данных, поэтому при удалении списка данные удаляться не будут. В противном случае список является владельцем данных, и при его удалении данные также будут удаляться. Конструктор Create создает начальный и конечный узлы и устанавливает их указатели. И, наконец, создается генератор случайных чисел. Он впоследствии будет использоваться в методе Add.

Деструктор Destroy очищает содержимое списка с помощью метода Clear, освобождает начальный и конечный узлы и уничтожает генератор случайных чисел.

Метод Clear предназначен для очистки содержимого всех узлов, находящихся между начальным и конечным узлами, путем прохождения списка по указателям нижнего уровня и уничтожения узлов.

Листинг 6.20. Очистка содержимого списка с пропусками

procedure TtdSkipList.Clear;

var

i : integer;

Walker, Temp : PskNode;

begin

{пройти по узлам уровня 0, освобождая все узлы}

Walker := FHead^.sknNext[0];

while (Walker <> FTail) do

begin

Temp Walker;

Walker := Walker^.sknNext[0];

slFreeNode(Temp);

end;

{восстановить начальный и конечный узлы}

for i := 0 to pred(tdcMaxSkipLevels) do

FHead^.sknNext[i] := FTail;

FTail^.sknPrev := FHead;

FCount := 0;

end;

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

Листинг 6.21. Выделение и уничтожение узлов в списке с пропусками

class function TtdSkipList.slAllocNode(aLevel : integer): PskNode;

begin

Result := SLNodeManager[aLevel].AllocNode;

Result^.sknLevel := aLevel;

end;

procedure TtdSkipList.siFreeNode(aNode : PskNode);

begin

if (aNode <> nil) then begin

if Assigned(FDispose) then

FDispose(aNode^.sknData);

SLNodeManager[aNode^.sknLevel].FreeNode(aNode);

end;

end;

class procedure TtdSkipList.slGetNodeManagers;

var

i : integer;

begin

{если диспетчеры узлов еще не созданы, создать их}

if (SLNodeManager[0] =nil) then

for i := 0 to pred(tdcMaxSkipLevels) do SLNodeManager[i] := TtdNodeManager.Create(NodeSize[i]);

end;

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

Остальные методы класса списка с пропусками еще проще - все они содержат всего несколько строк кода.

Листинг 6.22. Остальные методы класса списка с пропусками

procedure TtdSkipList.Delete

begin

{начальный и конечный узлы удалять нельзя}

if (FCursor = FHead) or (FCursor = FTail) then

slError(tdeListCannotDelete, 'Delete');

{удалить узел в позиции курсора}

Remove(FCursor^.sknData);

end;

function TtdSkipList.Examine : pointer;

begin

Result := FCursor^.sknData;

end;

function TtdSkipList.IsAfterLast : boolean;

begin

Result := FCursor = FTail;

end;

function TtdSkipList.IsBeforeFirst : boolean;

begin

Result := FCursor = FHead;

end;

function TtdSkipList.IsEmpty : boolean;

begin

Result := Count = 0;

end;

procedure TtdSkipList.MoveAf terLast;

begin

FCursor := FTail;

end;

procedure TtdSkipList.MoveBeforeFirst;

begin

FCursor := FHead;

end;

procedure TtdSkipList.MoveNext;

begin

if (FCursor <> FTail) then

FCursor := FCursor^.sknNext[0];

end;

procedure TtdSkipList.Move Prior;

begin

if (FCursor <> FHead) then

FCursor := FCursor^.sknPrev;

end;

С использованием набора диспетчеров узлов для списка с пропусками связана одна проблема, о которой мы еще не говорили. Она не так очевидна для связных списков. А заключается она в пробуксовке. Проблема пробуксовки становится все более заметной при увеличении количества узлов до миллионов. Дело в том, что в списке с пропусками соседние узлы, скорее всего, будут находиться в разных страницах памяти. Поэтому при последовательном прохождении по списку от начала до конца на пути будут попадаться узлы разного размера, находящиеся в разных страницах памяти. Это приводит к подкачке страниц. К сожалению, мы никак не можем устранить свопинг (при использовании списков с несколькими миллионами узлов данные узлов в любом случае могут находиться в разных страницах). Проблему можно немного смягчить за счет использования стандартного диспетчера кучи Delphi. Тем не менее, даже в этом случае не исключается возможность возникновения пробуксовки.

Эта глава была посвящена исследованию проблемы случайных чисел с нескольких точек зрения: с точки зрения генерирования последовательности случайных чисел и их применения для создания структуры данных не с прогнозируемыми, но вероятностными характеристиками.

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

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

В главе 4 были рассмотрены алгоритмы поиска элемента в массиве (например, TList) или в связном списке. Наиболее быстрым из рассмотренных методов был бинарный поиск, для выполнения которого требовался отсортированный контейнер. Бинарный поиск представляет собой алгоритм класса O(log(n)). Так, чтобы установить наличие или отсутствие заданного элемента в списке из 1000 элементов, требуется выполнить приблизительно 10 сравнений (поскольку 2(^10^) = 1024). Возможен ли еще более эффективный подход?

Если бы для выявления элемента обязательно нужно было использовать функцию сравнения, ответ на этот вопрос был бы отрицательным. Бинарный поиск -наиболее эффективный метод, который можно было бы использовать в этом случае.