Вихрь Мерсенна (Mersenne twister) — генератор псевдослучайных чисел
Запись от drnet_ua размещена 13.10.2010 в 20:24
навеяно этой темой
пример в первом посте я не заметил, вернее глянул мельком, показалось что на С, и както "грязненько", как многое сишное
полез в википедию, почитал.
20-25 минут был первый вариант, потом в течении дня с перерывами на работу вылизывал исходник.
как там в школе было: Проделав данную работу, я научился работать со статическими методами(т.е. работа с классом без явного создания инстанса), писать комментарии для автогенерации хелпа, ну и освежил в памяти bitwise операции.
по скорости работы - генерация целого в пределах 0-0xFFFFFFFF:
пример - 100%
статический вызов - 85%
через переменную - 67%
по скорости работы генерация "real" в пределах 0-1:
пример - 100%
статический вызов - 48%
через переменную - 34%
график распределения прилагается.
покритикуйте исходник.
package { /** * ... * @author drnet_ua * * Usage example: * * trace( MersenneTwister.IntRange(10, 50) ); * * or * * var mt:MersenneTwister = new MersenneTwister(); * trace( mt.mt.RandomSign()); * */ public class MersenneTwister { // constants private const MaxNumber:Number = Number.MAX_VALUE; private const MaxUint:uint = 0xFFFFFFFF; private const HalfMaxUint:uint = 0x7FFFFFFF; private const bit32nd:uint = 0x80000000; private const last31bits:uint = 0x7FFFFFFF; private const MagicNumber:uint = 0x6C078965; // coefficients for MT19937 private const n:uint = 624; private const m:uint = 397; private const r:uint = 31 private const a:uint = 0x9908B0DF; private const u:uint = 11; private const s:uint = 7; private const b:uint = 0x9D2C568016 private const t:uint = 15; private const c:uint = 0xEFC6000016; private const l:uint = 18; // variables private var MT:Array; private var index:uint = 0; private static var instance:MersenneTwister; // Static calls public static function getInstance():MersenneTwister { if(instance == null) { instance = new MersenneTwister(); } return instance; } /** * Generates random sign +1 or -1 * @return **/ public static function Sign():Number { return getInstance().RandomSign(); } /** * Generates random floating-point Number in [0..1) * @return **/ public static function Random():Number { return getInstance()._Random(); } /** * Generates random floating-point Number in [0..MAX_NUMBER) * @return **/ public static function Real():Number { return getInstance().randomReal(); } /** * Generates random floating-point Number in [Min..Max] * @return **/ public static function RealRange(Min:Number,Max:Number):Number { return getInstance().randomRealRange(Min,Max); } /** * Generates random integer Number in [0..MAX_NUMBER) * @return **/ public static function Int():Number { return getInstance().randomInt(); } /** * Generates random integer Number in [Min..Max] * @return **/ public static function IntRange(Min:Number, Max:Number):Number { return getInstance().randomIntRange(Min,Max); } /** * Generates random uint in [0..0xFFFFFFFF] * @return **/ public static function Uint():uint { return getInstance().ExtractNumber(); } /** * Setting new, user-defined starting seed, re-initializes Twister * @return **/ public static function Seed(NewSeed:uint):void { getInstance().SetSeed(NewSeed); } /** * Setting new, random starting seed, re-initializes Twister * @return **/ public static function Randomize():void { getInstance().RandomSeed(); } /** * Constructor method, starts with random seed * @return **/ public function MersenneTwister() { MT = new Array(n) SetSeed(Math.random() * MaxUint); } // Public calls /** * Generates random sign +1 or -1 * @return **/ public function RandomSign():Number { if (ExtractNumber() > HalfMaxUint) { return 1 } else { return -1}; } /** * Generates random floating-point Number in [0..1) * @return **/ public function _Random():Number { return ExtractNumber() / MaxUint; } /** * Generates random floating-point Number in [0..MAX_NUMBER) * @return **/ public function randomReal():Number { return _Random() * MaxNumber; } /** * Generates random floating-point Number in [Min..Max] * @return **/ public function randomRealRange(Min:Number, Max:Number):Number { if (Min == Max) { return Min; } if (Min > Max) { var Swap:Number = Min; Min = Max; Max = Swap; } return Min + _Random() * (Max - Min); } /** * Setting new, random starting seed, re-initializes Twister * @return **/ public function RandomSeed():void { SetSeed(Math.round(Math.random() * MaxUint)); } /** * Setting new, user-defined starting seed, re-initializes Twister * @return **/ public function SetSeed(seed:uint):void { index = 0; MT[0] = seed; for (var i:uint = 1; i < 624; i++) { MT[i] = (MagicNumber * (MT[i-1] ^ (MT[i-1] >> 30)) + i); } } /** * Generates random integer Number in [0..MAX_NUMBER) * @return **/ public function randomInt():Number { return Math.round(randomReal()); } public function randomIntRange(Min:Number, Max:Number):Number { return Math.round(randomRealRange(Min, Max)); } // twister routines private function GenerateNumbers():void { var y:uint; for (var i:uint = 0 ; i < n; i++) { y = (MT[i] & bit32nd) + (MT[(i + 1) % n] & last31bits); MT[i] = MT[(i + m) % n] ^ (y >> 1); if ((y % 2) == 1) { MT[i] ^= a; } } } private function ExtractNumber():uint { if (index == 0) { GenerateNumbers() } var y:uint = MT[index]; y ^= (y >> u); y ^= (y << s) & b; y ^= (y << t) & c; y ^= (y << l); index = (index + 1) % n; return y; } } }
Всего комментариев 53
Комментарии
13.10.2010 22:27 | |
класс не наследуется и не имплементирует интерфейс - синглтон не нужен.
|
14.10.2010 11:30 | |
Напомните, пожалуйста, какой разрядности uint?
|
14.10.2010 11:47 | |
32 unsigned
Number - up-to 52 bit |
14.10.2010 12:53 | |
Аха, а что тогда в коде делают пятибайтные юинты?
|
14.10.2010 15:01 | |
14.10.2010 16:00 | |
Цитата:
при копировании из википедии прилип индекс "16"
Сходятся ли ваши результаты с официальными? Ну и страница с сишным исходником, если что - http://www.math.sci.hiroshima-u.ac.j...mt19937ar.html |
15.10.2010 12:05 | |
Цитата:
Math.random() быстре в какихто "жалких" 7.2 раза )))
|
|
Обновил(-а) Neborya 15.10.2010 в 16:31
|
15.10.2010 19:12 | |
Math.random():
Цитата:
Experiment count: 8000000
Time: 3822 ms Цитата:
Experiment count: 8000000
Time: 14975 ms |
19.10.2010 08:46 | |
BlooDHounD, а диспетчеризация?
|
19.10.2010 10:49 | |
MrPoma, чего?
|
19.10.2010 11:37 | |
Это повод для использования синглтонов?
|
19.10.2010 13:07 | |
я Вас не понимаю. что подразумевается под диспетчеризацией?
|
19.10.2010 14:31 | |
Рассылка событий.
|
19.10.2010 14:41 | |
а при чем тут синглтоны?
|
19.10.2010 14:42 | |
В посте реализован.
|
19.10.2010 14:47 | |
ну и?? Не понимаю в вашем высказывании взаимосвязи синглтон - рассылка событий. Как вы к этому пришли?
|
19.10.2010 14:59 | |
MrPoma, что "рассылка событий"? вы о чём? что Вы хотите сказать?
|
19.10.2010 15:22 | |
Наверно MrPoma хочет сделать синглтон который наследуется от EventDispatcher`а, позволяющий глобально вешать и слушать события.
|
19.10.2010 15:27 | |
А по теме тогда какие события Генератор будет слать, типа "onNewRandomDouble" ?))
|
19.10.2010 15:30 | |
Psycho Tiger, да. Я мог бы объяснить это более подробно и в одном комментарии, но мне показалось, что и так понятно будет. А оказалось не понятно.
|
|
Обновил(-а) MrPoma 19.10.2010 в 15:33
|
19.10.2010 15:34 | |
MrPoma, ну так dispatchEvent это метод класса EventDispatcher.
Из этого следует что диспатчить не унаследовав нельзя. То есть мы должны унаследовать от EventDispatcher что бы диспатчить. Из этого следует что Ваше высказывание не опровергает то что: Цитата:
имплементация и наследование - это единственная причина, по которой нужно выбрать синглтон вместо обычных статиков
|
|
Обновил(-а) incvizitor 19.10.2010 в 15:38
|
19.10.2010 15:41 | |
Цитата:
То есть мы должны унаследовать от EventDispatcher что бы диспатчить.
|
19.10.2010 15:45 | |
А, ну да.
i.o, это имплементация. |
19.10.2010 15:50 | |
Цитата:
i.o, это имплементация.
|
19.10.2010 15:54 | |
Цитата:
i.o, это имплементация.
|
19.10.2010 15:56 | |
Psycho Tiger, я хотел диспатчизацию рассмотреть как повод использовать синглтон, но оказалось, что это наследование. Ну или имплементация.
|
19.10.2010 16:06 | |
то есть человеческим языком сказать такое простое высказывание было сложно. поэтому толпа людей выдаивала из вас по капле молока целую страницу.
|
19.10.2010 16:13 | |
Ну раз ситуация прояснилась, может мне кто по-человечески скажет, что же хотел MrPoma?
|
19.10.2010 16:42 | |
Ну, не то чтобы я хотел сделать. Уже сделал.
|
19.10.2010 17:30 | |
Не стоит злоупотреблять синглтонами - это идет вразрез с ООП. Получается что-то вроде шага назад к программингу с глобалами.
|
19.10.2010 18:46 | |
Я в крупных проектах стараюсь по этой причине не пользоваться. В одноразовом коде помогает.
|
19.10.2010 21:52 | |
Совсем не пользоваться глобальными штуками, пожалуй, ещё большее зло, чем злоупотребление ими, если смотреть с позиции того, кто будет в коде разбираться.
|
19.10.2010 22:15 | |
ну я ж написал не злоупотреблять, а не вообще исключить ))
|
20.10.2010 00:15 | |
А синглтон чистый оч. редкий зверь, на флэше ещё и делается через одно место. Я больше именно за глобальные функции. Loader#load или Socket#send в разных классах вызываются?
|
20.10.2010 01:31 | |
Что-то блоги превращаются в флейм по обсуждению архитектур)
Пора бы уж к форуму чат прикрутить) |
20.10.2010 03:23 | |
Ага голосовой , с возможностью тильта и цензуры)
|
Последние записи от drnet_ua
- Singleton и с чем его едят. (20.12.2010)
- Вихрь Мерсенна (Mersenne twister) — генератор псевдослучайных чисел (13.10.2010)