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

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

на обложку

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

Шрифт:

Тестирование

В основе всех тестов будут лежать одни и те же принципы. Мы будем генерировать большое количество случайных чисел из диапазона от 0.0 (включительно) до 1.0 (исключительно). Получаемые в результате работы генераторов значения будут разбиваться на несколько категорий, будет подсчитываться количество значений в каждой категории, а затем вероятность попадания значения в каждую категорию. На основе результатов вычислений будет определяться значение функции хи-квадрат, на основе которого будет прогоняться тест по критерию хи-квадрат. При этом количество степеней свободы будет на единицу меньше, чем количество категорий значений. Это было всего лишь краткое введение, но через несколько минут

мы приступим к собственно тестированию.

Тест на однородность

Первый тест самый простой - проверка на однородность. О нем мы уже говорили. Фактически случайные числа будут проверяться на равномерность распределения по диапазону от 0.0 до 1.0. Разобьем весь диапазон на 100 поддиапазонов, сформируем набор из 1000000 случайных чисел и вычислим количество значений, попавших в каждый поддиапазон. В поддиапазоне 0 будут находиться значения от 0.00 до 0.01, в поддиапазоне 1 - значения от 0.01 до 0.02 и т.д. Вероятность попадания случайного числа в любой поддиапазон составляет 0.01. Для полученного распределения вычислим значение параметра хи-квадрат и сравним его с данными для стандартного распределения хи-квадрат, находящимися в строке, для 99 степеней свободы.

Листинг 6.5. Тест на однородность

procedure UnifomityTest(RandGen : TtdBasePRNG;

var ChiSquare : double; var DegsFreedo : integer);

var

BucketNumber, i : integer;

Expected, ChiSqVal : double;

Bucket : array [0..pred(Uniformitylntervals) ] of integer;

begin

{вычислить количество чисел в каждом поддиапазоне}

FillChar(Bucket, sizeof(Bucket), 0);

for i := 0 to pred(UniformityCount) do

begin

BucketNumber := trunc(RandGen.AsDouble * Uniformitylntervals);

inc (Bucket [BucketNumber]);

end;

{вычислить значение параметра xu-квадрат}

Expected := UniformityCount / Uniformitylntervals;

ChiSqVal := 0.0;

for i := 0 to pred(Uniformitylntervals) do

ChiSqVal := ChiSqVal + (Sqr (Expected - Bucket [i]) / Expected);

{вернуть значения}

ChiSquare := ChiSqVal;

DegsFreedom := pred(Uniformitylntervals);

end;

Тест на пропуски

Второй тест, который мы проведем, - тест на пропуски - несколько сложнее первого. Тест на пропуски гарантирует, что последовательность случайных чисел не будет попадать сначала в один поддиапазон, а затем в другой, третий и т.д., несмотря на то, что в целом значения будут распределены равномерно по всему диапазону. Определим в диапазоне поддиапазон, скажем, первую половину - от 0.0 до 0.5. Сформируем набор случайных чисел. Для каждого генерируемого числа будем проверять, попадает ли оно в выбранный поддиапазон (попадание) или нет (промах). В результате проверок будет получена последовательность попаданий и промахов. Найдите последовательности из одного и большего количества промахов (такие последовательности называются пропусками, отсюда и название теста - тест на пропуски). Вы получите последовательности из одного, двух и даже большего количества промахов. Разбейте длины пропусков на категории. Если известно, что вероятность попадания равна p (в нашем случае она будет равна длине выбранного поддиапазона), то вероятность промаха будет (1 -p). На основе этих данных можно определить вероятность возникновения пропуска из одного промаха — (1 -p)p, двух промахов — (1 -p)(^2^)p, n промахов - (1 -p)(^n^)p, а, следовательно, вычислить ожидаемое количество пропусков любой длины. После этого применим тест по критерию хи-квадрат. Будем использовать 10 категорий пропусков (поскольку вероятность возникновения пропусков длиной 11 и более промахов очень мала, все пропуски длиной 10 и более будут учитываться в последней категории;

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

Листинг 6.6. Тест на пропуски

procedure GapTest(RandGen : TtdBasePRNG;

Lower, Upper : double;

var ChiSquare : double;

var DegsFreedom : integer);

var

NumGaps : integer;

GapLen : integer;

i : integer;

p : double;

Expected : double;

ChiSqVal : double;

R : double;

Bucket : array [0..pred(GapBucketCount) ] of integer;

begin

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

FillChar(Bucket, sizeof(Bucket), 0);

GapLen := 0;

NumGaps := 0;

while (NumGaps < GapsCount) do

begin

R := RandGen.AsDouble;

if (Lower <= R) and (R < Upper) then begin

if (GapLen >= GapBucketCount) then

GapLen := pred(GapBucketCount);

inc(Bucket[GapLen]);

inc(NumGaps);

GapLen := 0;

end else

if (GapLen < GapBucketCount) then

inc(GapLen);

end;

p := Upper - Lower;

ChiSqVal := 0.0;

{обработать все категории, кроме последней}

for i := 0 to GapBucketCount-2 do

begin

Expected := p * IntPower(1-p, i) * NumGaps;

ChiSqVal := ChiSqVal + (Sqr (Expected - Bucket [i]) / Expected);

end;

{обработать последнюю категорию}

i := pred(GapBucketCount);

Expected IntPower (1-p, i) * NumGaps;

ChiSqVal := ChiSqVal + (Sqr (Expected - Bucket [i]) / Expected);

{вернуть значения}

ChiSquare := ChiSqVal;

DegsFreedom := pred(GapBucketCount);

end;

Тест "покер"

Третий тест известен под названием "покер" (poker test). Случайные числа группируются в наборы по пять, а затем преобразуются в "карты", которые представляют собой цифры от 0 до 9. После этого определяется количество разных карт в каждом наборе (оно будет равно от одного до пяти) и полученные результаты разбиваются на категории. Поскольку вероятность пятикратного повторения одной и той же карты достаточно низка, случай выпадения только одной карты, как правило, включается в категорию "две разные цифры". К полученным четырем категориям применятся тест по критерию хи-квадрат (три степени свободы). Вероятность возникновения события для каждой категории вычислить не так уж легко (к тому же математические выкладки основаны на использовании комбинаторных значений, называемых числами Стерлинга), поэтому вычисления в этой книге не приводятся. Если вам интересно, то подробное описание можно найти в [11].

Листинг 6.7. Тест "покер"

procedure PokerTest(RandGen : TtdBasePRNG;

var ChiSquare : double;

var DegsFreedom : integer);

var

i, j, jlBucketNumber, NumFives : integer;

Accum, Divisor, Expected, ChiSqVal : double;

Bucket : array [0..4] of integer;

Flag : array [0..9] of boolean;

p : array [0..4] of double;

begin

{подготовительные операции}