Фундаментальные алгоритмы и структуры данных в 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, поскольку от него будет браться натуральный логарифм.
Списки с пропусками
После подробного описания нескольких генераторов случайных чисел, давайте рассмотрим структуру данных, которая для обеспечения высоких вероятностных характеристик быстродействия использует случайные числа.
Код класса для списков с пропусками
Помните, в главе 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 равным самому высшему уровню указателей списка с пропусками (предполагается, что уровень списка указывается при его создании и выполнении операций вставки и удаления).