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

• Название: Фундаментальные алгоритмы и структуры данных в Delphi
• Автор: Джулиан Бакнелл
• Издательство: ДиаСофтЮП
• Жанр: Программирование
• Год: 2003
• ISBN: ISBN 5-93772-087-3

Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».

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

Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

---

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

Первый тест самый простой - проверка на однородность. О нем мы уже говорили. Фактически случайные числа будут проверяться на равномерность распределения по диапазону от 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

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

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

NumFives PokerCount div 5;

{вычислить вероятности для каждой категории событий, алгоритм Кнута}

Accum := 1.0;

Divisor := IntPower(10.0, 5);

for i := 0 to 4 do

begin

Accum := Accum * (10.0 - i);

p[i] := Accum * Stirling(5, succ(i)) / Divisor;

end;

{для каждой группы из пяти случайных чисел преобразовать все значения и числа от 1 до 10, определить количество разных цифр}

for i := 1 to NumFives do

begin

FillChar(Flag, sizeof(Flag), 0);

for j := 1 to 5 do begin

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.