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

function ExponentialRandomNumber( aPRNG : TtdBasePRNG;

aMeart : double): double;

var

R : double;

begin

repeat

R := aPRNG.AsDouble;

until (R <> );

Result := -aMean * ln(R);

end;

И снова обратите внимание, что исключается редкий случай, когда значение равномерно распределенного случайного числа равно 0, поскольку от него будет браться натуральный логарифм.

Списки с пропусками

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

Код класса для списков с пропусками можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSkpLst.pas.

Помните, в главе 4 мы говорили о том, что при необходимости поиска определенного значения в связном списке нужно начать с его начала и проходить по узлам с помощью указателей Next до тех пор, пока не будет найдено искомое значение. Если список был отсортирован, можно было воспользоваться алгоритмом бинарного поиска, который позволяет минимизировать количество выполняемых сравнений, тем не менее, при этом для прохода по списку также применялись указатели Next.

Вильям Пью (William Pugh) в 1990 году в своей статье "Списки с пропусками: вероятностная альтернатива сбалансированным деревьям" ("Skip Lists: Probabilistic AItemative to Balanced Trees") [18] показал, что существует более удобная альтернатива связным спискам, если мы готовы использовать узлы большего размера с большим количеством указателей.

Вильям Пью разработал вариант не совсем обычного связного списка. На своем самом низком уровне это двухсвязный список с прямым указателем на следующий узел и обратным указателем на предыдущий узел. Однако в некоторых узлах списка с пропусками имеется еще один прямой указатель, направленный на узел, расположенный на несколько позиций вперед. Такой указатель позволяет "перепрыгнуть" через целый ряд других, обычных узлов. Кроме того, в некоторых из этих расширенных узлов имеется еще один дополнительный указатель, который позволяет перешагнуть еще дальше. Таким образом, список с пропусками выглядит примерно так, как показано на рис. 6.3. Обратите внимание, что, в конце концов, все указатели приходят к конечному элементу списка, а начальный узел является началом для прямых указателей всех уровней.

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

Рисунок 6.3. Схематичное представление списка с пропусками

Поиск в списке с пропусками

Если еще раз внимательно посмотреть на рис. 6.3, можно обратить внимание, что полученный список можно охарактеризовать как несколько объединенных односвязных и двухсвязных списков. На уровне 0 находится двухсвязный список, далее, на уровне 1 - односвязный список, который соединяет каждый второй узел, после него на уровне 2 находится еще один односвязный список, который объединяет каждый четвертый узел и, наконец, на уровне 3 односвязный список соединяет каждый восьмой узел. Таким образом, чтобы, например, найти узел с именем g, нужно перейти по указателю уровня 2 от начального узла к узлу d, затем по указателю первого уровня до узла f и, наконец, по указателю уровня 0 до узла g. Следовательно, теоретически говоря, чтобы найти седьмой узел, нужно будет перейти всего по трем указателям.

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

1. Установить значение переменной LevelNumber равным самому высшему уровню указателей списка с пропусками (предполагается, что уровень списка указывается при его создании и выполнении операций вставки и удаления).

2. Установить переменную BeforeNode на начальный фиктивный узел.

3. Перейти по прямому указателю уровня LevelNumber от узла BeforeNode. Назвать узел, в который мы попали, NextNode.

4. Сравнить элемент в узле NextNode с искомым. Если NextNode является искомым узлом, поиск завершается.

5. Если элемент в узле NextNode меньше искомого, то искомый узел должен находиться после узла NextNode. Установить переменную BeforeNode на узел NextNode и перейти к шагу 3.

6. Если элемент в узле NextNode больше искомого, то искомый узел, если он присутствует в списке, должен находиться между узлами BeforeNode и NextNode. Уменьшаем значение переменной LevelNumber на единицу (другими словами, уменьшаем количество пропускаемых за один шаг узлов).

7. Если значение переменной LevelNumber равно 0 или больше, перейти к шагу 3. В противном случае искомый элемент в списке не найден, и если его необходимо вставить, то его позиция должна находиться между узлами BeforeNode и NextNode.

