Re: [問題] 迴圈加速

看板Mathematica作者LPH66 (1597463007)時間10年前 (2014/12/21 03:28)推噓4(4推 0噓 4→)

留言8則, 5人參與討論串2/2 (看更多)

※ 引述《Serenede (Serenede)》之銘言： : sav = 0; iter = 10000000; : For[i = 1, i <= iter, i++, : If[Random[]^2 < 1/2, sav = sav + 1;] : ] // Timing : 2 sav/iter // N 這裡有幾個點可以提: 首先, i 這個只有計數不參加計算的變數可以拿掉這種單純做某事 n 次的可以使用不帶變數的 Do 此例就是改寫成 Do[If[Random[]^2 < 1/2, sav = sav + 1;], {it}] 在我的電腦上這樣就可以只用 70% 的時間接下來要怎麼進步其實有兩個方向一個是把高階的 If 變成低階的這裡有一個平常少用的函式叫做 UnitStep 當所有參數都大於等於 0 時回傳 1, 有參數小於 0 時則回傳 0 由於圖形就像一階階梯一樣所以叫做 UnitStep (「單位階梯」) 這裡你是想要讓 Random[]^2 < 1/2 時累積變數加 1 因此將 1/2 - Random[]^2 送進 UnitStep 就可以得到對應的 1 或 0 的結果再把它全部加進 sav 裡就行了這裡之所以說是把高階 If 變成低階是因為 UnitStep 把這個判斷給包起來了, 它變成底層運算裡的一部份相對於我們做出比較再使用 If 判斷效率會高一點只不過單純這樣做會把另一個問題給顯露出來 Do[sav = sav + UnitStep[1/2-Random[]^2], {it}] 這一行在我的電腦上的執行時間是一開始的 80% 問題在於原本因為 If 的關係, sav 這個變數只會在有更新時才會改寫現在卻是每一圈時都會改寫一次, 即使改寫成的值跟原來一樣 (這也是為什麼一開始將 i 變數的改寫拿掉之後效率會變好這麼明顯的原因) 也就是有部份圈數原本沒有變數改寫的在改動後有變數改寫造成效率降低所以另一個方向就是我們要再想辦法把 sav 這個變數拿掉可以看到每次運算的結果其實就只是單一值的更新也就是說這可以看成新sav=運算[舊sav] 這樣的一個函數對 Mathematica 來說進行函數運算比實際存取變數要好太多了因此我們可以把這個運算寫成一個函數, 然後套用 Nest 進行迭代 (關於 Nest 可參照本版 #1JbkymTC, 那篇也是在講一個差不多的迭代狀況可以參考) 這樣這個變數的中間結果就會變成函式迭代的中間過程, 變數本身就不見了於是把運算寫成純函式之後就變成推文這一條了: : → biglion: Nest[UnitStep[(1/2-Random[]^2)]+#&,0,10000000] 12/21 00:57 (關於純函式可參照本版 #1EiPGgzs) 這一條在我的電腦上的執行時間大約只有原來的 3~4% 而已不過呢, Mathematica 在這裡有一個大絕招還記得我上面提說把高階 If 變成低階吧？ Mathematica 有一個函式可以把大部份簡單的運算都給變成低階, 叫做 Compile 用法是 Compile[{變數}, 函數定義] 它會回傳一個 CompiledFunction 物件, 可以當做函式使用餵給這個物件參數就會用比較低階的方式計算你給的函數 (實際上 Compile 是將函數編譯成 Mathematica 內部專用的虛擬機器碼所以會比直接進行高階運算來的快) 最一開始的程式其實稍做修改就能改成 Compile 版: calculate1 = Compile[{{iter, _Integer}}, Module[{sav, i}, sav = 0; For[i = 1, i <= iter, i++, If[Random[]^2 < 0.5, sav = sav + 1;]]; sav ] ] calculate1[10000000] 很驚人的, 在我的電腦上這個計算的時間就已經是一開始的 4~5% 了! 這就是將運算變成低階的威力 (事實上, 整個函式裡只有 Random 這個函式沒有低階對應而要額外呼叫全部的時間有不小的部份都是花在這個外部呼叫上面的) 當然上面的改進寫進去也有助於計算加速把推文的那條改成 Compile 版是這樣: calculate2 = Compile[{{iter, _Integer}}, Nest[UnitStep[(0.5 - Random[]^2)] + # &, 0, iter]] calculate2[10000000] 我的電腦上這一條的計算時間是一開始的 2% 而已之所以看起來沒有差多少的原因就是因為 Random 這個外部呼叫的時間的關係不過呢, Compile 時有一個重點要記一下參數如果可以確定是整數, 那參數列上寫成像上面範例那樣有助於加速因為對電腦來說整數運算比實數運算要來得快做個比較, 如果 calculate1 的參數列單純只寫 {iter} 的話執行時間會多出約四分之一這是因為 Compile 會假設參數是實數的關係不過如果算到一半不得不出現實數時, 那寫實數會比寫分數快上面的 Compile 版把 1/2 改成 0.5 就是這個原因因為 Random 的回傳值一定是實數如果那裡依然寫 1/2 的話計算時間會稍稍多個 10% 左右 -- いああオレたちには見えてるモノがあるbデきっと誰にも奪われないモノがあるはずさけ開口一番一虚一実跳梁跋扈形影相弔yュL羊頭狗肉東奔西走国士無双南柯之夢歪もぶ　意味がないと思えるコトがあるラPきっとでも意図はそこに必ずあるんのく依依恋恋空前絶後疾風怒濤有無相生ラH急転直下物情騷然愚者一得相思相愛だがろ無意味じゃないラ6あの意図が恋たで有為転変死生有命蒼天已死黄天當立 !!6五里霧中解散宣言千錯万綜則天去私のり -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85 ※ 文章網址: http://www.ptt.cc/bbs/Mathematica/M.1419103728.A.0EF.html