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+...ます。あなたはすべての強打パターンを削除し、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])

このコードのオーバーフローの問題は、次のようにハック修正できます (より良い方法はありますか?)。

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

IS.foldたぶん、あなたのコードでも見たいと思うでしょう。

于 2011-04-16T09:59:58.380 に答える