Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Регистрация Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Блоги > drnet_ua

Оценить эту запись

Вихрь Мерсенна (Mersenne twister) — генератор псевдослучайных чисел

Запись от drnet_ua размещена 13.10.2010 в 20:24

навеяно этой темой

пример в первом посте я не заметил, вернее глянул мельком, показалось что на С, и както "грязненько", как многое сишное

полез в википедию, почитал.

20-25 минут был первый вариант, потом в течении дня с перерывами на работу вылизывал исходник.

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

по скорости работы - генерация целого в пределах 0-0xFFFFFFFF:
пример - 100%
статический вызов - 85%
через переменную - 67%

по скорости работы генерация "real" в пределах 0-1:
пример - 100%
статический вызов - 48%
через переменную - 34%

график распределения прилагается.

покритикуйте исходник.

Код AS3:
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;            
        }
 
    }
 
}
Изображения
Тип файла: jpg chart.jpg (15.2 Кб, 1764 просмотров)
Всего комментариев 53

Комментарии

Старый 13.10.2010 21:55 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Исходник нормальный, за исключением Сишной конвенции по написанию кода. У нас переменные и методы начинаются с маленькой буквы =)

На самом деле синглтон здесь весьма сомнителен - обычных статических переменных хватило бы. Ну во всяком случае при первом просмотре - не вчитывался.

Интересно было бы увидеть разницу в скорости против Math.random()
Старый 13.10.2010 22:27 BlooDHounD вне форума
BlooDHounD
 
Аватар для BlooDHounD
класс не наследуется и не имплементирует интерфейс - синглтон не нужен.
Старый 13.10.2010 23:19 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
BlooDHounD, похоже я не совсем понимаю зачем нужен синглтон ) Раньше считал что когда нужен глобальный доступ к одному объекту, который может существовать в единственном числе. Не совсем понимаю, причем здесь могут быть интерфейсы или наследование.
Старый 13.10.2010 23:39 BlooDHounD вне форума
BlooDHounD
 
Аватар для BlooDHounD
Psycho Tiger, 100 раз уже обсуждалось. и не один раз мною. синглтон нужен, что бы ограничить количество экземпляров одной штукой. глобальный доступ - это побочный эффект. а имплементация и наследование - это единственная причина, по которой нужно выбрать синглтон вместо обычных статиков.
Старый 14.10.2010 10:46 drnet_ua вне форума
drnet_ua
 
Аватар для drnet_ua
1) в первом варианте клас был самым обычным, это я потом в примере подсмотрел как оно устроено. Было интересно как работает Консоль, но там как-то сложно было разобратся, тут все на виду, поэтому и реализовал.

2) Math.random() быстре в какихто "жалких" 7.2 раза )))

по графику расперделения - он не хуже, так-что это из области теоретических эксперементов
Старый 14.10.2010 11:30 dimarik вне форума
dimarik
 
Аватар для dimarik
Напомните, пожалуйста, какой разрядности uint?
Старый 14.10.2010 11:47 drnet_ua вне форума
drnet_ua
 
Аватар для drnet_ua
32 unsigned
Number - up-to 52 bit
Старый 14.10.2010 11:49 drnet_ua вне форума
drnet_ua
 
Аватар для drnet_ua
Цитата:
The uint class provides methods for working with a data type representing a 32-bit unsigned integer. Because an unsigned integer can only be positive, its maximum value is twice that of the int class.

The range of values represented by the uint class is 0 to 4,294,967,295 (2^32-1).
как-то так
Старый 14.10.2010 12:53 dimarik вне форума
dimarik
 
Аватар для dimarik
Аха, а что тогда в коде делают пятибайтные юинты?
Старый 14.10.2010 15:01 drnet_ua вне форума
drnet_ua
 
Аватар для drnet_ua
очепятка следует читать как
Код AS3:
        private const b:uint = 0x9D2C5680
        private const c:uint = 0xEFC60000;
при копировании из википедии прилип индекс "16"

как не странно на график это не повлияло
Старый 14.10.2010 16:00 i.o. вне форума
i.o.
 
