※ 引述《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% 左右