Каков оптимальный алгоритм для создания несмещенного случайного целого в пределах диапазона?

В этом вопросе StackOverflow:

Генерирование случайного целого из диапазона

принятый ответ предлагает следующую формулу для генерации случайного целого числа между заданными min и max , причем min и max includeся в диапазон:

 output = min + (rand() % (int)(max - min + 1)) 

Но в нем также говорится, что

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

Но это не объясняет, почему оно предвзято относится к более низким числам или как устранить предвзятость. Итак, возникает вопрос: является ли это наиболее оптимальным подходом к генерации случайного целого в пределах (подписанного) диапазона, не полагаясь ни на какую фантазию, просто на функцию rand() , а в случае, если она является оптимальной, как удалить смещение ?

РЕДАКТИРОВАТЬ:

Я только что протестировал алгоритм while -loop, предложенный @Joey против экстраполяции с плавающей запятой:

 static const double s_invRandMax = 1.0/((double)RAND_MAX + 1.0); return min + (int)(((double)(max + 1 - min))*rand()*s_invRandMax); 

чтобы увидеть, насколько равномерно «шарики» «падают» и распределяются между несколькими «ведрами», один тест для экстраполяции с плавающей точкой и другой для алгоритма while -loop. Но результаты оказались разными в зависимости от количества «шаров» (и «ведер»), поэтому я не мог легко выбрать победителя. Рабочий код можно найти на этой странице Ideone . Например, с 10 ведрами и 100 шариками максимальное отклонение от идеальной вероятности среди ведер меньше для экстраполяции с плавающей запятой, чем для алгоритма while -loop (0,04 и 0,05 соответственно), но с 1000 шарами максимальное отклонение while -loop алгоритм меньше (0,024 и 0,011), а с 10000 шарами экстраполяция с плавающей запятой снова улучшается (0,0034 и 0,0053) и т. д. без значительной согласованности. Думая о возможности того, что ни один из алгоритмов не будет последовательно производить равномерное распределение лучше, чем у другого алгоритма, заставляет меня наклониться к экстраполяции с плавающей точкой, поскольку она работает быстрее, чем алгоритм while -loop. Так хорошо выбрать алгоритм экстраполяции с плавающей запятой или мои тесты / выводы не совсем корректны?

Проблема возникает, когда количество выходов генератора случайных чисел (RAND_MAX + 1) не равномерно делится на требуемый диапазон (max-min + 1). Так как будет последовательное отображение от случайного числа к выходу, некоторые выходы будут отображаться в более случайные числа, чем другие. Это независимо от того, как выполняется сопоставление – вы можете использовать модулю, деление, преобразование в плавающую точку, независимо от того, какой вуду вы можете придумать, основная проблема остается.

Масштабы проблемы очень малы, и нетребовательные приложения могут вообще уйти, игнорируя ее. Чем меньше диапазон и больший RAND_MAX, тем менее выраженный эффект будет.

Я взял ваш пример программы и немного изменил ее. Сначала я создал специальную версию rand которая имеет диапазон 0-255, чтобы лучше продемонстрировать эффект. Я сделал несколько настроек для rangeRandomAlg2 . Наконец, я изменил количество «шаров» до 1000000, чтобы улучшить согласованность. Вы можете увидеть результаты здесь: http://ideone.com/4P4HY

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

Я думаю, что вызов этого «алгоритма Java» немного вводит в заблуждение – я уверен, что он намного старше, чем Java.

 int rangeRandomAlg2 (int min, int max) { int n = max - min + 1; int remainder = RAND_MAX % n; int x; do { x = rand(); } while (x >= RAND_MAX - remainder); return min + x % n; } 

Проблема в том, что вы выполняете модульную операцию. Это не проблема, если RAND_MAX будет равномерно делиться вашим модулем, но обычно это не так. В качестве очень надуманного примера предположим, что RAND_MAX равен 11, а ваш модуль равен 3. Вы получите следующие возможные случайные числа и следующие полученные остатки:

 0 1 2 3 4 5 6 7 8 9 10 0 1 2 0 1 2 0 1 2 0 1 

Как вы можете видеть, 0 и 1 немного более вероятны, чем 2.

