Re: [問題] 大量數字的計數並排序

[tropical72 (藍影)]

※ 引述《bleed1979 (十三)》之銘言：
: 如果想要0 ~ 2147483647，

以下恕刪, 講到亂數, 我分享一下我的經驗, 我想 原原 po 可能會遇到和我一樣的問題

(看 原原po 的問題不知道是不是在算亂數的均勻度)

之前有一陣子是做 GA、PSO 相關研究，於是產生了二個問題，

一個是亂數太小 (#1B-QLJnn), 另一個是亂數重覆問題，

(亂數重覆問題導致結果會有規律一閃一閃的，一下是 A set on，一下是 B set on)

後來因緣際會下去聽 PSO 大師 Voratas 演講，最後得知原來他之前有做過亂數的研究

也針對各種程式語言進行亂數評估測試, 這裡打插一下，亂數的好壞主要有二個

一個是亂數取得的速度，一個是亂數取得幾次之後開始重覆。

(演講是沒說怎麼測的,不過亂數對GA,PSO 是真的很重要)

測試結果似乎都不合格(包含 vb,excel,c, 最差的是 excel, 最快重覆)

於是會後 mail 給他請他寄給我一份 paper, 我打算自己寫亂數。

他寄給我的 paper 是

SOFTWARE FOR UNIFORM RANDOM NUMBER GENERATION:
DISTINGUISHING THE GOOD AND THE BAD

有興趣的話可以去找找看。

然而我不是數學系,連工科都不是,paper 整篇光是符號、名詞就搞得快發瘋,

最後看了三天後決定放棄自己寫亂數的念頭, 於是又開始上網找一堆 paper,

經歷了許多時間之後找到了這個網站

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

裡面就有提供了作者自己寫的亂數原始碼

(author:2002, Makoto Matsumoto and Takuji Nishimura)

包含 32-bit integer, 64-bit integer, floating 亂數

好處我就不用多說了, 後來才知道這叫

馬其賽旋轉演算法 (Mersenne Twister algorithm),

下載下來用後我那相關的研究才又繼續進行。

說了那麼多, 如果有類似問題的話, 趕快去下載下來吧 !! 下載處：

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html

--
YouLoveMe() ? LetItBe() : LetMeFree();

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.76.142
※ 編輯: tropical72      來自: 180.177.76.142       (12/28 01:36)
推 bill42362:推
推 loveme00835:我還是再推 <tr1/random>
→ tropical72:我也推love大的作法,只是做特殊研究的話C的亂數不夠亂
→ loveme00835:你PSO亂數是用來做第一代的分布嗎?
→ loveme00835:XD 我記錯
→ Semisphere:因為設計變數值域很大嗎，亂數太小還蠻不常見的qq
推 loveme00835:自己跑實驗的結果, std::tr1::mt19937 就很亂了, 速度
→ loveme00835:倒還可以
→ tropical72:!! http://0rz.tw/L0PTW  mt19937: Marsenne twister
→ tropical72:太慢知道 std::trl 這種東西 XD
→ tropical72:to Semi~:當時我只知道用rand(),然而vc的RAND_MAX是
→ tropical72:32767,這個數字是真的很小,資料十萬筆抽二筆出來馬上就
→ tropical72:有問題了
推 ericinttu:請問可以用兩次亂數值去直接拓展亂數值域嗎?
→ ericinttu:例如(0~32767)x(0~32767) => (0~1073741823).
→ tropical72:樓上問題我沒確定過,不知道這樣會不會影響所謂的均勻度
推 ericinttu:個人以為均勻度問題跟亂數本身有關,跟拓展方式無關.
→ ericinttu:lib的亂數是均勻的且為獨立事件,就可以用這樣去增大亂數
→ ericinttu:的值域範圍.
推 ledia:有用 % 取你要的範圍, 就有可能會不均勻了
→ tropical72:to eric:想到一件事,這樣算的話,大於32767的質數永遠都
→ tropical72:取不到,這樣應該就不叫均勻了吧？
推 loveme00835:直接串接起來每個數字至少都會相距 32768, 相鄰的數字
→ loveme00835:不太可能出現, 有這規律其實不是很亂
→ james732:Linux底下有個亂數源/dev/random  這個東西夠亂嗎？
推 LPH66:樓樓上的問題其實還好...拓展後的數字相距32768內等於原亂數
→ LPH66:出現第一和第三個相等  兩個機率是一樣的...
→ LPH66:呃  我是指高15bit相等 @_@
→ LPH66:只要原來是 uniform 的  拓展出來就是 uniform
→ LPH66:當然 LCG 拿來做這種事的確不太能說均勻就是了...
→ loveme00835:要很獨立才能辦到吧? ...
推 LPH66:嚴格一點的話上下兩半要用獨立的 PRG 生出來才行
→ loveme00835:搞剛 Orz ...
推 ericinttu:tropical72誤會我了. 那個"x"並不是乘法,算是2維表示法.
→ tropical72:真的誤會大了,樓上是說 rand()*RAND_MAX+rand() 吧？
→ loveme00835:RAND_MAX 要 +1 喔~
推 VictorTom:那個, << 加 | 不就好了嗎@_@" 保險一點的話多個 & 遮掉
→ VictorTom:RAND_MAX可能不一定是32767的問題....XD
→ tropical72:目前的討論前提是RAND_MAX太小,大家都假設是32767