
Равномерный рандом
Как-то было дело — я столкнулся с тем, что стандартный Math.random() меня не устраивает. Дело в том, что числовые значения, получаемые при его использовании распределены по нормальному закону.
По-русски говоря, это значит, что если, например, создать генератор случайных целых чисел от 0 до 10, используя лишь штатный random(), то некоторые из получаемых чисел будут выпадать гораздо чаще остальных. Конечно, если необходимо сгенерировать лишь несколько случайных значений, это проканает, но если игра основана на случайности, то повышенная повторяемость некоторых «избранных» чисел начинает бросаться в глаза (((
Порыв интернет и перекопав старые политеховские лекции, я на скорую руку соорудил для себя класс, позволяющий получить случайные числа, распределенные по равномерному закону.
И опять же, если сказать по-русски, то частоты выпадения различных чисел, генерируемых этим классом, стремятся быть одинаковыми ))))
Для тех, кто еще не успел изобрести подобный велосипед и/или не собирается этого делать, я выкладываю код своего класса:
При создании экземпляра этого класса получаем очередной генератор случайных чисел. Конструктору передается в качестве аргумента верхний предел случайных значений.
Напимер:
Кстати, как видно из кода класса, если аргумент в конструктор не передавать, то максимальное число, которое может сгенерировать это творение рук человеческих (и уж поверьте — рано или поздно оно это сделает) по умолчанию равно
Ну а получить очередное случайное число можно простым обращением к свойству Value:
Я не претендую на оригинальность или совершенство идеи — может кто-то предложит лучший вариант (кстати буду рад — пишите, «есличо»), но я очень доволен результатами работы этого класса. )
Вот, вроде бы и все…
На последок скажу, что если внезапно у кого возникнет (возможно, по пьяни) непреодолимое желание поглубже вгрызться в физический смысл и механизм работы сварганенного мною класса, то можете поискать информацию о линейном конгруэнтном методе и линейных конгруэнтных последовательностях — ибо я при написании сего класса опирался именно на них
ПС: Буду искренне рад, если моя писанина хоть кому-нибудь поможет
По-русски говоря, это значит, что если, например, создать генератор случайных целых чисел от 0 до 10, используя лишь штатный random(), то некоторые из получаемых чисел будут выпадать гораздо чаще остальных. Конечно, если необходимо сгенерировать лишь несколько случайных значений, это проканает, но если игра основана на случайности, то повышенная повторяемость некоторых «избранных» чисел начинает бросаться в глаза (((
Порыв интернет и перекопав старые политеховские лекции, я на скорую руку соорудил для себя класс, позволяющий получить случайные числа, распределенные по равномерному закону.
И опять же, если сказать по-русски, то частоты выпадения различных чисел, генерируемых этим классом, стремятся быть одинаковыми ))))
Для тех, кто еще не успел изобрести подобный велосипед и/или не собирается этого делать, я выкладываю код своего класса:
public class RND {
private var val:uint;
static var maxValue:uint = 2147483647;
private var k:uint = 1220703125;
private var b:uint = 7;
private var m:uint;
public function RND(modul:uint = 2147483647) {
this.m = modul;
var t:Date = new Date();
var s:String = t.time.toString();
s = s.substr(s.length-3,3);
this.val = uint(s);
}
public function get Value() {
val = ((k * val + b) % maxValue);
return val % m;
}
}
Кстати есть особенность — генератор случайных чисел, реализованный в этом классе, будет выдавать случайные целые, неповторяющиеся числа от 0 до modul-1 с периодом, равным 7 миллионам. Думаю, для решения большинства задач этого достаточно.При создании экземпляра этого класса получаем очередной генератор случайных чисел. Конструктору передается в качестве аргумента верхний предел случайных значений.
Напимер:
private var rnd:RND = new RND(100);
Данный экземпляр будет генерировать целые случайные числа от 0 до 99.Кстати, как видно из кода класса, если аргумент в конструктор не передавать, то максимальное число, которое может сгенерировать это творение рук человеческих (и уж поверьте — рано или поздно оно это сделает) по умолчанию равно
2147483647 - 1 = 2147483646
.Ну а получить очередное случайное число можно простым обращением к свойству Value:
rnd.Value
ВАЖНО! при каждом обращении к свойству Value получаем новое случайное число!!!Я не претендую на оригинальность или совершенство идеи — может кто-то предложит лучший вариант (кстати буду рад — пишите, «есличо»), но я очень доволен результатами работы этого класса. )
Вот, вроде бы и все…
На последок скажу, что если внезапно у кого возникнет (возможно, по пьяни) непреодолимое желание поглубже вгрызться в физический смысл и механизм работы сварганенного мною класса, то можете поискать информацию о линейном конгруэнтном методе и линейных конгруэнтных последовательностях — ибо я при написании сего класса опирался именно на них
ПС: Буду искренне рад, если моя писанина хоть кому-нибудь поможет
- +10
- Hagemay
Комментарии (38)
Таким образом происходит инициализация генератора
ПС: А ссылочку про ксоры не могбы кинуть?
XOR
Разве не системное время?
Но так как вы решились публично выложить код, есть пару вопросов:
Почему название класса заглавными? Аббревиатура?
Почему имя геттера с большой, а переменных класса с маленькой?
Почему для статической переменной не указана область видимости? Да, по-умолчанию сейчас она internal.
Все что выше я написал — просто подсказки :)
Вероятности не меняются, основываясь на предыдущих результатах.
Имеется колода карт(36 штук), какова вероятность что выпадет n количество тузов из трех карт.
В данной задачи, w — сочетание.
Случай с n = 1:
A = среди трех взятых карт — 1 туз.
N = C(3 и 36) = (36*35*34)/(1*2*3) = 7140 (перерасчеты делать не будем, т.к. количество карт взятых и карт в колоде остается неизменным)
M = C(1 и 4) * C(2 и 32) = 4/1 * (32*31)/(1*2) = 1984
P(A) = 1984 / 7120 ~ 0.28 (или 28%)
Случай с n = 2:
A = среди трех взятых карт — 2 туза.
M = C(2 и 4) * C(1 и 32) = (4*3)/(1*2) * 32/1 = 192
P(A) = 192/7140 ~ 0.03 (или 3%)
Случай с n = 3:
A = среди трех взятых карт — 3 туза.
M = C(3 и 4) * C(0 и 32) = (4*3*2)/(1*2*3) = 4
P(A) = 0.0005 (или 0.05%)
Вуаля!
А так по сути да, велосипед) Но плюсую.
Я говорю про холдем или омаху, где каждый раз колода тусуется.
Естественно, если говорить про то, что у меня два туза на руках — то шанс тузу на доске выпасть весьма мал (поймать сет).
Я вот тут брал.
я не смогу сейчас назвать источник — давно эт было, но я собственными глазами читал о НОРМАЛЬНОМ характере распределения Math.random()!!!
В любом случае результаты, выдаваемые штатным рандомом весьма гавеные и уж очень далеки от равномерного закона — проведи эксперимент и ты увидишь ;)
Поэтому я с радостью заюзал самописный рендом как только предложили) Что собственно дало тот самый результат равномерного распределения =)
Например, если посадить человека писать произвольное действительное число, и параллельно сгенерить его компом — то сторонний человек может всегда легко выпасти, где человек генерил, а где комп (если конечно человек не сидел и не кидал монетку, только из ума генерил).
Выпасти просто: человек интуитвно не верит в частое появление длинных последовательностей одинаковых цифр, типа 1111, 22222, 33333333. И их избегает, думая что это не рандом получится.
А где вы читали про нормалное распределение? Можете поделиться ссылкой?:)
Кстати даже исходя из бонального удобства — зачем создавать штатный рандом с нормальным распределением? Из равномерного нормальное (или какое-то еще, если требуется) делается на раз-два, а вот из нормального сделать равномерное — нужно еще постараться. Это было бы просто неразумно — делать штатный рандом со «сложной» функцией распределения. В большинстве случаев требуется равномерное распределение, и заставлять разработчиков изгаляться было бы неуважительно.
Вы уж простите, что вступаю в спор, но мне кажется вы написали не совсем верную информацию:)
Буду очень рад выслушать аргументацуию в пользу нормальности распределения штатного рандома:)
нужно было склепать горстку фишек 6 окрасок, порядка сотни штук. окраска бралась рандомно из массива возможных окрасок. На протяжении двух дней, пока разбирался с другими задачами и параллельно тестил, заметил, что первая и последняя окраски в массиве встречаются на порядок меньше. Собственно бросалось в глаза то, что всё поле забито в основном двумя цветами из центра массива)
хотел решить проблему увеличением диапозона рандома и отсечением крайних значений, но вовремя появились эти темки)
За что очень благодарен авторам)
раньше вместо RandUtils.getInt(0, levelColors) стояло округление Math.random()*levelColors
мне кажется чтото в стандартном рандоме всётаки есть, раз несколько разных человек задавались этим вопросом =)
Исследованиями и спорами может заняться кто-нить у кого есть на это время
меня же вполне устроил предложенный в соседнем топике класс, и я получив что требовалось, продолжил разработку дальше)
а мне из за небольшого количества вариантов виделся метод распределения, а не обычный косяк в округлении =)
Я, конечно, не проверял на ста миллионах итераций…
Расскажу, как дело было:
Писал я игру наподобие Wack-A-Mole про Муму и злого Герасима:
www.newgrounds.com/portal/view/541007
игра провалилась, но не в этом суть — в игре случайным образом в девяти местах всплывают собаки и бомбы (далее — с/б). так вот сначала я пользовался штатным рандомом. после того как процесс всплывания с/б был запрограммирован, я решил немного потестить будущее детище и заметил неприятную особенность — начиная где-то с итерации 60й..70й с/б начали всплывать в 90 процентах случаев в строгой последовательности мест (простите за каламбур) — то есть, например:
собака во второй позиции;
собака в пятой позиции;
собака в шестой позиции;
собака в восьмой позиции;
бомба в третьей позиции;
собака в первой позиции…
и все зацикливается.
конечно нормальным законом тут пахнет мало. про нормальный закон штатного рандома я нагуглил непосредственно после вскрытия вышеописанного неприятного факта. к сожалению, ссылку ща дать не могу — я не помню на какой сайт меня привел гугл
По большому счету мне не важно по какому закону штатный рандом выдает значения. Меня интересовали всего лишь первые пару сотен случайный значений в рамках создаваемой игры и он моих надежд не оправдал. А написанный мною рандом удовлетворил мои запросы.