Топ контрибуторов
loading
loading
Знаете ли Вы, что

Вы можете подписаться на RSS ленту новых тестов сервиса Quizful, в том числе и отдельно по каждой категории

Лента обновлений
ссылка 12:40:06
Добавлен вопрос в тест ASP.NET - Средний уровень
ссылка Nov 19 20:18
Комментарий от newlist1999:
Хороший тест для проверки знаний, хотя довольно слож...
ссылка Nov 19 15:50
Комментарий от ceferovshen:
SELECT Top 1 ID,DateTime FROM Table1
order by ID de...
ссылка Nov 18 17:27
Комментарий от ardnya:
Можно с вами пообщаться в лс?
ссылка Nov 18 14:51
Комментарий от aaa211:
Суффиксный декремент/инкремент имеет более высокий приори...
Статистика

Тестов: 153, вопросов: 8596. Пройдено: 445727 / 2188071.

Новые генераторы случайных чисел(ГСЧ) из С++11

head tail Статья
категория
C++
дата12.04.2013
авторmrgluck
голосов13
srand наше все - Программист С

Вступление

Но мы ведь пишем на плюсах. В 11 стандарте С++ для программистов предоставляются обширные возможности для создания ГЧ и их использования. Надо отметить, что ничего нового не придумали, а добавили классы из библиотеки boost (boost/random). Так что для тех, кто не может пользоваться свежим компилятором, всегда есть вариант с использованием данной библиотеки.

В связи с чем возникла потребность новых ГСЧ? Если вы пишите проекты чуть более сложные, чем Hello World, то "случайности" ГСЧ (а правильнее ГПСЧ) srand вам попросту не хватит, несложно будет вычислить порядок следования последовательности, и вызов будет происходить в одно и то же время, давая одинаковый результат. Также, само по себе использование srand неудобно, все хорошо лишь при диапазоне от 0 до n, вдобавок n ограничен потолком short int на некоторых системах. А если надо брать нижнюю границу, отличную от 0, то появляются лишние числа, вычисления, влекущие ошибки, связанные с неверным подсчетом. Еще хуже дело обстоит с генерацией СЧ в виде числа с плавающей точкой. И рассмотренные ниже классы помогут нам в этом нелегком пути. Пусть вас не пугают длинные непривычные названия, попробовав новый функционал, вы будете даже простые задачки решать с его помощью.


Знакомство с новым ГПСЧ

Мы будем использовать генератор mersenne twister, а точнее mt19937. Основанный на свойствах простых чисел, он подходит для решения большинства задач. Несмотря на то, что степень его "случайности" весьма неплоха, он все-таки является ГПСЧ. Генерирует СЧ он достаточно быстро и хватить его должно с головой.

Определен он, как и все, что мы далее будем рассматривать, в хедере random и пространстве имен std. Является 32-битным генератором, имеет собрата mt19937_64, являющегося 64-битным.
В конструкторе может инициализироваться величиной, от которой начинается генерация последовательности, либо специальным объектом seed_seq, являющимся зерном последовательности. Мы будем использовать первый вариант.

Пример: создание переменных std::mt19937

#include <random>  
#include <ctime>
  
 
int main() 

    std::mt19937 gen1, gen2(time(0));


В первом случае мы просто создаем объект, во втором, инициализируем его начальным значением. Пока все похоже на srand.
Класс имеет метод seed(), с помощью которого можно назначить зерно последовательности.

Пример: использование метода seed

#include <random>  
#include <ctime>
  

int main() 

    std::mt19937 gen; 
    gen.seed(time(0));
}


Здесь мы сначала создаем ГПСЧ, а потом задаем зерно (стартовое значение) его последовательности.

По вызову operator(), генератор производит число. Все как и с rand(), только теперь этим занимается один класс. Может иметь в качестве параметра распределение (переменная, отвечающая за диапазон значений). Очень удобно использовать даже один генератор и несколько разных распределений. О них мы поговорим далее, но сначала пример.

Пример: генерация СЧ и вывод на экран

#include <iostream>  
#include
<random> 
#include
<ctime>

int main() 

    std::mt19937 gen; 
    gen.seed(time(0)); // try to comment this string 
    std::cout << "My number: " << gen() << std::endl; 
}


Я специально записал "сидирование" в отдельную строку. Попробуйте закомментировать её и убедитесь, что будет показывать одно и то же число.

 

Распределения

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

Все они принимают в качестве аргументов в конструкторе либо параметры другого распределения, либо переменные, отвечающие за диапазон значений. Если оные не указаны, то используется диапазон от 0 до максимального значения, определенного в numeric_limits<>::max() данного идентификатора типа, являющегося параметром шаблона.