В соответствии с этим алгоритмом, при поиске узла g на рис. 6.3 мы начинаем с уровня 3 и начального узла. Переходим по указателю уровня 3 до узла h. Сравниваем h и g. Поскольку h больше g, уменьшаем уровень на единицу и начинаем сначала. По указателю второго уровня от начального узла переходим к узлу d. d меньше, чем g, следовательно, узел d становится новым начальным узлом. Снова переходим по указателю уровня 2 до узла h. Поскольку h больше, чем g, уменьшаем уровень на единицу. Переходим от узла d по указателю уровня 1 до узла f. Он меньше искомого, поэтому делаем его новым начальным узлом. Переходим по указателю уровня 1, и мы снова попадаем в узел h, который больше искомого. Снова понижаем уровень на единицу, переходим вперед по указателю уровня 0 и находим искомый узел g.

Таким образом, при поиске было пройдено шесть ссылок и выполнено шесть сравнений. Звучит не очень впечатляюще, особенно если учитывать, что в простом двухсвязном списке нам пришлось бы перейти по семи указателям и выполнить семь сравнений. Тем не менее, на рис. 6.3 принято допущение, что указатель уровня n+1 переходит на расстояние, в два раза превышающее расстояние перехода для указателя уровня n. Но обязательно ли соблюдать это условие? Почему в два раза, а не в три или пять? В списке с пропусками, который будет создан в этой главе, указатели первого уровня будут переходить через четыре узла, указатели второго уровня - через 16 узлов (т.е. 4 * 4), указатели третьего уровня - через 64 узла (т.е. 4(^3^)) и указатели уровня n - через 4(^n^) узлов.

Подобный выбор расстояний переходов объясняется необходимостью балансировки степени возникновения переходов на большие расстояния на высоких уровнях и скорости поиска на уровне 0 при подходе к искомому узлу. Множитель 4 является хорошим компромиссом.

Насколько большими в таком случае будут узлы? Если предположить, что элемент, хранящийся в списке с пропусками, представляет собой указатель (как это было в главе 3), тогда размер узлов на уровне 0 будет равен, по крайней мере, размеру трех указателей (один указатель на данные, один - прямой указатель и один - обратный). Размер узлов на уровне 1 будет составлять четыре указателя

(поскольку в узле будет находиться два прямых указателя). Для уровня 2 размер узлов будет составлять пять указателей и т.д. Таким образом, на уровне n размер узлов будет равен не менее n + 3 указателям. (Если предположить, что размер указателя равен 4 байта, то мы получим узлы 12, 16, 20 и 4n + 12 байт для узлов уровней 0, 1, 2 и n соответственно.) В действительности, для организации списка с пропусками требуется увеличить полученные размеры узлов, по крайней мере, на 1 байт, поскольку в каждом узле необходимо хранить уровень, к которому принадлежит данный узел.

Как вы уже знаете, узел уровня n содержит указатель на узел, находящийся впереди него на 4" узлов. Если n равно 16, то указатель уровня n позволяет перейти вперед примерно на 4 миллиарда узлов - абсолютно недостижимое количество. Так, например, в 32-разрядной операционной системе каждый процесс имеет доступ к 4 миллиардам байт, в которых никак не могут разместиться 4 миллиарда узлов разного размера. На практике количество узлов, как правило, не будет превышать одного миллиона, поэтому указателей уровня 11 окажется вполне достаточно (т.е. общее количество уровней составит 12). На высшем уровне переход будет осуществляться на 4 миллиона узлов вперед.

На основе всего вышесказанного можно легко разработать структуру узла списка с пропусками. Это будет структура переменой длины, что несколько усложняет выделение памяти под узлы и ее освобождение. Структура узла приведена в листинге 6.14.

Листинг 6.14. Структура узла списка с пропусками

const

tdcMaxSkipLevels = 12;

type

PskNode = ^TskNode;

TskNodeArray = array [0..pred(tdcMaxSkipLevels) ] of PskNode;

TskNode = packed record

sknData : pointer;