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

看板C_and_CPP作者 (藍影)時間15年前 (2010/12/28 01:35), 編輯推噓11(11推 0噓 28→)
留言39則, 9人參與, 最新討論串4/5 (看更多)
※ 引述《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)
推
12/28 01:46, , 1F
推
12/28 01:46, 1F
推
12/28 01:46, , 2F
我還是再推 <tr1/random>
12/28 01:46, 2F
→
12/28 01:47, , 3F
我也推love大的作法,只是做特殊研究的話C的亂數不夠亂
12/28 01:47, 3F
→
12/28 02:07, , 4F
你PSO亂數是用來做第一代的分布嗎?
12/28 02:07, 4F
→
12/28 02:11, , 5F
XD 我記錯
12/28 02:11, 5F
→
12/28 02:16, , 6F
因為設計變數值域很大嗎，亂數太小還蠻不常見的qq
12/28 02:16, 6F
推
12/28 02:17, , 7F
自己跑實驗的結果, std::tr1::mt19937 就很亂了, 速度
12/28 02:17, 7F
→
12/28 02:18, , 8F
倒還可以
12/28 02:18, 8F
→
12/28 02:29, , 9F
!! http://0rz.tw/L0PTW mt19937: Marsenne twister
12/28 02:29, 9F
→
12/28 02:30, , 10F
太慢知道 std::trl 這種東西 XD
12/28 02:30, 10F
→
12/28 02:47, , 11F
to Semi~:當時我只知道用rand(),然而vc的RAND_MAX是
12/28 02:47, 11F
→
12/28 02:49, , 12F
32767,這個數字是真的很小,資料十萬筆抽二筆出來馬上就
12/28 02:49, 12F
→
12/28 02:49, , 13F
有問題了
12/28 02:49, 13F
推
12/28 07:40, , 14F
請問可以用兩次亂數值去直接拓展亂數值域嗎?
12/28 07:40, 14F
→
12/28 07:42, , 15F
例如(0~32767)x(0~32767) => (0~1073741823).
12/28 07:42, 15F
→
12/28 07:58, , 16F
樓上問題我沒確定過,不知道這樣會不會影響所謂的均勻度
12/28 07:58, 16F
推
12/28 09:05, , 17F
個人以為均勻度問題跟亂數本身有關,跟拓展方式無關.
12/28 09:05, 17F
→
12/28 09:06, , 18F
lib的亂數是均勻的且為獨立事件,就可以用這樣去增大亂數
12/28 09:06, 18F
→
12/28 09:07, , 19F
的值域範圍.
12/28 09:07, 19F
推
12/28 10:13, , 20F
有用 % 取你要的範圍, 就有可能會不均勻了
12/28 10:13, 20F
→
12/28 13:40, , 21F
to eric:想到一件事,這樣算的話,大於32767的質數永遠都
12/28 13:40, 21F
→
12/28 13:40, , 22F
取不到,這樣應該就不叫均勻了吧？
12/28 13:40, 22F
推
12/28 14:21, , 23F
直接串接起來每個數字至少都會相距 32768, 相鄰的數字
12/28 14:21, 23F
→
12/28 14:21, , 24F
不太可能出現, 有這規律其實不是很亂
12/28 14:21, 24F
→
12/28 14:29, , 25F
Linux底下有個亂數源/dev/random 這個東西夠亂嗎？
12/28 14:29, 25F
推
12/28 14:54, , 26F
樓樓上的問題其實還好...拓展後的數字相距32768內等於原亂數
12/28 14:54, 26F
→
12/28 14:55, , 27F
出現第一和第三個相等 兩個機率是一樣的...
12/28 14:55, 27F
→
12/28 14:55, , 28F
呃 我是指高15bit相等 @_@
12/28 14:55, 28F
→
12/28 14:55, , 29F
只要原來是 uniform 的 拓展出來就是 uniform
12/28 14:55, 29F
→
12/28 14:56, , 30F
當然 LCG 拿來做這種事的確不太能說均勻就是了...
12/28 14:56, 30F
→
12/28 15:13, , 31F
要很獨立才能辦到吧? ...
12/28 15:13, 31F
推
12/28 15:23, , 32F
嚴格一點的話上下兩半要用獨立的 PRG 生出來才行
12/28 15:23, 32F
→
12/28 15:44, , 33F
搞剛 Orz ...
12/28 15:44, 33F
推
12/28 20:56, , 34F
tropical72誤會我了. 那個"x"並不是乘法,算是2維表示法.
12/28 20:56, 34F
→
12/28 23:37, , 35F
真的誤會大了,樓上是說 rand()*RAND_MAX+rand() 吧？
12/28 23:37, 35F
→
12/28 23:44, , 36F
RAND_MAX 要 +1 喔~
12/28 23:44, 36F
推
12/29 00:01, , 37F
那個, << 加 | 不就好了嗎@_@" 保險一點的話多個 & 遮掉
12/29 00:01, 37F
→
12/29 00:01, , 38F
RAND_MAX可能不一定是32767的問題....XD
12/29 00:01, 38F
→
12/29 00:36, , 39F
目前的討論前提是RAND_MAX太小,大家都假設是32767
12/29 00:36, 39F
‣ 更多 tropical72 的文章
文章代碼(AID): #1D6Cv4MU (C_and_CPP)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 5 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共5篇)
‣ 更多 tropical72 的文章
文章代碼(AID): #1D6Cv4MU (C_and_CPP)