Справочник по Ada 2005
A.5.2 Генерация случайных чисел
Возможности для генерации псевдослучайных чисел с плавающей точкой предоставлены в пакете Numerics.Float_Random; обобщенный пакет Numerics.Discrete_Random предоставляет аналогичные возможности для генерации псевдослучайных целых чисел и псевдослучайных значений типов перечисления. Для краткости, псевдослучайные значения любого из этих типов называются случайными числами.
Некоторые из предоставленных возможностей являются базовыми для всех приложений, использующих случайные числа. К ним относятся ограниченный частный тип, каждый объект которого служит генератором (возможно, отличной) последовательности случайных чисел; функция для получения «следующего» случайного числа из заданной последовательности случайных чисел (то есть из ее генератора); и подпрограммы для инициализации или повторной инициализации заданного генератора до состояния, зависящего от времени, или состояния, обозначенного одним целым числом.
Другие возможности предоставляются специально для продвинутых приложений. К ним относятся подпрограммы для сохранения и восстановления состояния заданного генератора; частный тип, объекты которого могут использоваться для хранения сохраненного состояния генератора; и подпрограммы для получения строкового представления заданного состояния генератора или, задав такое строковое представление, соответствующего состояния.
Статическая семантика
Библиотечный пакет Numerics.Float_Random имеет следующее объявление:
package Ada.Numerics.Float_Random is
-- Основные возможности
type Generator is limited private;
subtype Uniformly_Distributed is Float range 0.0 .. 1.0;
function Random (Gen : Generator) return Uniformly_Distributed;
function Random (Gen : Generator) return Uniformly_Distributed;
procedure Reset (Gen : in Generator;
Initiator : in Integer);
procedure Reset (Gen : in Generator);
Initiator : in Integer);
procedure Reset (Gen : in Generator);
-- Продвинутые возможности
type State is private;
procedure Save (Gen : in Generator;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State);
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State);
Max_Image_Width : constant := определяемое реализацией целое значение;
function Image (Of_State : State) return String;
function Value (Coded_State : String) return State;
function Value (Coded_State : String) return State;
private
... -- не определено языком
end Ada.Numerics.Float_Random;
... -- не определено языком
end Ada.Numerics.Float_Random;
Тип Generator требует финализации (см. 7.6).
Обобщенный библиотечный пакет Numerics.Discrete_Random имеет следующее объявление:
generic
type Result_Subtype is (<>);
package Ada.Numerics.Discrete_Random is
-- Основные возможности
type Generator is limited private;
function Random (Gen : Generator) return Result_Subtype;
procedure Reset (Gen : in Generator;
Initiator : in Integer);
procedure Reset (Gen : in Generator);
Initiator : in Integer);
procedure Reset (Gen : in Generator);
-- Продвинутые возможности
type State is private;
procedure Save (Gen : in Generator;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State);
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State);
Max_Image_Width : constant := определяемое реализацией целое значение;
function Image (Of_State : State) return String;
function Value (Coded_State : String) return State;
function Value (Coded_State : String) return State;
private
... -- не определено языком
end Ada.Numerics.Discrete_Random;
... -- не определено языком
end Ada.Numerics.Discrete_Random;
Тип Generator требует финализации (см. 7.6) в каждой инстанциации Numerics.Discrete_Random.
Объект ограниченного частного типа Generator связан с последовательностью случайных чисел. Каждый генератор имеет скрытое (внутреннее) состояние, которое операции над генераторами используют для определения позиции в связанной последовательности. Все генераторы неявно инициализируются неопределенным состоянием, которое не меняется от одного выполнения программы к другому; их также можно явно инициализировать или повторно инициализировать в состояние, зависящее от времени, в ранее сохраненное состояние или в состояние, однозначно обозначенное целым значением.
Объект частного типа State может использоваться для хранения внутреннего состояния генератора. Такие объекты необходимы только в том случае, если приложение предназначено для сохранения и восстановления состояний генераторов или для их изучения или создания.
Операции над генераторами влияют на состояние и, следовательно, на будущие значения связанной последовательности. Семантика операций над генераторами и состояниями определена ниже.
function Random (Gen : Generator) return Uniformly_Distributed;
function Random (Gen : Generator) return Result_Subtype;
function Random (Gen : Generator) return Result_Subtype;
Получает «следующее» случайное число из заданного генератора относительно его текущего состояния в соответствии с определенным реализацией алгоритмом. Результат функции в Numerics.Float_Random предоставляется как значение подтипа Uniformly_Distributed, который является подтипом предопределенного типа Float с диапазоном от 0,0 до 1,0. Результат функции в инстанциации Numerics.Discrete_Random предоставляется как значение обобщенного формального подтипа Result_Subtype.
procedure Reset (Gen : in Generator;
Initiator : in Integer);
procedure Reset (Gen : in Generator);
Initiator : in Integer);
procedure Reset (Gen : in Generator);
Устанавливает состояние указанного генератора в состояние, которое является неопределенной функцией от значения параметра Initiator (или в состояние, зависящее от времени, если указан только параметр генератора). Последняя форма процедуры известна как процедура Reset, зависящая от времени.
procedure Save (Gen : in Generator;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State);
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State);
Save получает текущее состояние генератора. Reset присваивает генератору указанное состояние. Генератор, сброшенный в состояние, ранее полученное вызовом Save, восстанавливается в состояние, которое у него было во время вызова Save.
function Image (Of_State : State) return String;
function Value (Coded_State : String) return State;
function Value (Coded_State : String) return State;
Image предоставляет представление состояния, закодированного (определенным реализацией способом) как строка, длина которой ограничена значением Max_Image_Width. Value — обратная функция Image: Value(Image(S)) = S для каждого состояния S, которое может быть получено от генератора вызовом Save.
Динамическая семантика
Инстанцирование Numerics.Discrete_Random с подтипом, имеющим нулевой диапазон, вызывает исключение Constraint_Error.
Этот абзац был удален.
Ограниченные (временные) ошибки
Вызов Value со строкой, которая не является изображением состояния какого-либо генератора, является ограниченной ошибкой. Если ошибка обнаружена, возбуждается исключение Constraint_Error или Program_Error. В противном случае вызов Reset с полученным состоянием приведет к генератору, вызовы Random с этим генератором будут производить последовательность значений соответствующего подтипа, но которые могут не быть случайными по характеру. То есть, последовательность значений может не удовлетворять требованиям реализации в данном подразделе.
Требования к реализации
Достаточно длинная последовательность случайных чисел, полученная последовательными вызовами Random, примерно равномерно распределена в пределах диапазона подтипа результата.
Функция Random в инстанциации Numerics.Discrete_Random гарантированно возвращает каждое значение из своего подтипа результата за конечное число вызовов, при условии, что число таких значений не превышает 215.
Другие требования к производительности генератора случайных чисел, которые применяются только в реализациях, соответствующих приложению Numerics, и только в «строгом» режиме, определенном там (см. G.2), приведены в G.2.5.
Требования к документации
Ни один алгоритм генерации случайных чисел не является лучшим для всех приложений. Чтобы позволить пользователю определить пригодность генераторов случайных чисел для предполагаемого приложения, реализация должна описать используемый алгоритм и должна указать его период, если он известен точно, или нижнюю границу периода, если точный период неизвестен. Периоды, которые настолько велики, что периодичность не наблюдаема на практике, могут быть описаны такими терминами без указания числового ограничения.
Реализация также должна документировать минимальный интервал времени между вызовами процедуры Reset, зависящей от времени, которая гарантированно инициирует различные последовательности, и она должна документировать характер строк, которые Value будет принимать без возбуждения Constraint_Error.
Рекомендации по реализации
Любая память, связанная с объектом типа Generator, должна быть освобождена при выходе из области действия объекта.
Если период генератора достаточно велик по отношению к числу различных значений инициализатора, то каждое возможное значение инициализатора, переданное в Reset, должно инициировать последовательность случайных чисел, которая практически не перекрывается последовательностью, инициированной любым другим значением. Если это невозможно, то отображение между значениями инициализатора и состояниями генератора должно быть быстро меняющейся функцией от значения инициализатора.
ПРИМЕЧАНИЯ
14 Если два или более задач используют один и тот же генератор, то задачи должны синхронизировать свой доступ к генератору, как и к любой общей переменной (см. 9.10).
15 В рамках данной реализации повторяющуюся последовательность случайных чисел можно получить, полагаясь на неявную инициализацию генераторов или явно инициализируя генератор с повторяющимся значением инициализатора. Различные последовательности случайных чисел можно получить от данного генератора в разных выполнениях программы, явно инициализируя генератор в зависящем от времени состоянии.
16 Данная реализация функции Random в Numerics.Float_Random может или не может выдавать значения 0.0 или 1.0. Переносимые приложения должны предполагать, что эти значения или значения, достаточно близкие к ним, чтобы вести себя неотличимо от них, могут возникать. Если требуется последовательность случайных целых чисел из некоторого фиксированного диапазона, приложение должно использовать функцию Random в соответствующей реализации Numerics.Discrete_Random, а не преобразовывать результат функции Random в Numerics.Float_Random. Однако некоторые приложения со специфическими требованиями, такими как последовательность случайных целых чисел, каждый из которых выбирается из разного диапазона, могут найти более удобным преобразовать результат функции случайного числа с плавающей точкой. Для M ≥ 1, выражение
Integer(Float(M) * Random(G)) mod M
преобразует результат Random(G) в целое число, равномерно распределённое в диапазоне 0 .. M–1; оно является допустимым даже если Random возвращает 0.0 или 1.0. Каждое значение диапазона результата возможно, при условии, что M не слишком велико. Экспоненциально распределённые (с плавающей точкой) случайные числа со средним и стандартным отклонением 1.0 можно получить с помощью преобразования
-Log(Random(G) + Float'Model_Small)
где Log происходит из Numerics.Elementary_Functions (см. A.5.1); в этом выражении, добавление Float'Model_Small предотвращает исключение, которое было бы вызвано, если бы Log получил значение ноль, без влияния на результат (в большинстве реализаций), когда Random возвращает ненулевое значение.
Примеры
Пример программы, которая играет в симулированную игру в кости:
with Ada.Numerics.Discrete_Random;
procedure Dice_Game is
subtype Die is Integer range 1 .. 6;
subtype Dice is Integer range 2*Die'First .. 2*Die'Last;
package Random_Die is new Ada.Numerics.Discrete_Random (Die);
use Random_Die;
G : Generator;
D : Dice;
begin
Reset (G); -- Начальное состояние генератора в каждом запуске
loop
-- Бросаем пару костей; суммируем и обрабатываем результаты
D := Random(G) + Random(G);
...
end loop;
end Dice_Game;
procedure Dice_Game is
subtype Die is Integer range 1 .. 6;
subtype Dice is Integer range 2*Die'First .. 2*Die'Last;
package Random_Die is new Ada.Numerics.Discrete_Random (Die);
use Random_Die;
G : Generator;
D : Dice;
begin
Reset (G); -- Начальное состояние генератора в каждом запуске
loop
-- Бросаем пару костей; суммируем и обрабатываем результаты
D := Random(G) + Random(G);
...
end loop;
end Dice_Game;
Пример программы, которая моделирует подбрасывание монеты:
with Ada.Numerics.Discrete_Random;
procedure Flip_A_Coin is
type Coin is (Heads, Tails);
package Random_Coin is new Ada.Numerics.Discrete_Random (Coin);
use Random_Coin;
G : Generator;
begin
Reset (G); -- Начальное состояние генератора в каждом запуске
loop
-- Подбрасываем монету и обрабатываем результат
case Random(G) is
when Heads =>
...
when Tails =>
...
end case;
...
end loop;
end Flip_A_Coin;
procedure Flip_A_Coin is
type Coin is (Heads, Tails);
package Random_Coin is new Ada.Numerics.Discrete_Random (Coin);
use Random_Coin;
G : Generator;
begin
Reset (G); -- Начальное состояние генератора в каждом запуске
loop
-- Подбрасываем монету и обрабатываем результат
case Random(G) is
when Heads =>
...
when Tails =>
...
end case;
...
end loop;
end Flip_A_Coin;
Пример параллельной симуляции физической системы с отдельным генератором вероятностей событий в каждой задаче:
with Ada.Numerics.Float_Random;
procedure Parallel_Simulation is
use Ada.Numerics.Float_Random;
task type Worker is
entry Initialize_Generator (Initiator : in Integer);
...
end Worker;
W : array (1 .. 10) of Worker;
task body Worker is
G : Generator;
Probability_Of_Event : Uniformly_Distributed;
begin
accept Initialize_Generator (Initiator : in Integer) do
Reset (G, Initiator);
end Initialize_Generator;
loop
...
Probability_Of_Event := Random(G);
...
end loop;
end Worker;
begin
-- Инициализация генераторов в задачах Worker в различных состояниях
for I in W'Range loop
W(I).Initialize_Generator (I);
end loop;
... -- Ожидание завершения задач Worker
end Parallel_Simulation;
procedure Parallel_Simulation is
use Ada.Numerics.Float_Random;
task type Worker is
entry Initialize_Generator (Initiator : in Integer);
...
end Worker;
W : array (1 .. 10) of Worker;
task body Worker is
G : Generator;
Probability_Of_Event : Uniformly_Distributed;
begin
accept Initialize_Generator (Initiator : in Integer) do
Reset (G, Initiator);
end Initialize_Generator;
loop
...
Probability_Of_Event := Random(G);
...
end loop;
end Worker;
begin
-- Инициализация генераторов в задачах Worker в различных состояниях
for I in W'Range loop
W(I).Initialize_Generator (I);
end loop;
... -- Ожидание завершения задач Worker
end Parallel_Simulation;
ПРИМЕЧАНИЯ
17 Примечания к последнему примеру: Хотя каждая задача Worker инициализирует свой генератор в различном состоянии, эти состояния будут одинаковыми при каждом выполнении программы. Состояния генератора могут быть уникально инициализированы в каждом выполнении программы путём создания экземпляра Ada.Numerics.Discrete_Random для типа Integer в основной процедуре, сброса полученного от этого экземпляра генератора в зависящее от времени состояние, а затем использования случайных целых чисел, полученных от этого генератора, для инициализации генераторов в каждой задаче Worker.
