peltorator

Часто бывает так, что ваши решения задач зависят от случайных чисел. Стандартным примером будет являться декартово дерево, в котором логарифмическая высота достигается в том случае, если потенциалы будут выбраны случайно. Когда ваша программа использует случайные числа, нужно быть внимательным, чтобы не попасть в какую-нибудь ловушку. В этом разделе мы как раз поговорим про то, какие бывают ловушки, как в них не попасться, а также как упростить себе жизнь. В основном речь будет идти про C++, однако некоторые вещи можно по аналогии перенести в другие языки.

mt19937

Первое, что нужно сделать, когда вы работаете со случайными числами, — это забыть про функцию rand. Не стоит использовать ее ни-ко-гда! И на это есть три причины.

Первая причина заключается в том, что случайные числа, которые генерирует rand, — это «плохие» случайные числа. Дело в том, что компьютер не может сгенерировать по настоящему случайные числа. Поэтому вместо этого он генерирует «псевдослучайные» числа. Существуют разные способы генерации псевдослучайных чисел, и способ, который используется в rand далеко не самый лучший. В них легко можно вычленить периодичности и т.п.

Вторая причина более обозрима. Она заключается в том, что эта функция платформозависима. По стандарту она генерирует случайное число от нуля до RAND_MAX. Проблема заключается в том, что в linux это число RAND_MAX совпадает с максимальным числом, которое может храниться в типе int ($2^{31} - 1$), и все хорошо. Однако в windows RAND_MAX равен $32767$ ($2^{15} - 1$), а это на самом деле очень маленькое число. Если вы не знаете этого и хотите генерировать много случайных чисел, они будут очень часто повторяться в таком случае. Другая проблема встает тогда, когда вам нужно генерировать действительно большие числа. В этом случае с функцией rand придется изворачиваться и использовать конструкции типа RAND_MAX * rand() + rand().

И самое ужасное произойдет в тот момент, когда вы захотите использовать функцию random_shuffle, которая случайным образом перемешивает элементы массива. Для ее работы нужна генерация случайных индексов массива, то есть случайных чисел от $0$ до $n - 1$, однако число $n$ вполне вероятно может быть сильно больше, чем $32767$. В таком случае сгенерированная перестановка абсолютно не является случайной. К примеру, если $n = 3 \cdot 10^6$, тесты показывают, что каждый элемент находится в среднем на расстоянии $2 \% n$ позиций от своего изначального места, хотя с теоретической точки зрения это должно быть $33 \%$.

Замечание: Начиная с C++17 функция random_shuffle больше не поддерживается.

Третья причина заключается в том, что генератор случайных чисел, который мы рассмотрим далее работает просто быстрее, чем rand. Подробнее мы поговорим про это позже.

Для решения всех этих проблем подойдет генератор случайных чисел mt19937, добавленный в C++11. Он вне зависимости от компилятора генерирует случайные числа от $0$ до $2^{32} - 1$ (обратите внимание, что здесь генерируется случайное unsigned int число). Этот генератор основан на простом числе Мерсена $2^{19937} - 1$ (его название — это как раз сокращение от его параметров: «Mersenne Twister pseudo-random generator of 32-bit numbers with a state size of 19937 bits»). Такой генератор намного более «рандомный» и его период — это как раз $2^{19937} - 1$, что является невероятно большим числом (примерно $10^{6000}$). Давайте рассмотрим пример работы этого генератора:

mt19937 rnd(4321);
cout << rnd() << ' ' << rnd() << endl;

Данный код создает генератор под названием rnd с начальным сидом $4321$. После этого генератор можно использовать как функцию. Данный код выведет на экран два случайных числа от $0$ до $2^{32} - 1$. Стоит обращать внимание на то, что если присвоить значение rnd() переменной типа int, то значение может быть отрицательным. Однако если вы сразу знаете, что вам нужно число из какого-то диапазона, то взяв значение по модулю вы избежите отрицательных чисел:

rnd() % 1000

Кроме того, этот генератор можно использовать при перемешивании элементов массива. Для этого нужно воспользоваться функцией std::shuffle, аналогичной random_shuffle. Она принимает начало и конец последовательности, а также генератор. К примеру:

shuffle(a.begin(), a.end(), rnd);

Также стоит обратить внимание на то, что мы не только выигрываем в качестве генератора и величине генерируемых чисел, но и во времени. Генерация числа при помощи rnd в $3$ раза быстрее генерации при помощи rand.

Если вам нужно генерировать еще бóльшие числа, у mt19937 есть старший брат mt19937_64, который генерирует уже $64$-битные случайные числа.

