其實小第不請楚這樣表達對不對
一個電腦叢集可以做大量的計算
可是現實中我們沒辦法把兩台爛電腦連接起來玩高需求的電腦遊戲=口=
離題了...
我今天聽到同學再討論一個數學公式
公式的作用是，將上次的計算結果當成下次的計算條件
ㄜ~一聽很直覺就是遞回
他們在討論的是
老師給的題目用電腦來計算都要算上好幾天...
我在旁邊聽到就在想，能不能用更快的方式求出結果呢??
當然先想到的就是連接多台電腦來計算
可是數學公式是用遞回來求解
感覺上還是只能用單一台電腦來計算
所以上來請教各位前輩有沒有更好的方式??
(除了換更好的電腦之外)
已邀請的邦友 {{ invite_list.length }}/5
q00153提到：
老師給的題目用電腦來計算都要算上好幾天...
q00153提到：
上次的計算結果當成下次的計算條件
....
q00153提到：
將上次的計算結果當成下次的計算條件
這不一定是遞迴，通常稱為迭代。迭代可以用遞迴或單純迴圈來解。
要分散給多台做平行處理的，是每一次迭代所要處理的工作，而不是迭代這個處理程序。理解嗎？(打一個比方，你要把一塊大蛋糕吃掉，重點是把切分的每一塊小蛋糕吃掉，而不是切那塊蛋糕這個動作)
目前最夯的分散式處理，是 map-reduce，關鍵字去 google 一下吧！
q00153提到：
公式的作用是，將上次的計算結果當成下次的計算條件
感覺就跟計算簡單的階層問題是類似的...
可以透過Judge測試自己的解題方式是否正確
http://140.119.163.240/ShowProblem?problemid=d038
只要能AC(表示通過)而不會TLE(表示執行超過時間限制),
代表執行速度可以接受,不然就是設計上有問題所以速度太慢了~
例如要算 100! 如果已經有 99! 的結果 只需算 99! * 100 一次
如果從頭算一般就是迴圈99次 (((100*99)*98)*97 ... )
當然也可以作成是(A*B)遞回99次...
如果問題是要計算 1萬次 1000!
那麼有10000台電腦 各自從頭算一次1000!
當然時間會比1台電腦一值重算1000!作10000次要快
假設10000台電腦速度一樣, 後者處理時間是前者的一萬倍
但是每個相同n!的結果不論計算幾次結果都是相同的,
如果已經有1000!計算過的結果記憶,其實只需直接回應即可就不用重算了
也就是只要有台電腦 將 1!, 2!, 3!, 4!, ... 1000!
都算過一次記憶起來後, 就可以隨時回應 1 < N < 1000 的 N! 結果不用重算
當然也可以用10台或更多台每次要重算的電腦來應付這樣的需求,
將N送進閒置的電腦計算N!來獲得結果
如果全部電腦都剛好在算較大的N!所以比較慢,
就等某台先算完當前問題後才能在處理新的問題了...
wwx這個階乘例子應該是叫『動態規劃』，跟分散處理無關，也不需要用到分散處理。(用分散處理，反而是叫多台電腦做同樣的事了)
我想,可能把很簡單的事真的寫的很簡單可能造成誤會...
多台電腦可以是2台專門針對1~20!,2台針對21~100!, 6台針對101~1000! ...
1~20!可以用int64處理即可,更大的數就須透過大數運算來處理,
由於較大的階層結果值後面都是一串0,又可以用不一樣的演算技巧來增加效率, ...
10倍數的階層也可以另有設計技巧來增加效率, ...
現在又為了突顯事情所以用很笨的處理方式來描述這樣的系統,
如何map reduce,需不需要分散,各有巧思囉~
當然聰明的人在這個範圍內用現代的電腦大致上不會去思考分散處理吧!
而分散處理也是要規劃,如果採用動態規劃又常會冠上智能處理的說法,
總之,依我所見,各種行為在名詞出現之前就已經存在,
而要不要設計到那麼厲害與問題簡單與否其實是兩回事,
至於要用什麼名詞來解釋哪個部分是另一種討論的範圍了...
以前述情境,如果一個case是要獲得(3的倍數階層值所有結果)
那麼多台電腦是『動態規劃』還是『分散處理』呢? 呵~
iThome鐵人賽
看影片追技術