В разгар создания STL и бурной войны за стандарт языка C++ ряд программистов разработали собственную кроссплатформенную библиотеку классов, обеспечивающих разработчиков инструментами для решения повседневных задач, таких как обработка данных, алгоритмы, работа с файлами и т. д. Эта библиотека называется Boost. Проект настолько успешен, что возможности Boost заимствуются и вписываются в стандарт языка, начиная с C++11. Одним из таких дополнений является усовершенствованная работа со случайными числами.
Функции rand() и srand() относятся к школьному уровню и пригодны для написания простых программ. Минусом этих функций является генерация недостаточно хорошей последовательности псевдослучайных чисел (картинка выше). Также возможностей простых функций не хватает при разработке сложных проектов.
Для решения возникшей задачи были придуманы генераторы случайных чисел (далее ГСЧ). С их появлением значительно улучшилась работа по генерации многих типов данных как псевдо-, так и истинно случайных. Примером генерации истинно случайных чисел является шум на картинке ниже.
Генератор псевдослучайных чисел
Традиционный алгоритм создания СЧ совмещал в себе одновременно алгоритм создания непредсказуемых битов и превращение их в последовательность чисел. В библиотеке random C++, являющаяся частью Boost, разделили эти два механизма. Теперь генерация случайных чисел и создание из них распределения (последовательности) происходит отдельно. Использование распределения является совершенно логичным. Потому что случайное число без определенного контекста не имеет смысла и его сложно использовать. Напишем простую функцию, которая бросает кость:
#include <random>
int roll_a_dice() {
std::default_random_engine e{}; //создание генератора случайности
std::uniform_int_distribution<int> d{1, 6} //создание распределения с мин и макс значениями
return d(e);
}
Типичной ошибкой тех, кто изучает random, является игнорирование создания распределения и переход сразу к созданию случайных чисел способом, к которому они привыкли. Например, рассмотрим вышеописанную функцию.
return 1 + e() % 6;Некоторые считают такое ее использование допустимым. Ведь C++ позволяет так работать. Однако создателями библиотеки Boost и стандартов C++11 строго рекомендуется так не делать. В лучшем случае это окажется просто плохой на вид код, а в худшем – это будет работающий код, совершающий ошибки, которые очень сложно поймать. Использование распределений гарантирует, что программист получит то, что ожидает.
Инициализация генератора и seed
Этап объявления, определения и создания сущностей зачастую рассматривается как нечто, не стоящее особого внимания. Но недостаточно вдумчивая инициализация генератора случайных чисел может сказаться на его надлежащей работе.
std::default_random_engine e1; //неявная инициализация значением по умолчанию
std::default_random_engine e2{}; //явная инициализация значением по умолчаниюПервые 2 инициализации эквивалентны. И по большей части имеют отношение к вкусу или к стандартам написания красивого кода. А вот следующая инициализация в корне отличается.
std::default_random_engine e3{31255}; //инициализация значением 31255«31255» - это называется seed (семя, первоисточник) - число, на основе которого генератор создает случайные числа. Ключевым моментом здесь является то, что при такой инициализации тип seed должен быть таким же или приводимым к типу, с которым работает генератор. Этот тип доступен через конструкцию decltype(e()), или result_of, или typename.
Почему генератор создает одинаковые последовательности?
Когда программа запускается несколько раз, генератор всегда создает одну и ту же последовательность чисел, если его инициализация не меняется, то есть определение генератора происходит одинаковым образом от запуска к запуску программы. С одной стороны, такое самовоспроизведение чисел генератором полезно, например, при отладке. А с другой – является нежелательным и может создавать проблемы.
Соответственно, чтобы избежать повторения последовательности чисел, генератор должен инициализироваться разными значениями при каждом запуске программы. Как раз для этих целей можно использовать seed. Стандартным способом инициализации ГПСЧ является передача ему в качестве seed значения time(0) из заголовочного файла ctime. То есть генератор будет инициализироваться значением, равным количеству секунд, прошедших с момента 1 января 00 часов 00 минут 00 секунд, 1970 года по UTC.
Инициализация ГПСЧ другим генератором
Инициализации временем может быть недостаточно для решения ряда задач. Тогда можно определить ГПСЧ через другой генератор. Здесь хотелось бы сделать отступление и поговорить об одном мощном инструменте, позволяющем создавать по-настоящему случайные числа.
Random_device – генератор истинно случайных чисел
Все генераторы псевдослучайных чисел являются детерминированными. То есть имеют определение. Или другими словами, получение случайных чисел основано на математических алгоритмах. Random_device же является недетерминированным. Он создает числа на основе стохастических (случайных с др.-греч.) процессов. Такими процессами могут быть изменения фазы или амплитуды колебаний тока, колебания молекулярных решеток, движения воздушных масс в атмосфере и т.д.
Очевидно, что не у каждого компьютера и не в каждой системе может быть встроена возможность получить случайное число на основе стохастического процесса. Поэтому прибегать к использованию random_device стоит только в случае необходимости. Его работа может отличаться от системы к системе, от компьютера к компьютеру, а может и вовсе быть недоступной. Поэтому при использовании генератора истинно случайных чисел нужно обязательно предусмотреть обработку ошибок.
Использование random_device в качестве seed для ГПСЧ
std::random_device rd{};
std::default_random_engine e{ rd() };
Ничего принципиально нового в этом коде нет. При этом с каждым запуском ГПСЧ инициализируется случайными значениями, которые создает генератор истинно случайных чисел rd.
Стоит также отметить, что значение инициализации генератора может быть сброшено в любой момент:
e.seed(15027); // инициализация числом
e.seed(); //инициализация значением по умолчанию
e.seed( rd() ); //инициализация другим генератором
Обобщим: генераторы и распределения
Генератор (engine) – это объект, который позволяет создавать разные равновероятные числа.
Распределение (distirbution) – это объект, который преобразует последовательность чисел, созданных генератором, в распределения по определенному закону, например:
- равномерное (uniform);
- нормальное - гауссово (normal);
- биномиальное (binomial) и т. д.
Рассмотрим генераторы стандартной библиотеки C++.
- Новичкам достаточно использовать default_random_engine, оставив выбор генератора библиотеке. Выбран будет генератор на основе сочетания таких факторов, как производительность, размер, качество случайности.
- Для опытных пользователей библиотека предоставляет 9 заранее настроенных генераторов. Они сильно отличаются друг от друга производительностью и размерами, но в то же время их качество работы было подвержено серьезным тестам. Часто используется генератор под названием Mersenne twister engines и его экземпляры mt19937 (создание 32-битных чисел) и mt19937_64 (создание 64-битных чисел). Генератор представляет собой оптимальное сочетание скорости работы и степени случайности. Для большинства возникающих задач его будет достаточно.
- Для экспертов библиотека предоставляет собой конфигурируемые шаблоны генераторов, позволяющие создавать дополнительные виды генераторов.
Рассмотрим ключевые аспекты распределений. В стандарте языка их насчитывается 20 штук. В примере выше использовалось равномерное распределение библиотеки random C++ в диапазоне [a, b] для целых чисел - uniform_int_distribution. Такое же распределение можно использовать для действительных чисел: uniform_real_distribution с такими же параметрами a и b промежутка генерации чисел. При этом границы промежутка включены, то есть [a, b]. Перечислять все 20 распределений и повторять документацию C++ в статье смысла не имеет.
Следует отметить, что каждому распределению соответствует свой набор параметров. Для равномерного распределения это промежуток от a до b. А для геометрического (geometric_distribution) параметром является вероятность успеха p.
Большая часть распределений определена как шаблон класса, для которого параметром служит тип значений последовательности. Однако некоторые распределения создают последовательности только значения int или только значения real. Или, например, последовательность Бернулли (bernoulli_distribution) предоставляющая значения типа bool. Так же как и с ГСЧ, пользователь библиотеки может создавать собственные распределения и использовать с встроенными генераторами или с генераторами, которые создаст.
На этом возможности библиотеки не ограничиваются. Они значительно шире. Но предоставленной информации достаточно для использования и базового понимания генератора случайных чисел в C++.
Краткая справка: Random в стиле .Net
В .Net framework также присутствует класс Random для создания псевдослучайных чисел. Рассмотрим пример генерации Random number С++/CLI.
Для тех, кто работает в Visual Studio и никак не может понять, почему пространство имен System не определено.
Чтобы работать с .net необходимо подключение CLR. Делается это двумя способами.1) Создание проекта не windows console app, а с поддержкой CLR - Console application CLR (Консольное приложение CLR).2) Подключить поддержку CLR в настройках уже созданного проекта: свойства проекта(вкладка "проект", а не "сервис") -> конфигурация -> общее -> значения по умолчанию -> в выпадающем списке пункта "поддержка общеязыковой среды выполнения(CLR)" выбрать "Поддержка CLR-среды (/clr)".
#include "stdafx.h"
#include <iostream>
//using namespace System;
int main(array<System::String ^> ^args)
{
System::Random ^rnd1 = gcnew System::Random(); //создание ГСЧ, по умолчанию инициализируется текущем временем
std::cout << rnd1->Next() << "\n"; //возвращает положительное целое число
int upper = 50;
std::cout << rnd1->Next(upper) << "\n"; //возвращает положительное целое число не большее upper
int a = -1000; int b = -500;
std::cout << rnd1->Next(a, b) << "\n"; //возвращает целое число в диапазоне [a, b]
int seed = 13977;
System::Random ^rnd2 = gcnew System::Random(seed); //инициализировать ГСЧ числом seed
std::cout << rnd2->Next(500, 1000) << "\n"; //при каждом запуске программы будет создаваться одно и то же число.
std::cout << std::endl;
return 0;
}
В данном случае вся работа происходит благодаря функции Random Next C++/CLI.
Стоит особо отметить, что .net является большой библиотекой с обширными возможностями и использует свою версию языка, называемую C++/CLI от Common Language Infrastructure. В общем, это расширение C++ под платформу .Net.
Рассмотрим в конце несколько примеров, чтобы лучше понять работу со случайными числами.
#include <iostream>
#include <random>
#include <ctime>
int main() {
std::mt19937 e1;
e1.seed(time(0));
std::cout << e1() << std::endl;
std::mt19937 e2(time(0));
std::mt19937 e3{};
std::uniform_int_distribution<int> uid1(5, 10), uid2(1, 6);
std::cout << uid1(e2) << ", " << uid2(e3) << std::endl;
std::default_random_engine e4{};
std::uniform_real_distribution<double> urd(0.5, 1.2);
std::normal_distribution<double> nd(5.0, 2.0); //нормальное распределение со средним значение 5.0 и среднеквадратичным отклонением 2.0
std::cout << urd(e4) << ", " << nd(e4) << std::endl;
std::cout << std::endl;
system("pause");
return 0;
}Заключение
Любые технологии и методы постоянно развиваются и совершенствуются. Так случилось и с механизмом генерации случайных чисел rand(), который устарел и перестал удовлетворять современным требованиям. В STL существует библиотека random, в .Net Framework - класс Random для работы со случайными числами. От использования rand следует отказываться в пользу новых методов, т. к. они соответствуют современным парадигмам программирования, а старые методы будут выводиться из стандарта.
Но откуда у этого генератора эти данные?
Если данные были изначально загружены, то этот ГСН совсем не истинный, а генератор псевдослучайных чисел.