Функція Random C++

37 0 Новини високих технологій

У розпал створення STL і бурхливої війни за стандарт мови C++ ряд програмістів розробили власну кроссплатформенную бібліотеку класів, що забезпечують розробників інструментами для вирішення повсякденних завдань, таких як обробка даних, алгоритми, робота з файлами і т. д. Ця бібліотека називається Boost. Проект настільки успішний, що можливості Boost запозичуються і вписуються в стандарт мови, починаючи з C++11. Одним з таких додатків є вдосконалена робота з випадковими числами.


Функція Random C++
Функції rand() і srand() відносяться до шкільного рівня і придатні для написання простих програм. Мінусом цих функцій є генерація недостатньо хорошою послідовності псевдовипадкових чисел (зображення вище). Також можливостей простих функцій не вистачає при розробці складних проектів. Для вирішення виниклої задачі були придумані генератори випадкових чисел (далі ГВЧ). З їх появою значно покращилася робота з генерації багатьох типів даних як псевдо-, так і істинно випадкових. Прикладом генерації істинно випадкових чисел є шум на зображенні нижче.
Функція Random C++

Генератор псевдовипадкових чисел

Функція Random C++
Традиційний алгоритм створення СЧ поєднував у собі одночасно алгоритм створення непередбачуваних бітів і перетворення їх у послідовність чисел. В бібліотеці random C++, яка є частиною Boost, розділили ці два механізми. Тепер генерація випадкових чисел і створення з них розподілу (послідовності) відбувається окремо. Використання розподілу є абсолютно логічним. Тому що випадкове число без певного контексту не має сенсу і його складно використовувати. Напишемо просту функцію, яка кидає кістку:




#include
int roll_a_dice() {
std::default_random_engine e{}; //створення генератора випадковості
std::uniform_int_distribution 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 ініціалізації еквівалентні. І здебільшого мають відношення до смаку або до стандартів написання гарного коду. А ось наступна ініціалізація докорінно відрізняється.


<script type="text/javascript">
var blockSettings2 = {blockId:"R-A-70350-2",renderTo:"yandex_rtb_R-A-70350-2",async:!0};

if(document.cookie.indexOf("abmatch=") >= 0){
blockSettings2 = {blockId:"R-A-70350-2",renderTo:"yandex_rtb_R-A-70350-2",statId:70350async:!0};
}

!function(a,b,c,d,e){a[c]=a[c]||[],a[c].push(function(){Ya.Context.AdvManager.render(blockSettings2)}),e=b.getElementsByTagName("script")[0],d=b.createElement("script"),d.type="text/javascript",d.src="//an.yandex.ru/system/context.js",d.async=!0e.parentNode.insertBefore(d,e)}(this,this.document,"yandexContextAsyncCallbacks");
  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 C++

Всі генератори псевдовипадкових чисел є детермінованими. Тобто мають визначення. Або іншими словами, отримання випадкових чисел базується на математичних алгоритмах. Random_device ж є недетерминированным. Він створює числа на основі стохастичних (випадкових з ін-грец.) процесів. Такими процесами можуть бути зміни фази або амплітуди коливань струму, коливання молекулярних решіток, руху повітряних мас в атмосфері і т. д.


<script type="text/javascript">
var blockSettings3 = {blockId:"R-A-70350-3",renderTo:"yandex_rtb_R-A-70350-3",async:!0};

if(document.cookie.indexOf("abmatch=") >= 0){
blockSettings3 = {blockId:"R-A-70350-3",renderTo:"yandex_rtb_R-A-70350-3",statId:70350async:!0};
}

!function(a,b,c,d,e){a[c]=a[c]||[],a[c].push(function(){Ya.Context.AdvManager.render(blockSettings3)}),e=b.getElementsByTagName("script")[0],d=b.createElement("script"),d.type="text/javascript",d.src="//an.yandex.ru/system/context.js",d.async=!0e.parentNode.insertBefore(d,e)}(this,this.document,"yandexContextAsyncCallbacks");

Очевидно, що не у кожного комп'ютера і не в кожній системі може бути вбудована можливість отримати випадкове число на основі стохастичного процесу. Тому вдаватися до використання 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);
  • біноміальний (біном) і т. д.

Розглянемо генератори стандартної бібліотеки C++.

  1. Новачкам досить використовувати default_random_engine, залишивши вибір генератора бібліотеці. Обраний буде генератор на основі поєднання таких факторів, як продуктивність, розмір, якість випадковості.
  2. Для досвідчених користувачів бібліотека надає 9 заздалегідь налаштованих генераторів. Вони сильно відрізняються один від одного продуктивністю і розмірами, але в той же час їх якість роботи було піддано серйозних тестів. Часто використовується генератор під назвою Mersenne twister engines і його примірники mt19937 (створення 32-бітних чисел) і mt19937_64 (створення 64-бітних чисел). Генератор являє собою оптимальне поєднання швидкості роботи і ступеня випадковості. Для більшості виникаючих завдань його буде достатньо.
  3. Для експертів бібліотека надає собою конфігуровані шаблони генераторів, що дозволяють створювати додаткові види генераторів.
Функція Random C++

Розглянемо ключові аспекти розподілів. У стандарті мови їх налічується 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. Так само як і з ГВЧ, користувач бібліотеки може створювати власні розподілу і використовувати з вбудованими генераторами або з генераторами, які створить.

Функція Random C++

На цьому можливості бібліотеки не обмежуються. Вони значно ширше. Але наданої інформації достатньо для використання і базового розуміння генератора випадкових чисел в C++.

Коротка довідка: Random в стилі .Net

В .Net framework також присутній клас Random для створення псевдовипадкових чисел. Розглянемо приклад генерації Random number С++/CLI.

Для тих, хто працює в Visual Studio та ніяк не може зрозуміти, чому простір імен System не визначено.

Щоб працювати .net необхідно підключення CLR. Робиться це двома способами.1) Створення проекту не windows console application, а з підтримкою CLR - Console application CLR (Консольний додаток CLR).2) Підключити підтримку CLR у налаштуваннях вже створеного проекту: властивості проекту(вкладка "проект", а не "сервіс") -> конфігурація -> загальні -> значення за замовчуванням -> у випадаючому списку пункту "підтримка загальномовне середовище виконання(CLR)" вибрати "Підтримка CLR-середовища (/clr)".

  #include "stdafx.h" 
#include

//using namespace System;

int main(array ^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(5001000) "n"; //при кожному запуску програми буде створюватися одне і те ж число.

std::cout std::endl;

return 0;
}

У даному випадку вся робота відбувається завдяки функції Random Next C++/CLI.

Варто особливо відзначити, що .net є великою бібліотекою з великими можливостями і використовує свою версію мови, звану C++/CLI від Common Language Infrastructure. Загалом, це розширення C++ під платформу .Net.

Розглянемо наприкінці кілька прикладів, щоб краще зрозуміти роботу з випадковими числами.

  #include  
#include
#include
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 uid1(510), uid2(1 6);
std::cout uid1(e2) ", " uid2(e3) std::endl;

std::default_random_engine e4{};
std::uniform_real_distribution urd(051.2);
std::normal_distribution nd(502.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 слід відмовлятися на користь нових методів, оскільки вони відповідають сучасним парадигм програмування, а старі методи будуть виводитися з стандарту.