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

Бакнелл Джулиан М.

Длина массива, 55, и значения индексов, 54 и 23, - это не просто взятые наугад значения. Было показано, что они дают хорошие последовательности случайных чисел при генерации целых значений. (В книге [11] можно найти таблицы других удачных значений длины массива и индексов.)

Самым хорошим свойством данного генератора является длина цикла. Она просто огромна (при реализации на основе значений типа longint длина цикла будет составлять 230(255- 1), или приблизительно 3 * 1025). Даже если бы вы генерировали каждую секунду триллион случайных чисел, то для того, чтобы пройти весь цикл, потребовались бы годы.

Тасующие

генераторы

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

Как и для аддитивного генератора, на первом этапе создается массив случайных чисел с плавающей запятой. Количество элементов в массиве не имеет особого значения. Кнут (Knuth) предложил использовать длины порядка 100. В нашем примере будет использоваться массив из 97 элементов - простое число, близкое к 100 [11]. (Кстати, применение простого числа не обязательно, оно просто выбрано в качестве примера.) Заполним массив случайными числами, полученными с помощью минимального стандартного генератора случайных чисел. Введем новую вспомогательную переменную и установим ее значение равным следующему случайному числу в последовательности.

При необходимости генерации следующего случайного числа с помощью тасующего генератора, вспомогательная переменная используется для вычисления случайного числа из диапазона от 0 до 96. Устанавливаем значение вспомогательной переменной равным значению элемента с вычисленным индексом и заменяем элемент новым случайным числом, полученным от внутреннего генератора случайных чисел. В качестве результата тасующего генератора используется значение вспомогательной переменной.

Листинг 6.11. Тасующий генератор

type

TtdShuffleGenerator = class(TtdBasePRNG) private

FAux : double;

FPRNG : TtdMinStandardPRNG;

FTable : array [0..96] of double;

protected

procedure sgSetSeed(aValue : longint);

procedure sgInitTable;

public

constructor Create(aSeed : longint);

destructor Destroy; override;

function AsDouble : double; override;

property Seed : longint write sgSetSeed;

end;

constructor TtdShuffleGenerator.Create(aSeed : longint);

begin

inherited Create;

FPRNG := TtdMinStandardPRNG.Create(aSeed);

sgInitTable;

end;

destructor TtdShuffleGenerator.Destroy;

begin

FPRNG.Free;

inherited Destroy;

end;

function TtdShuffleGenerator.AsDouble : double;

var

Inx : integer;

begin

Inx := Trunc(FAux * 97.0);

Result := FTable[Inx];

FAux := Result;

FTable[Inx] := FPRNG.AsDouble;

end;

procedure TtdShuffleGenerator.sgSetSeed(aValue : longint);

begin

FPRNG.Seed := aValue;

sgInitTable;

end;

procedure TtdShuffleGenerator.sgInitTable;

var

i : integer;

begin

for i := 96 downto 0 do

FTable[i] := FPRNG.AsDouble;

FAux := FPRNG.AsDouble;

end;

Принимая во

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

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

Выводы по алгоритмам генерации случайных чисел

В предыдущем разделе были рассмотрены несколько достаточно простых генераторов случайных чисел. Наилучшие последовательности чисел позволяют получить два последних генератора, но, к сожалению, они выдвигают жесткие требования к памяти (так, например, последний алгоритм для хранения внутренней таблицы требует почти 800 байт). Самым плохим из рассмотренных был минимальный стандартный генератор, по крайней мере, что касается наличия регулярности в генерируемых им последовательностях случайных чисел, которую, как было показано, можно устранить с помощью алгоритма тасования. Если говорить о личных предпочтениях, то автору книги наиболее импонирует аддитивный генератор: он прост, использует только оператор сложения и генерирует хорошие последовательности статистически независимых случайных чисел. Единственным его недостатком является то, что при необходимости сохранения состояния генератора, нужно сохранять массив и два индекса, что, по сравнению с одним значением начального числа типа longint для минимального стандартного генератора, может показаться слишком огромным объемом данных.

Другие распределения случайных чисел

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

Вторым по значимости после равномерного является нормальное или гауссово распределение. Оно также известно под названием распределение колокообразной формы, поскольку все точки данных расположены симметрично относительно среднего значения, причем, чем дальше точка от среднего значения, тем меньше вероятность ее получения. Нормальное распределение играет очень важную роль в статистике, где оно используется практически повсеместно. Например, рост людей 42-летнего возраста распределен в соответствии с нормальным распределением. Если попросить измерить длину стола нескольких человек с помощью линейки, длина которой намного короче, чем длина стола (другими словами, в случае существования элемента ошибки), полученный ответ будет соответствовать закону нормального распределения. И подобных примеров можно привести очень много.