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. Тем не менее, даже в этом случае не исключается возможность возникновения пробуксовки.
Резюме
Эта глава была посвящена исследованию проблемы случайных чисел с нескольких точек зрения: с точки зрения генерирования последовательности случайных чисел и их применения для создания структуры данных не с прогнозируемыми, но вероятностными характеристиками.
Были приведены несколько методов генерации случайных чисел, распределенных по равномерному закону, в частности, мультипликативный конгруэнтный генератор, комбинационный и аддитивный генераторы, а также тасующий генератор. Для всех этих генераторов были представлены методы статистической оценки генерируемых ими последовательностей случайных чисел, которые позволяют оценить случайность получаемых результатов. Кроме того, были описаны два алгоритма генерации случайных чисел с другими распределениями: нормальным и экспоненциальным.
И, наконец, был рассмотрен список с пропусками - структура данных, используемая для хранения данных в отсортированном порядке. Было показано, каким образом случайные числа позволяют повысить характеристики быстродействия списков с пропусками.
Глава 7. Хеширование и хеш-таблицы
В главе 4 были рассмотрены алгоритмы поиска элемента в массиве (например, TList) или в связном списке. Наиболее быстрым из рассмотренных методов был бинарный поиск, для выполнения которого требовался отсортированный контейнер. Бинарный поиск представляет собой алгоритм класса O(log(n)). Так, чтобы установить наличие или отсутствие заданного элемента в списке из 1000 элементов, требуется выполнить приблизительно 10 сравнений (поскольку 2(^10^) = 1024). Возможен ли еще более эффективный подход?
