4

连续几天我一直在抨击 Haskell 空间泄漏（自然是堆栈溢出类型）。这令人沮丧，因为我试图直接从 CLR 模仿 BFS 算法，这不是自然递归的。注意：我已经启用了 BangPatterns，并且我在每个可能去的地方都放了一个 bang，试图对这个问题进行分支和绑定，但没有任何效果。我以前曾与空间泄漏作斗争，我不愿意放弃并为此而哭泣寻求帮助，但此时我被卡住了。我喜欢在 Haskell 中编码，并且非常了解函数式编程的禅宗，但调试空间泄漏与在满是图钉的地板上滚来滚去一样有趣。

也就是说，我的问题似乎是典型的“蓄能器”类型的空间泄漏。在下面的代码中，堆栈显然是围绕对 bfs' 的调用而建立的。非常感谢任何空间泄漏的提示。

import qualified Data.Map as M
import qualified Data.IntSet as IS
import qualified Data.Sequence as S
import qualified Data.List as DL

data BfsColor = White | Gray | Black deriving Show
data Node =
Node {
  neighbors :: !IS.IntSet,
  color     :: !BfsColor,
  depth     :: !Int
   }

type NodeID = Int
type NodeQueue = S.Seq NodeID
type Graph = M.Map NodeID Node

bfs :: Graph -> NodeID -> Graph
bfs graph start_node =
  bfs' (S.singleton start_node) graph

bfs' :: NodeQueue -> Graph -> Graph
bfs' !queue !graph
  | S.null queue = graph
  | otherwise =
  let (u,q1) = pop_left queue
      Node children _ n = graph M.! u
      (g2,q2) = IS.fold (enqueue_child_at_depth $ n+1) (graph,q1) children
      g3 = set_color u Black g2
  in bfs' q2 g3

enqueue_child_at_depth :: Int -> NodeID -> (Graph, NodeQueue)
                                        -> (Graph, NodeQueue)
enqueue_child_at_depth depth child (graph,!queue)  =
  case get_color child graph of
    White     -> (set_color child Gray $ set_depth child depth graph,
                   queue S.|> child)
    otherwise -> (graph,queue)

pop_left :: NodeQueue -> (NodeID, NodeQueue)
pop_left queue =
  let (a,b) = S.splitAt 1 queue
  in (a `S.index` 0, b)

set_color :: NodeID -> BfsColor -> Graph -> Graph
set_color node_id c graph =
  M.adjust (\node -> node{color=c}) node_id graph

get_color :: NodeID -> Graph -> BfsColor
get_color node_id graph = color $ graph M.! node_id

set_depth :: NodeID -> Int -> Graph -> Graph
set_depth node_id d graph =
  M.adjust (\node -> node{depth=d}) node_id graph
4

2 回答 2

3

这看起来更容易理解。（不过，您仍然可以将代码缩小 1/2。）

现在，空间泄漏的性质变得明显。也就是说，从未评估过的一件事是深度。它会堆积成一个大大的表情1+1+...。您可以删除所有的爆炸模式并添加一个单一的

enqueue_child_at_depth !depth child (graph,queue)

摆脱空间泄漏。

（进一步的代码提示：您可以将 替换为IS.IntSet一个简单的列表。队列最好按照

go depth qs graph = case viewl qs of
    EmptyL  -> graph
    q :< qs ->
        let
            qs' = (qs ><) . Seq.fromList
                . filter (\q -> isWhite q graph)
                . neighbors q $ graph
        in ...

)

于 2011-04-16T13:48:29.030 回答
0

首先，如果你能提供一些简单的测试用例（以代码的形式）来演示这个东西是如何堆栈溢出的，那将会非常有帮助。没有它，我个人只能推测原因。

作为一种猜测：是否IS.fold足够严格？好吧，例如以下最简单的代码堆栈也会溢出（带有 -O2 的 GHC）：

{-# LANGUAGE BangPatterns #-}
import qualified Data.IntSet as IS

test s = IS.fold it 1 s
    where it !e !s = s+e

main = print $ test (IS.fromList [1..1000000])

这段代码的溢出问题可以像这样被hackafixed（有更好的方法吗？）：

test s = foldl' it 1 (IS.toList s)
    where it !e !s = s+e

也许你也想看看IS.fold你的代码。

于 2011-04-16T09:59:58.380 回答