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

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

Листинг 6.12. Случайные числа с нормальным распределением

var

NRGNextNumber : double;

NRGNextlsSet : boolean;

function NormalRandomNumber(aPRNG : TtdBasePRNG;

aMean : double;

aStdDev : double): double;

var

Rl, R2 : double;

RadiusSqrd : double;

Factor : double;

begin

if NRGNextlsSet then begin

Result := NRGNextNumber;

NRGNextlsSet := false;

end

else begin

{получить два числа, которые определяют точку внутри окружности единичного радиуса}

repeat

Rl := (2.0 * aPRNG.AsDouble) -1.0;

R2 := (2.0 * aPRNG.AsDouble) - 1.0;

RadiusSqrd := sqr(Rl) + sqr(R2);

until (RadiusSqrd < 1.0) and (RadiusSqrd > 0.0);

{применить преобразование Бокса-Мюллера}

Factor := sqrt(-2.0 * In(RadiusSqrd) / RadiusSqrd);

Result := Rl * Factor;

NRGNextNumber :=R2 * Factor;

NRGNextlsSet :=true;

end;

Result := (Result * aStdDev) + aMean;

end;

Еще одним важным распределением является экспоненциальное. Случайные числа, распределенные по этому закону, используются для моделирования ситуаций "времени прибытия", например, времени прибытия покупателей к кассе в супермаркете. Если в среднем покупатели подходят к кассе каждые x секунд, то время прибытия будет распределено по экспоненциальному закону со средним значением х.

Генерировать случайные числа, распределенные по экспоненциальному закону, достаточно просто. Не вдаваясь в математические подробности можно сказать, что если u - случайное число, распределенное по равномерному закону в диапазоне от 0.0 до 1.0, то e, которое равно

e = -x ln(u)

будет случайном числом, распределенным по экспоненциальному закону со средним значением х.

Листинг 6.13. Случайные числа, распределенные по экспоненциальному закону

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. Схематичное представление списка с пропусками

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