Аватар для i.o.
Цитата:
при копировании из википедии прилип индекс "16"
Есть подозрения, что вы не проверяли правильность работы портированого алгоритма.
Сходятся ли ваши результаты с официальными?
Ну и страница с сишным исходником, если что - http://www.math.sci.hiroshima-u.ac.j...mt19937ar.html
Старый 14.10.2010 16:12 dimarik вне форума
dimarik
 
Аватар для dimarik
Может быть и вовсе не заморачиваться такими числами?
Код AS3:
trace( uint(0x9D2C568016) == uint(0x9D2C5680) ); // false
Показывает, что это разные числа. А раз разные и распределение не изменилось, то зачем оно вообще там такое?

В uint учитываются только 4 младших байта
Код AS3:
trace(uint(0x9D2C568016) == uint(0x2C568016) ); // true
Старый 15.10.2010 12:05 Neborya вне форума
Neborya
 
Аватар для Neborya
Цитата:
Math.random() быстре в какихто "жалких" 7.2 раза )))
А вот тут мужик хвалится, что у него Math.random в 6 раз быстрее http://seld.be/notes/random-seeds-ordering-disorder
Обновил(-а) Neborya 15.10.2010 в 16:31
Старый 15.10.2010 19:12 drnet_ua вне форума
drnet_ua
 
Аватар для drnet_ua
Math.random():
Цитата:
Experiment count: 8000000
Time: 3822 ms
import com.seld.util.SeededRand:
Цитата:
Experiment count: 8000000
Time: 14975 ms
3,9 раз
Старый 19.10.2010 08:46 MrPoma вне форума
MrPoma
 
Аватар для MrPoma
BlooDHounD, а диспетчеризация?
Старый 19.10.2010 10:49 BlooDHounD вне форума
BlooDHounD
 
Аватар для BlooDHounD
MrPoma, чего?
Старый 19.10.2010 11:37 MrPoma вне форума
MrPoma
 
Аватар для MrPoma
Это повод для использования синглтонов?
Старый 19.10.2010 13:07 BlooDHounD вне форума
BlooDHounD
 
Аватар для BlooDHounD
я Вас не понимаю. что подразумевается под диспетчеризацией?
Старый 19.10.2010 14:31 MrPoma вне форума
MrPoma
 
Аватар для MrPoma
Рассылка событий.
Старый 19.10.2010 14:41 i.o. вне форума
i.o.
 
Аватар для i.o.
а при чем тут синглтоны?
Старый 19.10.2010 14:42 MrPoma вне форума
MrPoma
 
Аватар для MrPoma
В посте реализован.
Старый 19.10.2010 14:47 i.o. вне форума
i.o.
 
Аватар для i.o.
ну и?? Не понимаю в вашем высказывании взаимосвязи синглтон - рассылка событий. Как вы к этому пришли?
Старый 19.10.2010 14:59 BlooDHounD вне форума
BlooDHounD
 