Стоит не забывать и о платформенной независимости. mt19937 не только генерирует большие случайные числа на любой платформе, он кроме того генерирует одни и те же числа (при фиксированном сиде) на любой платформе. Так что вы можете быть уверены, что когда вы засылаете ваше решение в систему, оно будет там работать точно так же, как и на вашем компьютере.

Еще одним плюсом может быть то, что вы можете создавать несколько разных mt19937 генераторов в одной программе (с одним и тем же сидом, либо с разными) и использовать их независимо. Как это можно использовать, каждый решит для себя сам. К примеру, если вы делаете in-code стресс, вы можете не передавать решениям входные данные, сгенерированные случайно, а генерировать их прямо по ходу решения, и если вы используете один и тот же сид, но разные генераторы в двух решениях, они будут генерировать одни и те же числа.

uniform_int_distrubition

В C++ помимо mt19937 есть большое количество удобных вспомогательных инструментов для работы со случайными числами.

Первый пример, который мы рассмотрим, — это uniform_int_distribution. Это инструмент, позволяющий генерировать случайное целое число в заданном диапазоне. Легче всего понять его принцип работы на примере:

mt19937 rnd(4321);
uniform_int_distribution<int> distrib(1, 10);
cout << distrib(rnd) << endl;

Мы создаем объект класса uniform_int_distribution. В шаблон мы передаем, какого типа должны возвращаться числа, в данном случае это int (его можно опускать, потому что компилятор сам догадается о типе из типа левой и правой границы). Затем в конструктор передается два числа — левая и правая граница отрезка, в котором будут генерироваться числа. После чего для того, чтобы сгенерировать случайное число, нужно передать в uniform_int_distribution наш генератор случайных чисел. В данном случае это mt19937, который мы заранее определили. Такой код выведет случайное целое число от $1$ до $10$ включительно.

Стандартным способом сгенерировать число в полуинтервале от $l$ до $r$ был бы следующий код:

int uniform_distribution(int l, int r) {
    return rnd() % (r - l) + l;
}

В случае, если нужно сгенерировать случайное число от $0$ до $r$, код можно упростить, просто взяв значение rnd() по модулю $r$. uniform_int_distribution не только упрощает этот процесс, но и спасает вас от неожиданных проблем.

Обратите внимание, что если rnd генерирует случайное число от $0$ до $C$, то rnd() % r — это случайное число от $0$ до $r$ только в том случае, если $C$ делится на $r$. В противном случае остатки $0$, $1$, $\ldots$, $\left(C - 1\right) \bmod r$ будут генерироваться немного чаще, чем все остальные. Вы вряд ли как-то это сможете заметить, если $r$ — это, к примеру, $3$, однако для больших $r$ это может привести к неприятным последствиям. Пускай $r = \left\lfloor \frac{2 \cdot C}{3} \right\rfloor$. Тогда для остатков от $0$ до $\frac{r}{2}$ есть два возможных числа с такими остатками, а для остатков, больших $\frac{r}{2}$, таких чисел по одной штуке. Это значит, что маленькие остатки будут генерироваться в среднем в два раза чаще, чем большие. uniform_int_distribution как раз таки помогает решить эту проблему.

Момент, который стоит все таки отметить — это то, что в отличие от mt19937, uniform_int_distribution все таки платформозависим. То есть при фиксированном сиде mt19937 могут выдаваться разные числа на разных компиляторах. Не то, чтобы это было очень серьезной проблемой, но стоит учитывать, что у вас на компьютере и в тестирующей системе могут генерироваться разные числа.

Как генерировать случайные числа по модулю

Сделаем небольшое отступление. Как мы поняли, если нам нужно генерировать случайное число из какого-то отрезка, нам в этом поможет uniform_int_distribution. Однако что бы мы делали, если бы у нас его не было? Пришлось бы использовать плохой генератор, который генерирует числа неравномерно? Давайте приведем рандомизированный алгоритм, который за ожидаемое время $O(1)$ вернет нам случайный равномерно распределенный остаток по модулю $r$.

Как мы уже поняли, если $2^{32}$ делится на $r$, то все хорошо. Мы должны просто взять остаток от деления rnd() на $r$. Однако если $r$ не является степенью двойки, распределение такого остатка будет неравномерным. Давайте избавимся от этих последних остатков, которые мешают равномерности. То есть возьмем число $X$, равное $2^{32} - (2^{32} \bmod r)$. Такое число будет делиться на $r$, но при этом будет не меньше $2^{31}$ (если $r \ge 2^{31}$, то такое число не меньше $r$, которое не меньше $2^{31}$, а если $r < 2^{31}$, то мы вычтем что-то меньшее $2^{31}$, поэтому получим число, которое не меньше $2^{31}$). Тогда давайте сделаем так: если случайно сгенерированное число $q$ меньше $X$, то вернем $q \bmod r$, что будет равномерно распределенным случайным остатком, а если $q$ не меньше $X$, то повторим генерацию заново. Так как $X$ не меньше $\frac{2^{32}}{2}$, то вероятность успеха каждый раз не меньше $\frac{1}{2}$, поэтому нам в среднем понадобится сгенерировать не больше двух случайных чисел.

