在Haskell中从BFS输出重构一个图

Question

在Haskell中从BFS输出重构一个图

8

我希望在Haskell中重构一个图的发生结构，该结构由其广度优先遍历的输出给出。明确地说，输出包括一个根节点和一个邻域列表（邻域是一个标记为新或旧（=已访问）的顶点列表），其中每个邻域对应于尚未分配到邻域的最小顶点。

在任何命令式语言中，我会使用队列来解决这个问题：

Input: root vertex r, list of neighborhoods L
(1) Put r into the empty queue Q
(2) if Q is empty then STOP
(3) extract the first vertex v of Q
(4) extract the first neighborhood N of L
(5) append the unvisited vertices of N to Q
(6) remove the markings (new/old) of the nodes of N and assign v to N
(7) goto (2)

我尝试在Haskell中实现这个朴素算法（使用列表或使用Data.Sequence作为队列），但是ghci总是会用光内存。这不应该发生，因为虽然输入由300MB数据组成，但16GB的RAM显然足够。

因此，朴素实现似乎导致了内存泄漏。你会如何在Haskell中实现这个算法？

编辑： 这里是我使用的（稍微简化的）数据类型：

data Output = Out !Vertex ![[BFSNode]]
data Vertex = Vertex Integer SomeMoreComplexData
data BFSNode = New Vertex | Old Integer

data Graph = ![Vertex] ![(Integer,[Integer])]

数据类型“Output”包含已解析的BFS输出，包括根顶点和邻域列表。BFSNode对应于BFS树中的一个节点，该节点属于新访问的顶点之一，或者属于已经被访问过并因此由其唯一编号引用的旧顶点。请注意，解析过程工作正常且消耗的内存很少。

我的目标是将“Output”转换为数据类型“Graph”，它由顶点列表和关联列表组成。

以下是我实现的简化版本：

readTree :: [[BFSNode]] -> Seq Integer -> Graph
readTree [] _ = Graph [] []
readTree (nb:nbs) qs =
    let (i :< qs') = viewl qs
        newVs = fromList $! map nodeNr . filter isNew $ nb
        (Graph vs adj) = readTree nbs $ qs' >< newVs
    in  Graph (map unNew (filter isNew nb) ++ vs) ((i,nub $ map nodeNr nb):adj)

"nbs"是邻居列表，"qs"是队列。函数"nodeNr"从顶点中提取唯一标识号，"isNew"测试顶点是否为新的，"unNew"从数据类型"BFSNode"中解压新的顶点。 编辑2：我现在认为我已经定位了问题所在。也许这与我的转换过程实现无关。我的失败之处在于使用内置函数"read"从文件中读取数据类型"Output"。我现在意识到，Haskell在读取大文件时存在问题。即使只是读取整数列表，例如。

main = do 
    txt <- readFile "test"
    writeFile "test2" . show $ (read txt :: [Integer]) }

如果文件“test”足够大，程序将耗尽内存。我现在明白了，这种解析数据的方式不好，因为“read”会在显示任何输出之前将所有数据加载到内存中，但我仍然不明白为什么它会占用16GB的RAM，即使文件数量还不到500MB。你有没有想过“read”出了什么问题？在你的机器上Haskell是否表现出相同的行为？

编辑3：现在我实现了一个基于流的解析函数“readOutput”，它接受一个字符串并返回数据类型“Output”。这个函数是惰性的，所以当我调用它时，我立即得到一个输出。但是当我将它与我的转换函数“readTree”组合时（这显然是尾递归的），我根本没有得到任何输出，并且内存使用量像往常一样增加。我做错了什么？

编辑4：编辑3中的问题来自某些强制执行，我现在已经删除了它们。

- Dune

4

关于你已经有的简单实现：尝试使用ghc -O2编译它，而不是使用GHCi。 - gspr

2

值得注意的是，对于Sequence的叶子节点添加一些严格性是值得的，例如确保在进入队列之前所有数据都被完全评估。一个顶点的实现是什么？它可以被取消装箱/强制执行吗？ - daniel gratzer

2

有没有办法查看一些测试数据/代码的子集？这样更容易进行优化。 - daniel gratzer

@gspr：感谢您的快速回复！不幸的是，使用-O2编译并没有改变任何东西。 - Dune

@jozefg：在将顶点添加到队列之前，严格化顶点似乎是一个好主意，因为现在内存使用率增长得更慢了，但仍然会出现内存不足的情况。我将尝试添加更多相关信息。 - Dune

1个回答

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

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

- David M. Rogers · Accepted Answer

这个问题没有指定一个关键因素——在Haskell中，图将如何表示？函数式程序需要仔细考虑数据结构以最大化共享和运行效率。通常，这意味着它们从无（归纳）递归地构建。有一篇论文介绍了一个表示方法：归纳图和函数式图算法。

module Test where

data Graph a = Empty | Extension (Graph a) [Int] (Int, a)
               deriving Show

也就是说，图表可以是Empty，或通过添加一个节点的方式成为（规模更小的）图表。这正是函数式语言中使用 Cons 构建列表的方式，只不过附加节点必须指定较小的图表、前身链接([Int])、新节点号和数据(Int,a)。请注意，他们出于效率原因将其实现为抽象类型。

可以通过扩展空图来生成一个具有一个节点的图。

singleton :: (Int,a) -> Graph a
singleton x = Extension Empty [] x

使用这种结构，定义递归解析算法对于您的BFS树来说是非常简单的。

data Mark a = Visited Int | New (Int,a) deriving Show

parse :: (Int,a) -> [[Mark a]] -> Graph a
parse x nbrs = extend Empty [x] nbrs

extend :: Graph a -> [(Int,a)] -> [[Mark a]] -> Graph a
extend g [] [] = g
extend g _  [] = Empty -- leftover nodes, really an error.
extend g [] _  = Empty -- leftover neighborhoods, really an error.
extend g (x : tl) (nbr : nbrs) =
  extend (Extension g (seen nbr) x) (news tl nbr) nbrs

news :: [(Int,a)] -> [Mark a] -> [(Int,a)]
news l (New x : tl) = news (uniq l x) tl
news l (_ : tl) = news l tl
news l [] = l

uniq :: [(Int,a)] -> (Int,a) -> [(Int,a)]
uniq (x:tl) y = x : if (fst x == fst y) then tl else uniq tl y
uniq [] y = [y]

seen :: [Mark a] -> [Int]
seen (Visited i : tl) = i : seen tl
seen (_ : tl) = seen tl
seen [] = []

m0 = [New (1,())]
m1 = [Visited 0, New (2,()), New (3,())]
m2 = [Visited 1, New (3,())]
m3 = [Visited 1, Visited 2]    
nbrs = [m0,m1,m2,m3]

测试一下，

$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :load Test
[1 of 1] Compiling Test             ( Test.hs, interpreted )
Ok, modules loaded: Test.
*Test> parse (0,()) nbrs
Extension (Extension (Extension (Extension Empty [] (0,())) [0] (1,())) [1] (2,())) [1,2] (3,())

为了提高效率，您可以采取以下措施：

将news和seen函数合并为let (ns,sn) = newseen nbr ([],[])并使其成为尾递归函数（传递它们部分构造的列表并立即返回），以提高效率。
您的输入可以跟踪每个邻居列表中心的节点。这将避免在邻居堆栈中进行列表连接。或者，您可以使用函数式双端队列来保存该堆栈。

如果您还没有看过的话，我建议您阅读Okasaki关于纯函数数据结构的书籍。