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

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). Возможен ли еще более эффективный подход?

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

Однако если бы элемент можно было связать с уникальным индексом, его можно было бы найти посредством однонаправленного действия: просто извлекая элемент, расположенный в позиции MyList[ItemIndex]. Это пример поиска с использованием индексирования по ключу, когда ключ элемента преобразуется в индекс, и элемент извлекается из массива с помощью этого индекса. Такой подход кардинально отличается от бинарного поиска, при котором, по существу, ключ элемента используется для перемещения по структуре с применением метода, в основе которого лежит сравнение.