Один из вариантов решения этой проблемы – выборка отбраковки: запрещая номера 9 и 10 выше, вы можете привести к тому, что результирующее распределение будет равномерным. Трудная часть – это выяснить, как сделать это эффективно. Очень хороший пример (тот, который занял у меня два дня, чтобы понять, почему он работает) можно найти в Java java.util.Random.nextInt(int) .

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

 int n = (int)(max - min + 1); int remainder = RAND_MAX % n; int x, output; do { x = rand(); output = x % n; } while (x >= RAND_MAX - remainder); return min + output; 

EDIT: Исправлена ​​ошибка fencepost в вышеприведенном коде, теперь она работает так, как должна. Я также создал небольшую пробную программу (C #; взяв единый PRNG для чисел от 0 до 15 и построил PRNG для чисел от 0 до 6 от него различными способами):

 using System; class Rand { static Random r = new Random(); static int Rand16() { return r.Next(16); } static int Rand7Naive() { return Rand16() % 7; } static int Rand7Float() { return (int)(Rand16() / 16.0 * 7); } // corrected static int Rand7RejectionNaive() { int n = 7, remainder = 16 % n, x, output; do { x = Rand16(); output = x % n; } while (x >= 16 - remainder); return output; } // adapted to fit the constraints of this example static int Rand7RejectionJava() { int n = 7, x, output; do { x = Rand16(); output = x % n; } while (x - output + 6 > 15); return output; } static void Test(Func rand, string name) { var buckets = new int[7]; for (int i = 0; i < 10000000; i++) buckets[rand()]++; Console.WriteLine(name); for (int i = 0; i < 7; i++) Console.WriteLine("{0}\t{1}", i, buckets[i]); } static void Main() { Test(Rand7Naive, "Rand7Naive"); Test(Rand7Float, "Rand7Float"); Test(Rand7RejectionNaive, "Rand7RejectionNaive"); } } 

Результат выглядит следующим образом (вставка в Excel и добавление условной раскраски ячеек, чтобы различия были более очевидными):

введите описание изображения здесь

Теперь, когда я исправил свою ошибку в вышеприведенной выборке, она работает так, как должна (до того, как она будет смещаться 0). Как вы можете видеть, метод float совсем не идеален, он просто распределяет смещенные числа по-разному.

Легко понять, почему этот алгоритм создает смещенную выборку. Предположим, что ваша функция rand() возвращает однородные целые числа из набора {0, 1, 2, 3, 4} . Если я хочу использовать это для генерации случайного бита 0 или 1 , я бы сказал rand() % 2 . Множество {0, 2, 4} дает мне 0 , а множество {1, 3} дает мне 1 – так ясно, что я пробовал 0 с 60% и 1 с 40% правдоподобием, совсем не однородным!

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

В приведенном выше примере целевой диапазон равен 2, наибольший множитель, который вписывается в диапазон случайной генерации, равен 4, поэтому мы отбрасываем любой образец, который не находится в наборе {0, 1, 2, 3} и снова рулон.

std::uniform_int_distribution(min, max) простым решением является std::uniform_int_distribution(min, max) .

Interesting Posts

Тип Nullable не является нулевым типом?

Случайно удалил папку «Загрузки», окно «Специальная папка», как восстановить?

cron jobs – как зарегистрироваться?

Когда fragment fragmentа с SwipeRefreshLayout во время обновления, fragment замерзает, но на самом деле все еще работает

Как мне диагностировать и визуализировать время ping для Wi-Fi-маршрутизатора?

JAXB: как отобразить карту в значение

Получение ViewExpiredException в кластерной среде, в то время как метод сохранения состояния установлен на клиентский и пользовательский сеансы действителен

Удалить дубликаты из MongoDB

Как прокручивать и просматривать данные на экране GNU

Сообщение об ошибке: для Android SDK требуется Android Developer Toolkit версии 22.6.1 или выше

Как читать несколько текстовых файлов в одном RDD?

как сохранить текущую строку в jqgrid

Возврат кода статуса http из Web Api controller

Как написать Firefox Addon?

Как изменить культуру приложения WinForms во время выполнения

Давайте будем гением компьютера.