難以理解的Haskell內存分配行爲

我偶然發現了Haskell和FP，並被可能性嚇倒了。我內心的老數學書呆子沒有任何困難寫實際有用的樸素代碼。儘管如此，我仍然很難理解如何避免出現一些令人驚訝的性能瓶頸。難以理解的Haskell內存分配行爲

所以我寫了很簡短的代碼與天真的實現，然後嘗試一些改變，看看性能如何響應。這裏有一個例子，我真的無法理解......我寫了這個函數，它找到了一個解決方案Josephus problem,目的與一個天真的列表實現。

m = 3 
n = 3000 
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived...\n" 

whosLeft [lucky] = lucky 
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers

後者運行時間爲190 ms，根據RTS的生產率爲63％。

然後，我想嘗試的第一件事是刪除（長度士兵-1），並用遞減的整數替換它。

運行時間增加到900毫秒，生產力降低到16％，並且使用比以上簡單代碼多47倍的內存！所以我增加了嚴格的評估，強制使用Int類型，嘗試刪除全局變量等，但效果不佳。而我無法理解這種放緩。

m = 3::Int 
n = 3000::Int 
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived...\n" 

whosLeft 1 [lucky] = lucky 
whosLeft n' soldiers = n' `seq` left `seq` whosLeft (n'-1) left 
       where left = take (n'-1) $ drop m $ cycle soldiers

我已經通過性能相關的文章和帖子篩選過，但我似乎沒有得到有關此暗示。仍然是一個Haskell noob我一定會錯過一些大的東西...這個如何添加參數（預咀嚼計算...）如此之多地降低速度？

PS：我知道，如果真的約瑟夫曾與3000名士兵，他們就不會需要自殺......

來源

2011-08-30 Mathias Dolidon

沒有必要seq n'，whosLeft在n'中已經很嚴格。但你應該優化編譯。 – augustss

第一個解決方案利用其長度迫使士兵名單的整個脊椎。第二個解決方案只強制（使用seq）士兵列表的頭。將left替換爲seq與length left之間的內容，然後重新開始。

來源

2011-08-30 18:13:06 sclv

令人驚歎。所以我完全錯過了這個觀點，畢竟它很簡單：D非常感謝你sclv。這是一個有趣的技巧要知道。 –

這是[deepseq]（http://hackage.haskell.org/package/deepseq）軟件包的優點之一嗎？ –

@Antal：我不喜歡使用deepseq，因爲它是一個鈍器。例如，在這種情況下，您只需強制列表的脊椎。 Deepseq也強制使用這些值。它相對便宜，因爲它們本質上已經被迫，但是成本很低，如果你將其乘以列表的長度和遞歸調用的數量，它就會相加。如果你急着想，Deepseq很好，但我認爲如果可能的話，以最佳方式混合懶惰和嚴謹，強迫它在操作上更合理，而不是無差別。 – sclv

難以理解的Haskell內存分配行爲

回答

相關問題