Re: [問題] 記憶體爆炸

作者: LPH66 (-6.2598534e+18f)   2017-11-16 21:28:51
你的程式有兩個問題:
(1) 這個問題應該跟你所謂"記憶體不足"有關
RK 法它是一個數值方法, 所以你不能讓 Mathematica 用精確值一直疊代
舉個例: xRK[0] := 1
xF1[0] := Sqrt[xRK[0]] 算得 Sqrt[1] = 1
xF2[0] := Sqrt[xRK[0]+π/100*xF1[0]] 算得 Sqrt[1+π/100] 就會停在這裡
xF3[0] := Sqrt[xRK[0]+π/100*xF2[0]]
會算得 Sqrt[1+π/100*Sqrt[1+π/100]]
xF4[0] 同理會算得 Sqrt[1+π/50*Sqrt[1+π/100*Sqrt[1+π/100]]]
所以 xRK[1] 就會是一個很長的算式:
https://i.imgur.com/NVhAzQ1.png
因為 Mathematica 的特性, 它碰到這種無法化簡的東西就會保持原樣在那裡
所以你可以想像 xRK[100] 會是一個多麼深的疊代式
這可能是造成你的程式記憶體不足的原因
解決方法很簡單, 因為這是數值方法, 只要每一次都算出大約值就行了
也就是在你這些疊代的式子外面掛上 N[] 即可
(2) 這個問題則跟你的計算時間有關
同樣也是因為這是一個疊代公式
所以直接從這裡計算 xRK[100] 會非常多次地計算它下面的所有值:
xRK[100] 呼叫 xRK[99], xF1[99], xF2[99], xF3[99], xF4[99]
xF1[99] 呼叫 xRK[99]
xF2[99] 呼叫 xRK[99], xF1[99] 所以一共呼叫兩次 xRK[99]
xF3[99] 一共呼叫三次 xRK[99]
xF4[99] 一共呼叫四次 xRK[99]
所以 xRK[100] 一共呼叫十一次的 xRK[99]
依此類推下去, xRK[100] 將會呼叫 11^100 次 xRK[0]
這種數字你也不用等它算完了, 宇宙大概會先毁滅 XD
解決方法是一種稱做 memoization 的方法
(個人喜歡翻譯為「筆記法」, 維基百科的詞條叫「記憶化」)
概念很簡單, 算好的東西記下來之後要就直接拿
在 Mathematica 裡的 memoization 的寫法有一個公式:
func[n_] := func[n] = (* 函數定義 *)
這裡前面的 := 阻止它後面的東西先求值
在你呼叫它給它 n 值之後 (例如 func[5]), 後面的 n 代換成你給它的值
會變成 func[5] = (* 函數定義 /. n->5 *)
這即是一個函數特殊狀況的賦值, 所以會把函數定義算出來後賦給 func[5]
以後只要再次呼叫 func[5] 就會直接提取這個值出來, 不會重算一次
用這兩種方式改寫你的程式之後, 算出要畫表的那個 Table 幾乎是瞬間完成:
https://i.imgur.com/vzcUMjm.png
作者: ar851060 (ar851060)   2017-11-19 19:23:00
喔喔喔喔居然有那麼簡單的方法!太感謝了
作者: louis925 (稚空)   2016-04-30 06:06:00
大推!是個需要學習演算法的前奏記憶法好像也稱為 Dynamical programming
作者: LPH66 (-6.2598534e+18f)   2016-06-27 19:03:00
記憶法跟 DP 是很像但不一樣的演算法最重要的差別是記憶法是 top-down, 由後方呼叫啟動計算當取用到前面的呼叫時只在第一次做計算, 之後就查筆記但 DP 是 bottom-up, 由前方呼叫先行計算藉由排定一個計算順序使得所有東西能夠依序求出來在 Mathematica 的這種長得很像函式語言的結構下寫 DP 會比寫記憶法來得有挑戰性
作者: pig030 (FEBUR.PHEIX)   2016-03-11 20:58:00
lph66高手!

Links booklink

Contact Us: admin [ a t ] ucptt.com