为什么 putStrLn 每次迭代都会变慢?
Why does putStrLn slow down with each iteration?
我制作了一个生命游戏小程序,它可以自行迭代几代人。问题是每次迭代时,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"
我最初预计由于某种原因每个新的生成也计算所有前几代,但似乎并非如此。如果是这种情况,我希望 evolution 函数的计算时间会增加,而不是 putStrLn 函数打印缓慢。关于是什么让每一代的 putStrLn 函数变慢这么多,有什么想法吗?
(免责声明:这只是一个猜测,我可能是错的。我没有 运行 实验来证实这一点。)
这是使用函数表示网格所付出的代价
type Generation = Position -> CellState
这是一种表示状态的优雅方式,但在较长的 运行 中效率不高。当你的算法 运行s 时,它会创建很多闭包:
generation0 = \position -> ....
generation1 = \position -> .... use generation0
generation2 = \position -> .... use generation1
generation3 = \position -> .... use generation2
...
即使你只需要最后一代,所有上一代的数据仍然保留在内存中,因为它被上一代(间接)使用。因此,您永远不会释放内存,这已经很糟糕了。
更糟糕的是,每次你使用生成N
,这将调用生成N-1
多次(8),这又将调用生成N-2
多次(8),以此类推,直到第 0
代。这会导致指数爆炸。
要解决此问题,您需要将数据表示更改为更高效的形式。我认为一些类似矩阵的类型可以工作。
我制作了一个生命游戏小程序,它可以自行迭代几代人。问题是每次迭代时,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"
我最初预计由于某种原因每个新的生成也计算所有前几代,但似乎并非如此。如果是这种情况,我希望 evolution 函数的计算时间会增加,而不是 putStrLn 函数打印缓慢。关于是什么让每一代的 putStrLn 函数变慢这么多,有什么想法吗?
(免责声明:这只是一个猜测,我可能是错的。我没有 运行 实验来证实这一点。)
这是使用函数表示网格所付出的代价
type Generation = Position -> CellState
这是一种表示状态的优雅方式,但在较长的 运行 中效率不高。当你的算法 运行s 时,它会创建很多闭包:
generation0 = \position -> ....
generation1 = \position -> .... use generation0
generation2 = \position -> .... use generation1
generation3 = \position -> .... use generation2
...
即使你只需要最后一代,所有上一代的数据仍然保留在内存中,因为它被上一代(间接)使用。因此,您永远不会释放内存,这已经很糟糕了。
更糟糕的是,每次你使用生成N
,这将调用生成N-1
多次(8),这又将调用生成N-2
多次(8),以此类推,直到第 0
代。这会导致指数爆炸。
要解决此问题,您需要将数据表示更改为更高效的形式。我认为一些类似矩阵的类型可以工作。