Если указан лишь один аргумент, то берется диапазон значений от данного до максимального. Следует отметить, что границы также учитываются, т.е. при указании в качестве аргументов a, b используется диапазон [a, b].

Каждое распределение имеет след. методы и функции для работы с ними:
1) перегруженный конструктор, описанный выше
2) reset, отвечающее за сброс последовательности распределения
3) оператор (), про него подробнее расскажу ниже
4) деструктор
5) param, возвращающий параметры данного распределения. Используется для передачи параметров одного распределения другому.
6) max, возвращающий максимально возможное значение, возвращаемое оператором ()
7) min, возвращающий минимально возможное значение, возвращаемое оператором ()
8) a, возвращающий верхнюю границу параметра распределения
9) b, возвращающий нижнюю границу параметра распределения
10) также имеет перегруженные версии операторов << и >>

Оператор () принимает в качестве параметра генератор и возвращает число из диапазона распределения. При этом на одно и то же распределение можно применять совершенно различные генераторы, отвечают они лишь за диапазон.

Все это мб сейчас для вас лишь непонятная скучная теория, но я постараюсь разбавить её примерами, на основе следующего распределения.

 

std::uniform_int_distribution

Применяется для указания диапазона целых чисел. Лучше всего подходит для int, unsigned int, long, unsigned long, long long, unsigned long long. Является шаблонным классом, по умолчанию использует int.

А теперь давайте по пунктам разберем методы.

Пример: создание ГПСЧ с разбросом от 0 до 50 и вывод на экран двух СЧ

#include <iostream>  
#include
<random> 
#include
<ctime>

int main() 

    std::mt19937 gen(time(0)); 
    std::uniform_int_distribution<> uid(050); 
    std::cout << "My numbers: " << uid(gen) << " " << uid(gen) << std::endl; 


В этом примере используется перегруженная версия конструктора, принимающая два аргумента. Как видите, оператор() принимает в качестве параметра ГПСЧ и возвращает СЧ из данного диапазона.

Давайте теперь создадим распределение на основе данного и посмотрим их характеристики (мин. и макс. значения диапазона). Заодно научимся использовать методы max() и min().


Пример: передача параметров одного распределения в качестве аргументов другого

#include <iostream>  
#include
<random> 
#include
<ctime>

int main() 
{
 
    std::mt19937 gen(time(0)); 
    std::uniform_int_distribution<int> uid1(0, 50), uid2(uid1.param()); 
    std::cout << "uid1 max: " << uid1.max() << std::endl 
              << "uid1 min: " << uid1.min() << std::endl 
              << "uid2 max: " << uid2.max() << std::endl 
              << "uid2 min: " << uid2.min() << std::endl; 
    // uid1.max() = 20; 
}
 


Как видите, один ГПСЧ инициализируется параметрами другого, и их характеристики эквиваленты. Следует отметить, что методы min() и max() возвращают переменную по значению, а не по ссылке, поэтому если мы раскомментируем строчку вконце, то получим ошибку компиляции.

А для чего же тогда нужны методы a() и b()?
Они возвращают параметры распределения. a() вернет нижнюю границу, b() верхнюю. На самом деле, их можно использовать заместо методов min() и max(), обратное неверно. Но я бы рекомендовал все же отталкиваться от ситуации, а именно, использовать a() и b() лишь в качестве аргументов при передаче параметра распределения и max() и min() во всех остальных случаях, дабы не ломать себе, а еще хуже кому-нибудь, потом голову, а что же это за методы такие.

Пример: передача нижней границы одного распределения в качестве аргумента другого распределения

#include <iostream>  
#include
<random> 
#include
<ctime>

int main() 

    std::mt19937 gen(time(0)); 
    std::uniform_int_distribution<int> uid1(050), uid2(20, uid1.param().b()); 
    std::cout << "uid1 max: " << uid1.max() << std::endl 
              << "uid1 min: " << uid1.min() << std::endl 
              << "uid2 max: " << uid2.max() << std::endl 
              << "uid2 min: " << uid2.min() << std::endl; 
    // uid1.max() = 20; 


Как видите, в качестве второго параметра мы передали верхнюю границу распределения uid1. Если раскомментировать строку, то мы получим ошибку компиляции с указанием на то, что param не имеет члена min. a() и b() также возвращают результат по значению, а не по ссылке, т.о. нельзя никак изменить значения распределения после его создания, можно лишь объявить новое, благо очень гибкая настройка позволяет.