Другие распределения

По аналогии с uniform_int_distribution в C++ есть много других распределений. К примеру, normal_distribution и exponential_distribution, которые соответствуют нормальному и экспоненциальному распределениям. Маловероятно, что это может понадобиться вам при решении задач, но все же.

А вот что действительно может понадобиться вам, так это генерировать случайное вещественное число. Для этого подойдет uniform_real_distribution. Его использование аналогично uniform_int_distribution, но только теперь генерируется не случайное целое число из отрезка, а случайное вещественное.

Выбор сида рандома

Важным вопросом является выбор сида рандома. Формально есть всего два варианта выбора сида: детерминированный (фиксированное число) и случайный. Давайте поймем, какой вариант нужно использовать в какой ситуации.

Чаще всего (частота употребления — это, конечно, индивидуальная вещь, но все же) вы хотите использовать константный сид рандома (мы ранее использовали всегда число $4321$, но это может быть ваше любимое число). Какие у этого плюсы? В таком случае ваши случайные числа весьма условно случайны. На самом деле они вполне детерминированы. Каждый раз, когда вы запускаете программу, вам выдаются одни и те же числа. Чем же это хорошо? Тем, что вы контролируете ситуацию.

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

Другой плюс — это уверенность в результате. Вы знаете, что когда вы зашлете решение в систему, оно будет работать там на тестах точно так же, как и на вашем компьютере. Кроме того, если вы получили по задаче AC, то вы уверены, что сколько бы раз не происходило перетестирование, ваше решение все равно будет проходить тесты.

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

В каком же случае все таки нужно использовать случайный сид (про то, как сгенерировать случайный сид, мы поговорим позже)? Во-первых, в любых контестах со взломами (codeforces, topcoder и т.п.). Если в таких соревнованиях ваш сид не случайный, то человек, который смотрит на ваш код, может запустить у себя локально ваше решение, посмотреть, какие случайные числа оно генерирует, и без труда построить контртест, тем самым вся ваша случайность будет абсолютно бесполезна.

Во-вторых, это может понадобиться вам, когда вы хотите запустить ваше решение несколько раз и проверить, что от изменения сида вывод не меняется. Это можно сделать, меняя каждый раз сид руками в коде, но после этого каждый раз придется перекомпилировать программу. Случайный сид может быть хорошим решением этой проблемы.

В-третьих, если вы пишете стресс тесты. Есть два подхода в этом плане. Первый — передавать сид как аргумент командной строки, либо выбирать его случайно. Если вы все таки решили выбрать сид случайно, то вам очень важно «качество» этого случайного сида. Об этом мы как раз и поговорим далее.

Случайным сидом обычно выбирают текущее время, потому что это некоторая меняющаяся величина. Самый простой способ получения времени — это time(0). Эта функция возвращает текущее время в секундах. Этот вариант подойдет вам, если вы хотите запустить ваше решение несколько раз и посмотреть, что оно делает при разных сидах (если вы запускаете ваше решение не чаще, чем раз в секунду). Однако эту функцию категорически не стоит использовать в двух других случаях.

В случае стресс тестирования вы хотите прогонять тысячи тестов в секунду, но при использовании time(0) ваш генератор целую секунду будет генерировать вам один и тот же тест, поэтому поиск неправильного теста замедляется в тысячи раз.

В случае взломов проблема не так очевидна. На самом деле человек, который вас взламывает, может подгадать, в какую секунду ваше решение будет тестироваться и подготовить тест специально для нее. Если этот вариант кажется вам невозможным, то есть и более реалистичный случай. Можно сделать тест, который является контртестом сразу к $60$ разным сидам. И если эти сиды — это последовательные секунды, то здесь для взлома остается лишь совершить его в правильную минуту, что совершенно не является проблемой.

Что же делать? Нужно использовать время в наносекундах (миллиардная доля секунды). Тогда подгадать сид точно уже не представляется возможным. Получить текущее время в наносекундах можно при помощи следующей строки:

chrono::steady_clock::now().time_since_epoch().count()

И это можно использовать как сид рандома:

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

Есть еще способ через random_device. Это генератор случайных чисел, который недетерминирован сам по себе:

random_device rd;
mt19937 rnd(rd());

Однако, к сожалению, это тоже платформозависимое решение. На windows random_device все таки детерминирован, поэтому этот способ не рекомендуется использовать.