Аватар для BlooDHounD
MrPoma, что "рассылка событий"? вы о чём? что Вы хотите сказать?
Старый 19.10.2010 15:22 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Наверно MrPoma хочет сделать синглтон который наследуется от EventDispatcher`а, позволяющий глобально вешать и слушать события.
Старый 19.10.2010 15:27 i.o. вне форума
i.o.
 
Аватар для i.o.
А по теме тогда какие события Генератор будет слать, типа "onNewRandomDouble" ?))
Старый 19.10.2010 15:30 MrPoma вне форума
MrPoma
 
Аватар для MrPoma
Psycho Tiger, да. Я мог бы объяснить это более подробно и в одном комментарии, но мне показалось, что и так понятно будет. А оказалось не понятно.
Обновил(-а) MrPoma 19.10.2010 в 15:33
Старый 19.10.2010 15:34 incvizitor вне форума
incvizitor
 
Аватар для incvizitor
MrPoma, ну так dispatchEvent это метод класса EventDispatcher.
Из этого следует что диспатчить не унаследовав нельзя. То есть мы должны унаследовать от EventDispatcher что бы диспатчить.
Из этого следует что Ваше высказывание не опровергает то что:
Цитата:
имплементация и наследование - это единственная причина, по которой нужно выбрать синглтон вместо обычных статиков
Обновил(-а) incvizitor 19.10.2010 в 15:38
Старый 19.10.2010 15:41 i.o. вне форума
i.o.
 
Аватар для i.o.
Цитата:
То есть мы должны унаследовать от EventDispatcher что бы диспатчить.
Необязательно. Можно реализовать интерфейс IEventDispatcher
Старый 19.10.2010 15:45 MrPoma вне форума
MrPoma
 
Аватар для MrPoma
А, ну да.
i.o, это имплементация.
Старый 19.10.2010 15:50 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Цитата:
i.o, это имплементация.
Ну и что? Всё равно позволяет диспатчить.
Старый 19.10.2010 15:54 i.o. вне форума
i.o.
 
Аватар для i.o.
Цитата:
i.o, это имплементация.
угу, так и есть.
Старый 19.10.2010 15:56 MrPoma вне форума
MrPoma
 
Аватар для MrPoma
Psycho Tiger, я хотел диспатчизацию рассмотреть как повод использовать синглтон, но оказалось, что это наследование. Ну или имплементация.
Старый 19.10.2010 16:06 BlooDHounD вне форума
BlooDHounD
 
Аватар для BlooDHounD
то есть человеческим языком сказать такое простое высказывание было сложно. поэтому толпа людей выдаивала из вас по капле молока целую страницу.
Старый 19.10.2010 16:13 i.o. вне форума
i.o.
 
Аватар для i.o.
Ну раз ситуация прояснилась, может мне кто по-человечески скажет, что же хотел MrPoma?
Старый 19.10.2010 16:26 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
i.o. MrPoma хотел сделать из синглтона объект наследник-EventDispatcher, который мог бы глобально рассылать и позволять слушать события. Типа:
Код AS3:
Singleton.getInstance().addEventListener/dispatchEvent
MrPoma: диспатчить события можно или наследником EventDispatcher`а, или комозицией в которой реализованы эти методы. Композицию имеет место делать с реализацией IEventDispatcher, то есть в любом случае получаем или наследование, или реализация интерфейса. В таком случае синглтон делать нужно. Есть ли польза от глобальной диспатчеризации - вопрос другой.
Старый 19.10.2010 16:42 MrPoma вне форума
MrPoma
 
Аватар для MrPoma
Ну, не то чтобы я хотел сделать. Уже сделал.
Старый 19.10.2010 17:01 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Мне это тоже казалось неплохой идеей. А потом я понял что синглтон для какой-либо логики - уф уф но. Как в целом, почти для всего. Мультитон, пожалуй, туда же.

Сам использую статики для звуков - типа SoundMaster.addSound, даже там синглтон мне ненужен.
Старый 19.10.2010 17:30 i.o. вне форума
i.o.
 
Аватар для i.o.
Не стоит злоупотреблять синглтонами - это идет вразрез с ООП. Получается что-то вроде шага назад к программингу с глобалами.
Старый 19.10.2010 18:46 MrPoma вне форума
MrPoma
 
Аватар для MrPoma
Я в крупных проектах стараюсь по этой причине не пользоваться. В одноразовом коде помогает.
Старый 19.10.2010 21:52 -De- вне форума
-De-
 
Аватар для -De-
Совсем не пользоваться глобальными штуками, пожалуй, ещё большее зло, чем злоупотребление ими, если смотреть с позиции того, кто будет в коде разбираться.
Старый 19.10.2010 22:15 i.o. вне форума
i.o.
 
Аватар для i.o.
ну я ж написал не злоупотреблять, а не вообще исключить ))
Старый 19.10.2010 22:21 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
-De-, ну я вполне себе живу почти без глобальных штучек и совсем без синглтонов. Чем наличие их сказывается на читабельности? Злоупотребление - это всё рухнет при первой правке. Совсем нету - ну и пусть.
Старый 19.10.2010 23:49 -De- вне форума
-De-
 
Аватар для -De-
Document class не единственный? =)
Доставать глобальные штуки всегда проще и понятней. И если по сути глобальная штука достается обходными путями, то выглядит оно не айс.
Менеджер ассетов (ну тут так-сяк можно несколько), локализации, коннектор к серверу - глобальны, то, что всем рекомендуется. Или копирование кода и прочие нечитабельные в том числе вещи.
Старый 19.10.2010 23:52 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
-De-, мне как-то не приходило в голову сделать документ класс синглтоном. Нормальные люди его создавать заново не будут, однако возможность есть.