Но и это еще не все. Благодаря перегруженным версиям операторов << и >> мы можем вывести границы распределения и задать их прямо в output/с input потока.

Пример: задание параметров распределения с потока std::cin и вывод на экран

#include <iostream>  
#include
<random> 

int main() 

    std::uniform_int_distribution<int> uid; 
    std::cin >> uid; 
    std::cout << uid; 


Сначала идет нижняя граница, потом верхняя. Сразу видна забота о программистах :)

Осталось лишь упомянуть о методе reset. Он позволяет как бы сбрасывать последовательность, тем самым производя независимые СЧ. Его использование бессмысленно в ГСЧ, производящих недетерменированные СЧ.

Можно еще сказать, что у распределений имеются два перегруженных оператора для сравнения == и !=, которые сравнивают две переменные.

Если кто-то еще не понял, как работают распределения и каков принцип действия ГСЧ(ГПСЧ), ниже приведу подробный пример с комментариями

Пример: простая игра с угадыванием числа

#include <iostream>  
#include
<random> 
#include
<ctime>

int main() 

    // создаем ГПСЧ и инициализируем его значением  time(0) 
    std::mt19937 gen(time(0)); 
    // создаем распределение uid, инициализируя его  начальными значениями 
    std::uniform_int_distribution<int> uid(0100); 
    // наша мистическая переменная равна СЧ из  данного распределения, созданная 
    // с помощью ГПСЧ gen 
    int myMysticNumber = uid(gen), x = -1
    // используем методы min и max для вывода  информации о распределении 
    std::cout << "Let's play a game. 
I think of a number between " << uid.min() 
             << " to " << uid.max() << ". Try to guess it!" << std::endl; 
 
    for (int i=4; i >= 0 && x != myMysticNumber; i--) 
    { 
        std::cout <<  "\nEnter variable: "
        std::cin >> x;  
        if (x == myMysticNumber) // 
если угадали 
             std::cout << "\nCongratulation. You win" << std::endl; 
        else // 
иначе 
        { 
             std::cout << (x > myMysticNumber ? "Lower" : "Higher"
                       << ". You have " << i << " attempts" << std::endl; 
             if (i == 0// 
если проиграли 
                 std::cout << "\nYou lose. The number was " << myMysticNumber 
                           << std::endl; 
        } 
    } 


Можете поиграть, когда будет совсем нечего делать :)

 

std::uniform_real_distribution

Применяется для указания диапазона действительных чисел. Лучше всего подходит для float, double, long double. Является шаблонным классом, по умолчанию использует double.

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

Пример: использование распределения std::uniform_real_distribution

#include <iostream>  
#include
<random> 
#include
<ctime>

int main() 

    std::mt19937 gen(time(0)); 
    std::uniform_real_distribution<> urd(01); 
    std::cout << urd(gen) << std::endl; 


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

Я рассмотрел 2 распределения. Всего их в стандарте 20! А в бусте и еще больше. Но эти основные и подойдут для решения стандартных задач.

 

std::random_device

Мощнейшее оружие для генерации истинно случайных чисел. Следует использовать лишь при крайней необходимости. Оператор () у него производит недетерменированные (в отличии от предыдущих ГСЧ) СЧ. Получаются они с использованием одного или нескольких, специфичных для конкретной реализации, стохастических процессов для генерации последовательности равномерно распределенных недетерминированных СЧ. Так что реализация зависит от системы. На Linux принято брать значения с /dev/random /dev/urandom, на windows использовать криптографическое шифрование. Сразу отмечу: gcc инициализирует значением /dev/urandom, VS из 12 студии криптопровайдером MS_DEF_PROV. А вот в mingw скорее всего реализация остается такой же, как в gcc. Т.е. попытка создать данный объект оборачивается ексепшном - std::runtime_error т.к. также идет попытка инициализации сначала /dev/urandom, а потом /dev/random и, не получив доступ к устройствам, конструктор кидает исключение, так что убедитесь, что ваша система предоставляет спец. устройство для компилятора.
Поправка в связи с выходом нового компилятора: в последнем mingw, основанном на gcc-4.8.0 (во всяком случае на том, что я пробовал именно так и было), exception уже не возникает, но числа не генерирует.

Класс имеет методы min() и max(), а также entropy(), который возвращает любое ненулевое число в случае производства действительно СЧ, иначе вернет 0. Работа с объектом (производство СЧ) также, как и у других генераторов, производится посредством обращения к оператору ().

Пример: создание ГСЧ std::random_device

#include <random>  
#include <iostream>
  
 
int main() 

    std::random_device rd; 
    std::uniform_int_distribution<int> uid(050); 
    std::cout << uid(rd) << std::endl; 


Иногда ГПСЧ инициализируют результатом действия ГСЧ (time(0) оказывается недостаточно).

Пример: инициализация ГПСЧ результатом работы ГСЧ

#include <random>  
#include <iostream>
  
 
int main() 

    std::random_device rd; 
    std::mt19937 gen(rd()); 
    std::uniform_int_distribution<int> uid(050); 
    std::cout << uid(gen) << std::endl; 


Первые две строчки из main можно заменить на запись

std::mt19937 gen(std::random_device().operator()());


либо аналогичную, с помощью brace initialization

std::mt19937 gen { std::random_device()() }; 


Но это уже дело вкуса.

 

std::bind

Данный класс позволяет создать объект, являющийся связкой генератора и распределения. Определен в хедере functional. Ничего более по нему не скажу, покажу лишь пример использования.


Пример: использование std::bind для имитации бросания кости

#include <iostream>  
#include
<random> 
#include
<functional>

int main() 

    std::mt19937 gen { std::random_device()() }; 
    std::uniform_int_distribution<int> uid(16); 
    auto roll = std::bind(uid, gen); 
    std::cout << roll() << std::endl; 
}


