PTT數位生活區 / C_and_CPP (C/C++)

[問題] 關於在陣列中快速產生亂數的方法

看板C_and_CPP (C/C++)作者 (幻滅)時間12年前 (2013/09/30 11:47), 編輯推噓6(6推 0噓 37→)
留言43則, 8人參與, 最新討論串1/2 (看更多)
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) VC++2012 問題(Question)： 如何在陣列中快速產生亂數 由於我的專題需要用到演算法作最佳化計算，所以我使用了C++去寫一個DE演算法 但是我在初始化部分是使用for三層迴圈(因為我總共有三個變數)將值一個一個產生 在一個一個丟入陣列中，我們老師覺得說這樣的初始化太慢了，他希望可以在一次迴圈中 就可以將一整列的亂數。 簡單來說就是: 我的程式是 loop1 [1][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ] loop2 [1][2][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ] 我的老師希望的是 loop1 [1][2][3][4][5][6] [ ][ ][ ][ ][ ][ ] loop2 [1][2][3][4][5][6] [4][7][8][0][5][6] 這是我C++的程式碼(我的有三個變數，PopulationSize、machine、VariableNumber) http://codepad.org/4fGQzhZ8 這是我們老師給我參考的MATLAB程式碼(此為兩變數，PopulationSize、VariableNumber) http://codepad.org/PqQ6CpQO 我有看到書上似乎可以用vector一次產生一整列的值，不過似乎只能固定值 因為當我使用亂數產生時，應該是同時產生的關係導致時間一樣所以所有亂數產生的值 都是一樣的。 這是我測試的程式碼 http://codepad.org/wNBx69lD 我GOOGLE了很多資料，還是找不太到我可以改的方法，所以想來這請教一下。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 210.240.236.116
→
09/30 12:16, , 1F
VC6?
09/30 12:16, 1F
VC2012
→
09/30 12:20, , 2F
matlab的rand(M,N)可以一次產生一個MxN的亂數矩陣
09/30 12:20, 2F
→
09/30 12:20, , 3F
c library裡面的rand()只能一次產生一個數字
09/30 12:20, 3F
→
09/30 12:21, , 4F
matlab並沒有比較快,只是把苦工包裝起來看不見而已
09/30 12:21, 4F
關於這點我有問過我一個C++比較強的同學，他也是這樣說跟我的可是我們老師對C不熟 他認為for迴圈會大大的降低程式運算的速度，所以要越少用越好... 而且...痾 你應該也了解 有些老師滿會堅持自己的觀點... 有些事情很難談....所以我才想來問問，有沒有什麼其他的方法可以做修改 謝謝 ※ 編輯: abab7974 來自: 210.240.236.116 (09/30 13:12)
→
09/30 13:21, , 5F
那看你重點是要 "加速" 還是只是不想看到 "for"..
09/30 13:21, 5F
→
09/30 13:24, , 6F
可以的話當然兩樣都能做最好了..
09/30 13:24, 6F
應該這樣說 我們老師認為有for就是有拖慢速度之嫌 而我問我同學的說法是我原本的程式碼跟matlab跑出來的速度是一樣的... 但是最終還是得依照我們老師的想法下去修正 所以當然第一優先 希望可以先把for迴圈給去除掉，因為難保我之後還會不會在多 一些變數，這樣有可能就要多幾維陣列了，這樣他又會更有話說了.... (所以還是希望有方法可以做到多維陣列只使用到1組for迴圈，就算運算速度一樣沒關係) 謝謝 ※ 編輯: abab7974 來自: 210.240.236.116 (09/30 13:30)
→
09/30 13:27, , 7F
那你要不要先算看看你現在這樣有多慢
09/30 13:27, 7F
→
09/30 13:28, , 8F
使用QueryPerformanceCounter()計時,告訴老師這樣並不慢
09/30 13:28, 8F
我是有寫計時下去，可是我沒有另一個可以比較的程式來看我的程式是否比較快 因為我們老師的程式跟我現在所要做的用途有差。 我現在是使用DE去跑一個測試函數( http://goo.gl/PpAGBw )來驗證結果是否正確 而這個測試函數不管是使用我們老師還是我的程式他所運算的時間都非常的短， 所以沒辦法有效的做比較。 而我現在要做的用途是用DE去一組資料的最佳化，過程包括讀入txt檔、 DE作最佳化數值、call模擬程式作計算、寫入txt檔，循環個幾千到幾萬次，總共的變數 也有100~400個左右，所以常常程式跑完都需要花個2~3天。 而我們老師的程式只有單純的寫DE演算法而已，我剛剛上面所提到的那耶過程是， 他要所要我做的東西，所以我沒有現在只有一個程式，沒有辦法提出說，何種辦法比較快 的數據給他看。 ※ 編輯: abab7974 來自: 210.240.236.116 (09/30 13:42)
推
09/30 13:40, , 9F
其實用一個 for 模擬多個 for 當然是可能的 (提示: 十進位)
09/30 13:40, 9F
→
09/30 13:41, , 10F
不過我也同意上面推文說的 先做一次 profiling
09/30 13:41, 10F
→
09/30 13:41, , 11F
告訴你們老師這兩種寫法沒有顯著的差異...
09/30 13:41, 11F
→
09/30 13:44, , 12F
不過是說我個人覺得用這種方法藏 for 會變慢...
09/30 13:44, 12F
※ 編輯: abab7974 來自: 210.240.236.116 (09/30 13:44)
→
09/30 14:00, , 13F
那用 std::generate_n 去藏 for 吧.
09/30 14:00, 13F
→
09/30 14:02, , 14F
要變快的話, 除了改變隨機性或者用平行處理之類的. 差異不大
09/30 14:02, 14F
→
09/30 14:13, , 15F
恩恩，感謝提供意見 我也有在研究多執行緒的部份了
09/30 14:13, 15F
推
09/30 14:20, , 16F
說真的, 不過是初始化一個陣列而已, 跟你要執行的演算法比
09/30 14:20, 16F
→
09/30 14:20, , 17F
在那上面多花那麼一點點時間根本就沒差...
09/30 14:20, 17F
推
09/30 14:22, , 18F
我還是覺得你不要糾結在陣列初始化上面了
09/30 14:22, 18F
其實也不只有初始化的部分，我在運算過程的陣列相乘也是使用for迴圈一層一層 慢慢去乘的，我也還在看我還有哪邊可以做修改以加快程式運算速度。 謝謝各位的幫忙 ※ 編輯: abab7974 來自: 210.240.236.116 (09/30 14:32)
→
09/30 14:36, , 19F
程式再怎麼寫,cpu還是一個一個去讀...
09/30 14:36, 19F
→
09/30 14:37, , 20F
compiler的最佳化開到最大就對了
09/30 14:37, 20F
→
09/30 14:38, , 21F
matlab是實作時要連續parse才會有不要多次for
09/30 14:38, 21F
→
09/30 15:29, , 22F
CPU還不都是把值一個一個塞進欄位裡面 有差嗎
09/30 15:29, 22F
→
09/30 17:16, , 23F
如果只是要把for藏起來, std::generate_n 是好解..
09/30 17:16, 23F
→
09/30 17:17, , 24F
如果問效能的話 再舉證說沒差就好了
09/30 17:17, 24F
→
09/30 17:17, , 25F
如果真的覺得程式慢得無法接受, 就 profiling 先..
09/30 17:17, 25F
→
09/30 17:18, , 26F
初始化很有可能對整體時間沒什麼太大影響..
09/30 17:18, 26F
推
09/30 19:46, , 27F
不然也不一定要一直call rand()
09/30 19:46, 27F
→
09/30 19:48, , 28F
主要就matlab for loop會慢是有原因的,在C不成立
09/30 19:48, 28F
→
09/30 19:50, , 29F
話說STL的rand性質不是很好,對你有影響嗎XD？
09/30 19:50, 29F
→
09/30 19:56, , 30F
STL在之前沒用過，是因為在找方法才去看到STL的用法
09/30 19:56, 30F
推
09/30 20:01, , 31F
那個亂數是演算法的過程之一, 所以差一點的亂數應該還好
09/30 20:01, 31F
→
09/30 21:06, , 32F
我就不相信rand()一秒300MB的throughput會不夠用...
09/30 21:06, 32F
推
10/01 02:06, , 33F
呃, kdjf 應該不是在講 throughput 的問題...
10/01 02:06, 33F
→
10/01 02:06, , 34F
他大概是想講 PRNG 產生的亂數在統計上沒有非常好
10/01 02:06, 34F
→
10/01 02:10, , 35F
LFSR統計特性應該還OK,是不可預測性超級爛,不能用在加密
10/01 02:10, 35F
→
10/01 02:11, , 36F
我講throughput是因為那時忍不住跑個測速比較看看
10/01 02:11, 36F
→
10/01 02:12, , 37F
64-bit平台跑Whirlpool可以到400MB/s,它又是加密等級hash
10/01 02:12, 37F
→
10/01 02:13, , 38F
我覺得可以寫幾個方便的function拿Whirlpool來取代rand()
10/01 02:13, 38F
→
10/01 02:15, , 39F
不過這些都是題外話,原PO的問題從300MB/s變成400沒啥幫助
10/01 02:15, 39F
→
10/01 02:17, , 40F
先把整個project寫完,分析哪邊最耗時再設法改良才有意義
10/01 02:17, 40F
→
10/01 02:18, , 41F
引擎馬力不足,結果在改雨刷外型以便降低風阻,沒幫助啊...
10/01 02:18, 41F
→
10/01 02:23, , 42F
Intel RDRAND指令號稱可以到500MB/s以上,但我沒實測過
10/01 02:23, 42F
→
10/01 02:24, , 43F
因為這個指令是Ivy bridge才開始有的,我手上沒有貨 XD
10/01 02:24, 43F
‣ 更多 abab7974 的文章
文章代碼(AID): #1IIFGxEu (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 abab7974 的文章
文章代碼(AID): #1IIFGxEu (C_and_CPP)