为什么每次迭代都会减慢 putStrLn 的速度？

Question

为什么每次迭代都会减慢 putStrLn 的速度？

7

我写了一个小的生命游戏程序，可以自动进行迭代。问题在于，每次迭代时，putStrLn函数的速度会明显变慢，我无法找出原因。以下是代码：

import Control.Concurrent

data CellState = Dead | Alive

data Position = Position Integer Integer

type Generation = Position -> CellState

is_alive :: CellState -> Bool
is_alive Alive = True
is_alive Dead = False

neighbors :: Position -> [Position]
neighbors (Position x y) =
  [(Position (x-1) (y-1)), (Position x (y-1)),  (Position (x+1) (y-1)), (Position (x+1) y),
  (Position (x+1) (y+1)), (Position x (y+1)), (Position (x-1) (y+1)), (Position (x-1) y)]

alive_neighbors :: Generation -> Position -> Int
alive_neighbors generation position = length (filter is_alive (map generation (neighbors position)))

evolution :: Generation -> Generation
evolution generation position =
  case (alive_neighbors generation position) of
  2 -> if (is_alive (generation position)) then Alive else Dead
  3 -> Alive
  _ -> Dead

visualize_generation generation = map (visualize_line generation) [1..10]

visualize_line :: Generation -> Integer -> String
visualize_line generation y = concat (map (visualize_cell generation y) [1..10])

visualize_cell generation y x =
  case (generation (Position x y)) of
  Alive -> ['0']
  Dead -> ['.']

{-
bar (Position 1 2) = Alive
bar (Position 2 3) = Alive
bar (Position 3 3) = Alive
bar (Position 3 2) = Alive
bar (Position 3 1) = Alive
bar (Position x y) = Dead
-}

bar (Position 1 3) = Alive
bar (Position 2 3) = Alive
bar (Position 3 3) = Alive
bar (Position x y) = Dead

life :: Generation -> IO ()
life bar_ = do cls
               mapM_ putStrLn (visualize_generation bar_)
               threadDelay 1000000 
               life (evolution bar_)

cls = putStr "\ESC[2J"

我最初认为每一代新的计算方式都会计算所有之前的计算方式，但似乎并非如此。如果是这样，我期望演化函数的计算时间会增加，而不是putStrLn函数打印得慢。有什么想法可以解释为什么每一代都会导致putStrLn函数变得如此缓慢吗？

- Asgeir Bjelland

问题似乎出在你对“代”的表示上，以及当你多次应用“进化”时会发生什么。你能想象你实际上正在内存中构建什么样的结构吗？ - dfeuer

2

你说：“我最初预期每一代新的计算都会计算所有之前的一代，但似乎并非如此。” 你是如何确定这不是情况的呢？（我认为这种判断存在缺陷--实际上它会多次重新计算之前的一代。） - Daniel Wagner

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chi · Accepted Answer

（免责声明：这只是一个猜测，可能是错误的。我没有运行实验来确认。）

这是以您当前所使用的函数表示网格所需支付的代价。

type Generation = Position -> CellState

这是一种优雅的表示状态的方式，但从长远来看并不是非常高效。当您的算法运行时，会创建许多闭包：

generation0 = \position -> ....
generation1 = \position -> .... use generation0
generation2 = \position -> .... use generation1
generation3 = \position -> .... use generation2
...

即使你只需要最后一代数据，所有前代的数据仍然会保存在内存中，因为它被最后一代（间接地）使用。所以，你永远不会释放已经存在的内存，这是不好的。

更糟糕的是，每次你使用第 N 代时，这将调用第 N-1 代多次（8 次），进而调用第 N-2 代多次（8 次），等等，直到第 0 代。这导致了指数级的增加。

要解决这个问题，你需要改变你的数据表示方式，采用更有效的方式。一些类似于矩阵的类型可能会起作用，我认为。