Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Flag [trunc(RandGen.AsDouble * 10.0)] :=true;
end;
BucketNumber := -1;
for j := 0 to 9 do
if Flag[j] then
inc(BucketNumber);
inc(Bucket[BucketNumber]);
end;
{объединить две первые категории - это будет сумма категорий "все цифры одинаковы" и "две разные цифры"}
inc(Bucket[1], Bucket[0]);
Expected := (p[0]+p[1]) * NumFives;
ChiSqVal := Sqr(Expected - Bucket[1]) / Expected;
{обработать другие категории}
for i := 2 to 4 do
begin
Expected :=p[i] * NumFives;
ChiSqVal := ChiSqVal + (Sqr (Expected - Bucket [i]) / Expected);
end;
{вернуть значения}
ChiSquare := ChiSqVal;
DegsFreedom := 3;
end;
Тест "сбор
Четвертый тест, который мы будем проводить, называется "сбор купонов" (coupon collector's test). Случайные числа считываются по одному и преобразуются в "купоны" - числа от 0 до 4. Фиксируется длина последовательности до получения полного комплекта купонов (т.е. цифр от 0 до 4). Очевидно, что получаемые длины будут от пяти и выше. После набора полного комплекта сбор купонов начинается снова. Длины последовательностей разбиваются на категории, к которым затем применяется тест по критерию хи-квадрат. Как правило, используются категории для длин от 5 до 19 и еще одна дополнительная категория для больших длин. Таким образом, мы получаем 16 категорий, а, следовательно, 15 степеней свободы. Как и в тесте "покер", вычисление вероятностей для каждой из категорий включает сложные математические выкладки, которые в этой книге не приводятся. Соответствующие подробности можно найти в [11].
Листинг 6.8. Тест "сбор купонов"
procedure CouponCollectorsTest(RandGen : TtdBasePRNG;
var ChiSquare : double;
var DegsFreedom : integer);
var
NumSeqs, LenSeq, NumVals, NewVal, i : integer;
Expected, ChiSqVal : double;
Bucket : array [5..20] of integer;
Occurs : array [0..4] of boolean;
p : array [5..20] of double;
begin
{вычислить вероятности для каждой категории событий, алгоритм Кнута}
p[20] := 1.0;
for i := 5 to 19 do
begin
p[i] := (120.0 * Stirling(i-1, 4)) / IntPower(5.0, i);
p[20] := p[20] - p[i];
end;
NumSeqs := 0;
FillChar(Bucket, sizeof(Bucket), 0);
while (NumSeqs < CouponCount) do
begin
{продолжать сбор купонов (т.е. случайных чисел) до получения полного набора из пяти купонов}
LenSeq := 0;
NumVals := 0;
FillChar (Occurs, sizeof(Occurs), 0);
repeat
inc(LenSeq);
NewVal := trune(RandGen.AsDouble * 5);
if not Occurs [NewVal] then begin
Occurs[NewVal] := true;
inc(NumVals);
end;
until (NumVals = 5);
{обновить значение для соответствующей категории в зависимости от количества собранных купонов}
if (LenSeq > 20) then
LenSeq := 20;
inc(Bucket[LenSeq]);
inc (NumSeqs);
end;
{вычислить значение xu-квадрат}
ChiSqVal := 0.0;
for i := 5 to 20 do
begin
Expected := p [ i ] * NumSeqs;
ChiSqVal := ChiSqVal + (Sqr(Expected - Bucket [i]) / Expected);
end;
{вернуть значения}
ChiSquare := ChiSqVal;
DegsFreedom := 15;
end;
Результаты выполнения тестов
В разделе сопровождающих эту книгу материалов, который расположен на Web-сайте издательства, можно найти тестовую программу, которая применяет все рассмотренные нами тесты к стандартному генератору случайных чисел Delphi и минимальному стандартному генератору случайных чисел. На рис. 6.1 приведены результаты проведения одного из тестов для генератора случайных чисел Delphi.
Рисунок. 6.1.
Как видите, данный конкретный тест свидетельствует о том, что стандартный генератор Delphi успешно прошел проверку. (под успешным прохождением теста понимается, что предложенная к тестированию последовательность случайных чисел не дает результатов, которые являются значимыми на уровне 5%.)
Окно в правой части окна программы представляет собой снимок случайных чисел, полученных на выходе генератора. Координаты точек вычисляются на основе двух случайных чисел: первого для оси х, а второго - для оси Y. После этого точки выводятся в окне, если они находятся в прямоугольнике (0.0, 0.0, 0.001, 1.0) или, другими словами, в прямоугольнике, нижний левый угол которого расположен в точке (0.0, 0.0), а верхний правый - в точке (0.001, 1.0). Чтобы распределение точек было удобнее изучать, прямоугольник растянут по оси х. Как видите, на рисунке точки случайным образом разбросаны по всему прямоугольнику. Никакой системы при этом не наблюдается.
У вас может возникнуть удивление, зачем мы так много говорим об этом окне. Посмотрите на рис. 6.2, на котором показана та же программа, но для минимального стандартного генератора случайных чисел. Как видите, и этот генератор успешно прошел все тесты, но посмотрите на распределение случайных точек. Очевидно, что генератор дает последовательность случайных чисел, которые при переносе их на график формируют определенный регулярный рисунок.
Регулярность минимального стандартного генератора не позволяет использовать его для некоторых приложений, особенно тех, которые требуют пар случайных чисел. Даже незначительной регулярности бывает достаточно для того, чтобы приложение давало неверные результаты. Кроме того, отсутствие регулярности в результатах стандартного генератора случайных чисел Delphi в двухмерной плоскости не означает, что регулярности не будет в гиперплоскостях более высокой размерности. Существуют тесты, которые проверяют случайные числа на наличие регулярности в А> мерном пространстве, но давайте не будем погружаться в изучение слишком сложных тестов, а рассмотрим методы использования двух уже известных нам генераторов для дальнейшей рандомизации их выходных данных.
Рисунок 6.2. Тестирование минимального стандартного генератора
Мы рассмотрим три метода: первый известен как комбинаторный, второй - аддитивный и третий - метод тасования.
Комбинирование генераторов
Комбинирование генераторов заключается в параллельном использовании двух (или большего количества) мультипликативных линейных конгруэнтных генераторов с различными длинами циклов. Случайные числа генерируются обоими генераторами, а затем вычисляется их разность. Если получено отрицательное число, необходимо сделать его положительным, сложив его с длиной цикла первого генератора.
Листинг 6.9. Комбинирование генераторов type
TtdCombinedPRNG = class (TtdBasePRNG) private
FSeed1 : longint;
FSeed2 : longint;
protected
procedure cpSetSeed1(aValue : longint);
procedure cpSetSeed2(aValue : longint);
public
constructor Create(aSeed1, aSeed2 : longint);
function AsDouble : double; override;
property Seed1 : longint read FSeed1 write cpSetSeed1;
property Seed2 : longint read FSeed2 write cpSetSeed2;