Локализация - лучше сделать функцией. Коннектор к серверу глобальный - это плохо. Должна быть вполне себе иерархие - сначала старшие контроллеры кушают, потом младшие. Менеджер ассетов - может быть, но наверняка есть более красивое решение.
Старый 20.10.2010 00:15 -De- вне форума
-De-
 
Аватар для -De-
А синглтон чистый оч. редкий зверь, на флэше ещё и делается через одно место. Я больше именно за глобальные функции. Loader#load или Socket#send в разных классах вызываются?
Старый 20.10.2010 00:36 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Вызываются. Только вот получается что вызываем статиком, а слушать мы статиком не можем, должно идти другой дорогой - от старшего к младшему. Получается каша какая-то. К тому же достаточно часто младший контроллер просит "хочу проституток в номер!", старший контроллер добавит в запрос в какой именно номер, контроллер выше добавит туда ещё город, а самый старший заголовок запроса. Вот и сдулся статик.

Кстати, можно поподробнее про Loader#load. Централизованная загрузка всего извне? Зачем? Это я хочу загрузить аватарку, так мне надо просить центр отдать мне её? А если я передумаю её грузить? Просить центр найти её и остановить загрузку? А если content достать проблематично? Отдавать копию через loaderInfo.bytes? А если от одного content проблематично, а от другого нет? Помечать от кого отдавать, а от кого нет? К чему все эти сложности?
Старый 20.10.2010 01:21 -De- вне форума
-De-
 
Аватар для -De-
Почему не можем слушать статиком? Вот старший и есть один глобальный, пусть он слушает, остальных может и не быть. Как допустим все ответы от сервера трейсить, если он не один?
Про Loader#load я имел в виду общение с сервером по http, URLLoader#load. Но у меня, кстати, есть такой загрузчик, у него есть в частности cancel(key:String):void, get(key:String):* и getBytes(key:String):ByteArray. Что там у кого есть всегда без проблем знал заказывающий загрузку. Полезная вещь, рекомендую, хоть он и не про глобальность, но автоматическая обработка ошибок и загрузка в 1 строку того стоит.
PS: оффтоп какой-то злой пошел %)
Старый 20.10.2010 01:31 Котяра вне форума
Котяра
 
Аватар для Котяра
Что-то блоги превращаются в флейм по обсуждению архитектур)
Пора бы уж к форуму чат прикрутить)
Старый 20.10.2010 03:23 in4core вне форума
in4core
 
Аватар для in4core
Ага голосовой , с возможностью тильта и цензуры)
Старый 20.10.2010 13:10 Psycho Tiger вне форума
Psycho Tiger
 
Аватар для Psycho Tiger
Цитата:
Почему не можем слушать статиком? Вот старший и есть один глобальный, пусть он слушает, остальных может и не быть. Как допустим все ответы от сервера трейсить, если он не один?
Офигенно. У нас старший контроллер должен слушать коннектор к серверу/являться его клиентом, причем один создаёт второго. Зачем здесь статик?

Цитата:
Как допустим все ответы от сервера трейсить, если он не один?
Например, в старшем или коннекторе.
Цитата:
Но у меня, кстати, есть такой загрузчик, у него есть в частности cancel(key:String):void, get(key:String):* и getBytes(key:String):ByteArray. Что там у кого есть всегда без проблем знал заказывающий загрузку.
А как заказчик узнаёт о том, что загрузилось? Ему отсылают событие или он слушает мульен событий и выбирает по key?

Цитата:
Полезная вещь, рекомендую, хоть он и не про глобальность, но автоматическая обработка ошибок и загрузка в 1 строку того стоит.
Как бы разные части программы - разные приоритеты. Не загрузилась аватарка - пофиг. Не загрузилась модель 3д мира - уже не пофиг. В итоге обработка в 1 строчку всё равно выливается в подписку событий просто перекинутых наверх.
 

 


Часовой пояс GMT +4, время: 07:59.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2020, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.