用盡Haskell的內存回憶

Question

昨天我終於決定開始學習Haskell了。我開始通過教程進行掃描，但很快決定實際練習會更有益。因此，我開始將我的python腳本移植到Haskell中。令我驚訝的是，它實際上工作和生成的值匹配的蟒蛇。

我意識到實施可能是絕對可怕的。可怕的性能不足並不會讓我感到困擾，但讓我困擾的是，當我試圖長時間運行模擬時，我一直在用盡內存。這是因爲執行本身是有缺陷的，還是可以使其工作？我試圖用三種不同的方法構建主循環：「迭代」，一個遞歸函數（我讀了關於尾遞歸，但沒有設法使它工作）和一個更實驗性的遞歸函數。有問題的功能被命名爲模擬，測試和TEST2。我用選項「-O2」編譯程序。

爲什麼程序內存不足，我該怎麼做才能避免這種情況？

代碼

不那麼重要的部分：

import System.Environment 
import Data.List (tails) 
import System.CPUTime 
import Text.Printf 
import Control.Exception 

gConst = 6.674e-11 

data Vector = Vector2D Double Double | Vector3D Double Double Double deriving (Show) 
deltaVector :: Vector -> Vector -> Vector 
deltaVector (Vector2D x1 y1) (Vector2D x2 y2) = Vector2D (x2 - x1) (y2 - y1) 
deltaVector (Vector3D x1 y1 z1) (Vector3D x2 y2 z2) = Vector3D (x2 - x1) (y2 - y1) (z2 - z1) 

data Position = Position Vector deriving (Show) 
data Velocity = Velocity Vector deriving (Show) 

distance2DSquared (Vector2D deltaX deltaY) = deltaX ** 2 + deltaY ** 2 
distance3DSquared (Vector3D deltaX deltaY deltaZ) = (distance2DSquared $ Vector2D deltaX deltaY) + deltaZ ** 2 
distance vector = sqrt (distance3DSquared $ vector) 

force vector mass1 mass2 = gConst * (mass1 * mass2)/(distance3DSquared vector) 
acceleration force mass = force/mass 

vectorComponentDivide (Vector2D x y) c = Vector2D (x/c) (y/c) 
vectorComponentDivide (Vector3D x y z) c = Vector3D (x/c) (y/c) (z/c) 

vectorComponentMultiply (Vector2D x y) c = Vector2D (x*c) (y*c) 
vectorComponentMultiply (Vector3D x y z) c = Vector3D (x*c) (y*c) (z*c) 

vectorComponentAdd (Vector2D x1 y1) (Vector2D x2 y2) = Vector2D (x1+x2) (y1+y2) 
vectorComponentAdd (Vector3D x1 y1 z1) (Vector3D x2 y2 z2) = Vector3D (x1+x2) (y1+y2) (z1+z2) 

invertedVector (Vector2D x1 y1) = Vector2D (-x1) (-y1) 
invertedVector (Vector3D x1 y1 z1) = Vector3D (-x1) (-y1) (-z1) 

normalizedVector :: Vector -> Vector 
normalizedVector vector = vectorComponentDivide vector $ distance vector 

velocity vel0 mass1 mass2 vector deltaT = 
    vectorComponentMultiply (vectorComponentAdd vel0 (vectorComponentMultiply (normalizedVector vector) (acceleration (force vector mass1 mass2) mass1))) deltaT 

data Actor = Actor String Vector Vector Double deriving (Show) 

earth = Actor "Object1" (Vector3D 0 0 0) (Vector3D 0 0 0) 10 
moon = Actor "Object2" (Vector3D 10 0 0) (Vector3D 0 0 0) 10 

actors = [earth, moon] 

combinations :: Int -> [a] -> [[a]] 
combinations 0 _ = [ [] ] 
combinations n xs = [ y:ys | y:xs' <- tails xs 
          , ys <- combinations (n-1) xs'] 

updateVelocity [(Actor name1 position1 velocity1 mass1),(Actor name2 position2 velocity2 mass2)] = 
    [(Actor name1 position1 a mass1),(Actor name2 position2 b mass2)] 
    where a = velocity velocity1 mass1 mass2 vector deltaT 
      b = velocity velocity2 mass2 mass1 (invertedVector vector) deltaT 
      vector = deltaVector position1 position2 
      deltaT = 1 

updatePosition [(Actor name1 position1 velocity1 mass1),(Actor name2 position2 velocity2 mass2)] = 
     [Actor name1 (vectorComponentAdd position1 velocity1) velocity1 mass1, Actor name2 (vectorComponentAdd position2 velocity2) velocity2 mass2] 

相關部分：

update list = map updatePosition (map updateVelocity list) 


simulation state n = do 
    if n == 0 
     then do 
      print state 
      return() 
     else do 
      let newState = update state 
      simulation newState $! (n-1) 

test list n = iterate update list !! n 

test2 list 0 = list 
test2 list n = (test2 (update list) (n-1)) 

time :: IO t -> IO t 
time a = do 
    start <- getCPUTime 
    v <- a 
    end <- getCPUTime 
    let diff = (fromIntegral (end - start))/(10^12) 
    printf "Computation time: %0.3f sec\n" (diff :: Double) 
    return v 

main :: IO() 
main = do 
    let combo = combinations 2 actors 
    putStrLn "Hello World!" 
    let n = 1000000 
    print n 
    --time $ print (test combo n) 
    time $ simulation combo n 
    _ <- getLine 
    putStrLn "BAI" 

Answer 1

相信懶惰害你的代碼：你的代碼生成大的thunk（未計算表達式），這導致到OOM。

例如，iterate是（以）導致大的thunk而聞名，當您訪問中間的結果列表時，無需強制以前的列表元素。更確切地說

iterate f x !! n 

是不好的，因爲它會真的執行任何工作前建立表達f (f (f ...(f x)))。我們希望在訪問下一個元素之前評估每個列表元素。這可能是穹頂自定義!!功能：

(!!!) :: [a] -> Int -> a 
[]  !!! _ = error "!!!: out of range" 
(x:_) !!! 0 = x 
(x:xs) !!! n = seq x (xs !!! pred n) 

現在我們可以使用iterate f a !!! n沒有大的thunk建立。

這有同樣的問題：

simulation state n = do 
    if n == 0 
     then do 
      print state 
      return() 
     else do 
      let newState = update state 
      simulation newState $! (n-1) 

將建設大型update (update (update ...))的thunk不加評估了。一個可能的修復可能是

  ... 
      (simulation $! newState) $! (n-1) 

但是，請記住，你的情況是newState名單（名單！）。在這種情況下，seq或$!只會根據其第一個單元格構造函數要求對列表進行評估 - 僅足以檢查列表是否爲空。這種「強迫」可能已經足夠或者不適合你的目的。

有一個名爲deepSeq的庫函數，這將迫使完整列表，如果真的需要（用Hoogle找到文檔）。

總結：懶惰的評價有它的好處和其缺點。它通常允許更高的效率，例如有時提供恆定的空間列表處理，而不需要編寫精心設計的功能。它還允許無限列表技巧，這是很方便的。但是，它也可能導致不必要的thunk過長時間，浪費記憶。所以，在這些情況下，程序員有一些負擔。特別是當用於嚴格語義學的時候，這些問題起初可能會讓人感到害怕（我們去過那裏！）。您的代碼