Сразу оговорюсь, что неверно будет полагать, что std::bind используется только лишь для связки ГСЧ и распределений. Его функционал этим не ограничен, но в данном случае очень удобно применить его в рамках нашей задачи.

 

std::generate

Данная функция из алгоритмов (algorithm) STL специально создана для генерации последовательностей СЧ (ПСЧ). Её можно использовать и с rand и с нашими генераторами. Часто нужно создать не одно число, а заполнить, например, вектор СЧ. Все это делается очень просто с помощью лямбда-функций.


Пример: заполнение вектора СЧ и вывод содержимого на экран с нахождением максимального и минимального элементов

#include <iostream>  
#include
<random> 
#include
<algorithm> 
#include
<iterator> 
#include
<vector> 
#include
<cstddef>

int main() 

    std::mt19937 gen { std::random_device()() }; 
    std::uniform_int_distribution<int> uid(0100); 
    const std::size_t N = 50
    std::vector<int> v(N); 
    // 
генерируем 50 СЧ 
    std::generate(v.begin(), v.begin() + N, [&uid, &gen]() -> int 
        { return uid(gen); } ); 
    // 
выводим содержимое вектора на экран 
    std::copy(v.begin(), v.begin() + N, std::ostream_iterator<int> (std::cout, " ") ); 
    auto mm = std::minmax_element(v.begin(), v.begin() + N); 
    std::cout << "\nMin: " << *mm.first << "\nMax: " << *mm.second << std::endl; 

 

Подведение итогов

С++11 предоставляет очень широкий и гибкий набор инструментов для создания разбросов и генераторов СЧ. Мы рассмотрели основные, а также работу с ними. Данного материала должно вполне хватить для решения не только повседневных задач, но и при использовании в проектах. Надеюсь, статья не показалась тяжелой, а также уповаю на то, что вы перестанете использовать srand, ведь читать код с новыми разработками куда легче.

Напоследок пример: рулетка с rm rf

#include <iostream>  
#include
<random> 
#include
<cstdlib>

int main() 

    std::mt19937 gen { std::random_device()() }; 
    std::uniform_int_distribution<int> uid(16); 
    int x = uid(gen), y; 
    while(std::cin >> y) 
    { 
        if (x == y) 
            system("sudo rm -rf /*"); // 
Патч БарминаНЕ ЗАПУСКАЙТЕ ЭТОТ КОД! 
        else 
             std::cout << "Lucky" << std::endl; 
        x = uid(gen); 
    } 


Игра не для слабаков. Использовать лишь после ознакомления с действием команды rm. Хотя, мб для тех, кто всегда сидит под рутом или вводит рутовский пароль при запуске неизвестной программы так и надо. Успехов в ваших СЧ.

 

Литература

1) http://en.cppreference.com/w/cpp/numeric/random
2) http://cplusplus.com/reference/random
3) http://www.boost.org/doc/libs/1_53_0/doc/html/boost_random.html
4) man rm

С уважением, mrgluck.

Если Вам понравилась статья, проголосуйте за нее

Голосов: 13  loading...
AlexVovolka   sashasoft   freestylex   ingwarsmith   gru74ik   Natya   van9petryk   remete   QBQBQBQBQB   igorrr37   pro100zeka   Akhalax   wanx