21.6. Случайные числа
Довольно близкими к задачам сортировки и поиска являются задачи генерации случайных чисел. Зачастую случайные числа предназначены для нарушения упорядочивания списков и позволяют получить непредвиденные результаты. Они позволяют сжать много информации в одну страницу, выбирая содержимое случайным образом для каждого запроса. С ними можно столкнуться каждый день в Internet в виде цитат дня, баннерных объявлений и идентификаторов сеансов.
Случайные числа характеризуются двумя свойствами: они имеют равномерное распределение, и каждое следующее значение независимо от предыдущего. Равномерное распределение означает, что ни одно из значений не будет сгенерировано чаще любого другого значения.
Идея независимости заключается в том, что заданная последовательность чисел, возвращаемых генератором, такова, что следующее значение угадать невозможно. Конечно, алгоритм, который бы создавал действительно независимые значения, создать невозможно. Для этого в нашем распоряжении должна иметься некая формула, которая по своей природе является непредсказуемой. Однако нечто подобное этому можно создать, воспользовавшись генератором псевдослучайных чисел. Он использует достаточно простые математические выражения, которые возвращают почти случайные числа. Для него требуется ввод только некоего начального значения, и только для первого вызова. При всех остальных вызовах используется предыдущее значение. Нужно помнить, что одно и то же начальное значение начинает одну и ту же последовательность чисел. Один из способов сохранить уникальность последовательности - это задавать в качестве начального значения время в секундах.
Для генерирования случайных чисел стандартная библиотека языка C имеет функцию rand, а PHP работает с ней же с помощью своей одноименной функции. Передав ей верхний и нижний пределы, вы получаете целое число. Задать начальное значение можно с помощью специальной функции srand. Решение задачи генерации начального значения можно отдать на откуп операционной системы и получить начальное значение по текущему времени. К сожалению, стандартный генератор в различных операционных системах может работать неадекватно. К счастью, Педро Мело (Pedro Melo) добавил в PHP новый набор функций, в котором используется алгоритм Mersenne Twister. Не будем вдаваться в подробности алгоритма Mersenne Twister, так как это не затрагивает проблематику данной книги. Более детальную информацию об этом алгоритме можно получить на Web-странице, которая находится по адресу <http://www. math.keio.ac.jp/~matumoto/emt.html>. По мере необходимости вы сможете убедиться в точности этого алгоритма.
В листинге 21.8 содержится очень простой пример генерирования 100 случайных чисел, лежащих в диапазоне от 1 до 100, с помощью функции mt_rand. Затем он вычисляет среднее и медиану. Если распределение чисел является равномерным, среднее и медиана должны иметь очень близкие значения. Полученный набор в действительности очень мал, поэтому разные прогоны этого сценария дают достаточно большие флуктуации. Результат работы этого сценария представлен на рис. 21.5.

Листинг 21.8. Получение случайных чисел

<?php
// Задать начальное значение
mt_srand(doubleval(microtime()) * 100000000);
// Генерировать числа
print("<h3>Пример набора^!^^^'),-
$size = 100;
$total = 0;
for($i=0; $i < $size;
{
$n = mt_rand(1, $size); $sample[$i] = $n; $total += $n;
print("$n ");
}
print("<br>n");
print("Среднее: " . ($total/$size) . "<br>n"); sort($sample);
print("Медиана: " . ($sample[intval($size/2)]) . "<br>n");
?>
Сортировка, поиск и случайные числа