Это одна из этих очень простых задач программирования, с которыми я столкнулся недавно: учитывая функцию, возвращающую случайные целые числа от 0 до 4 включительно с равной вероятностью, напишите функцию, возвращающую случайные целые числа от 0 до 6 включительно.
Конечно, решение должно также возвращать одинаково распределенные числа. Итак, давайте начнем с определения образца входной функции:
|
1
|
def rand4() = (math.random * 5).toInt |
Ваша задача — реализовать rand6() , используя только rand4() . Дайте себе несколько минут и продолжайте читать.
Первый подход довольно прост, но он полностью нарушен:
|
1
|
def rand6() = rand4() * 3 / 2 |
Так просто. В идеальном решении каждое выходное значение от 0 до 6 должно появляться с вероятностью 1/7 . Можете ли вы сказать из кода выше, какова вероятность того, что rand6() 2 или 5 ? Правильно, это не больше 0 , вы никогда не получите эти значения. Надеюсь понятно почему. Итак, давайте перейдем к чему-то более сложному:
|
1
|
def rand6() = (rand4() + rand4()) % 7 |
Выглядит лучше, но все еще довольно далеко. Код выше имеет два основных недостатка. Прежде всего, результаты rand4() + rand4() варьируются от 0 до 8 но нам нужно от 0 до 6 . Очевидное решение — использовать операцию % 7 . Однако это приводит к тому, что 0 и 1 возвращаются в два раза чаще, поскольку 7 и 8 переполняются до 0 и 1 . Так что по этому поводу:
|
1
2
3
4
5
6
7
|
def rand6(): Int = { val rand8 = rand4() + rand4() if(rand8 > 6) rand6() else rand8} |
Я надеюсь, что рекурсия (которую можно легко превратить в цикл, но я оставляю эту работу компилятору Scala) не скрывает намерение — если сумма двух rand4() превышает ожидаемый результат, мы просто отбрасываем ее и вызываем rand6() раз. Однако есть еще одна тонкая, но поразительная ошибка — цитирование Википедии о равномерном распределении . Сумма двух независимых равномерно распределенных равномерных распределений дает симметричное треугольное распределение . Если вы не совсем поняли вышесказанное, взгляните на это живое демо на JavaScript, используя <canvas/> иллюстрирующее, что означает Википедия:
Эта программа просто размещает пиксели в случайных (X, Y) позициях на каждой панели. На первой панели я использую один Math.random() * 300 масштабированный до целого холста. Как видите, распределение более или менее равномерно. Но мы не можем сказать это о второй и третьей панелях. На второй панели я в принципе использую сумму двух равномерно распределенных переменных: (Math.random() + Math.random()) * 150) . Даже если это выражение может возвращать что-либо между 0 и 300 , точки очень смещены к середине холста (треугольное распределение). Такое же поведение подчеркивается на третьей панели, где используются десять вызовов Math.random() .
Правильный ответ
Подход, который я использую, основан на наблюдении, что rand4() может rand4() два случайных младших бита. Итак, начнем с реализации rand3() с известной семантикой:
|
1
2
3
4
|
def rand3(): Int = rand4() match { case 4 => rand3() case x => x} |
rand3() возвращает равномерно распределенные значения от 0 до 3 , отклоняя вывод 4 из rand4() . Как это поможет нам? Теперь у нас есть два случайных бита, каждый из которых равен 0 или 1 с вероятностью 50%. Мы можем легко расширить его для больших последовательностей, например, rand15() и rand7() :
|
1
2
|
def rand15() = (rand3() << 2) + rand3()def rand7() = rand15() >> 1 |
Вы должны быть довольно удобны с немного возиться выше. Имея возможность генерировать два случайных бита, я могу легко сгенерировать 4 и 3. Теперь rand6() представляет никакой сложности:
|
1
2
3
4
|
def rand6() = rand7() match { case 7 => rand6() case x => x} |
Чтобы сделать этот урок немного более интересным, давайте реализуем randN(n: Int) поверх rand4() . randN() должен возвращать равномерно распределенные натуральные значения от 0 до n . Я начну с реализации вспомогательного метода atLeastKrandBits(k: Int) возвращающего… как минимум K случайных битов :
|
1
2
3
4
5
6
|
def atLeastKrandBits(k: Int): Int = k match { case 0 => 0 case 1 => rand3() >> 1 case 2 => rand3() case b => (atLeastKrandBits(k - 2) << 2) + rand3()} |
Альтернативная реализация с помощью foldLeft() :
|
1
2
3
|
def atLeastKrandBits(k: Int) = (0 to (k + 1) / 2).foldLeft(0){ (acc, _) => (acc << 2) + rand3()} |
… или если вы действительно ненавидите тех, кто поддерживает ваш код:
|
1
2
3
|
def atLeastKrandBits(k: Int) = (0 /: (0 to (k + 1) / 2)){ (acc, _) => (acc << 2) + rand3()} |
Любая из реализаций выше randN(n: Int) проста:
|
1
2
3
4
5
6
7
8
|
def randN(n: Int) = { val bitsCount = java.lang.Integer.highestOneBit(n) val randBits = atLeastKrandBits(bitsCount) if(randBits > n) randN(n) else randBits} |
Выводы
Вы можете задать себе вопрос: почему мне это все равно? Если вы не понимаете распределение вероятностей, ваше приложение может выдать случайный результат, который на самом деле довольно легко предсказать. Это не имеет большого значения, если вы пишете игру, и враги с большей вероятностью появятся в некоторых местах на карте (но игроки обнаружат ее и злоупотребят ею!) Но если вам нужны случайные числа по соображениям безопасности или вы полагаетесь на равномерное распределение например, в целях балансировки нагрузки — любое отклонение может стать фатальным.
Ссылка: Распределение вероятностей для программистов от нашего партнера JCG Томаша Нуркевича в блоге Java и соседстве .