優化nbody算法F＃

怎麼能進一步優化此代碼：優化nbody算法F＃

let rec nCollect func = function 
     | [] -> [] 
     | x::xs -> let firstAndNext body (firstBody, ys) = 
         let newFirst, z = func firstBody body 
         newFirst, z::ys 
        let y, ys = List.foldBack firstAndNext xs (x, []) 
        y::(nCollect func ys)

此代碼是nbody仿真程序的一部分。它正在獲取每個身體，並在它和下一個身體之間應用func功能。結果用於下一次迭代。我用列表略微優化了它。問題在於輸入物體數量在10以下，但nCollect被稱爲數百萬次。例如，如果我在nCollect中使用尾遞歸，結果會更糟糕。

來源

2011-11-01 The_Ghost

除了尾遞歸以外，你試過了什麼？你有測試顯示問題嗎？ – Richard

我認爲每種語言中90％的微優化問題的答案總是相同的：使用數組，循環和變異。

所以，我會使用數組，循環和變異，而不是List.foldBack。

來源

2011-11-01 09:03:47 Brian

List.foldBack本質上是一個循環，但問題在於從循環體（firstBody）創建的中間數據。如果它足夠聰明，可以重新使用中間存儲的內存位置，那麼它將會很好。但編譯器會做出這樣的魔力嗎？ –

@The_Ghost：如果很容易判斷某個方法是否純粹，那麼這將是可能的，但是在F＃中這是非常困難的。易於訪問可變性的問題之一。 – Guvante

一些快速的意見

List.Fold應該打List.FoldBack。看看這裏的代碼 - https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/list.fs你可以看到FoldBack將分配一個臨時數組，這可能很慢，而fold可以快速遍歷列表。

您也可以嘗試內聯firstAndNext

手動展開循環可能會有所幫助

來源

2011-11-01 09:04:44

內聯沒有幫助。奇怪的是，但在我的情況下foldback運行速度更快。 –

使用像埃瓦爾德求和或快速多（FMM）更好的算法。
用數組和for循環替換列表和遞歸函數。
對於小問題，用自定義代碼生成替換循環。

來源

2011-11-01 16:19:19

優化nbody算法F＃

回答

相關問題