haskell - LPath 的 Haskell 实现中是否存在空间泄漏？

Question

为了好玩，我尝试编写一个朴素最长路径算法的实现(用于查找循环图中最长非循环路径的长度)。我从命令式算法的直接移植开始，该算法工作且性能相当好。

data Route = Route {dest:: !Int32, cost:: !Int32}

type Node = [Route]

lPathImperative :: V.Vector Node -> Int32 -> UMV.IOVector Bool -> IO (Int32)
lPathImperative !nodes !nodeID !visited = do
  UMV.write visited (fromIntegral nodeID) True
  max <- newIORef 0
  Prelude.mapM_  (\ Route{dest, cost} -> do
         isVisited <- UMV.read visited (fromIntegral dest)
         case isVisited of
           True -> return ()
           False -> do
               dist <- fmap (+ cost) $ lPathImperative nodes dest visited
               maxVal <- readIORef max
               if dist > maxVal then writeIORef max dist else return ())
     (nodes V.! (fromIntegral nodeID))
  UMV.write visited (fromIntegral nodeID) False
  readIORef max

其中visited是一个未装箱的可变 bool 向量，表示图中的每个节点当前是否已被访问，全部初始化为false，并且节点是节点的向量..

然后，我尝试通过将 max 作为在折叠中传递的值(而不是作为 IORef)来使其更加实用，如下所示:

lPathFun :: V.Vector Node -> Int32 -> UMV.IOVector Bool -> IO (Int32)
lPathFun !nodes !nodeID !visited = do
  UMV.write visited (fromIntegral nodeID) True
  let max = CM.foldM acc (0::Int32) (nodes V.! (fromIntegral nodeID))
  UMV.write visited (fromIntegral nodeID) False
  max
    where
      acc :: Int32 -> Route -> IO (Int32)
      acc maxDist Route{dest,cost}  = do
          isVisited <- UMV.read visited (fromIntegral dest)
          case isVisited of
            True -> return maxDist
            False -> do
              dist <- fmap (+ cost) $ lPathFun nodes dest visited
              return $ if dist > maxDist then dist else maxDist

但是这个版本无法完成，运行了几分钟(另一个版本花了几秒钟来处理相同的输入)，然后因内存不足(请求 1048576 字节)而死掉。如果有人可以查看我的 lPathFun 代码并看看我做错了什么，我将不胜感激。我尝试过让其中的所有内容变得严格，但这并没有帮助，也尝试让所有内容变得懒惰，没有任何改变。我什至尝试将 type node 更改为 V.Vector route 并在其上使用严格的 foldM'，但无济于事。

我怀疑问题是空间泄漏。这是因为我尝试将 lPathFun 翻译成 OCaml 并且效果很好(OCaml 版本使用手动递归这一事实应该不会产生影响:我的函数式 Haskell 版本最初也使用手动递归，但遭受了与使用 FoldM 相同的问题):

type route = {dest: int; cost: int}
type node = route array

let rec lPathFun (nodes: node array) nodeID visited =
  visited.(nodeID) <- true;
  let rec loop i maxDist =
    if i < 0 then maxDist
    else
      let neighbour = nodes.(nodeID).(i) in
      if (not visited.(neighbour.dest))
      then
        let dist = neighbour.cost + lPathFun nodes neighbour.dest visited in
        let newMax = if dist > maxDist then dist else maxDist in
        loop (i-1) newMax
      else
        loop (i-1) maxDist in
  let (max: int) = loop (Array.length nodes.(nodeID) - 1) 0 in
  visited.(nodeID) <- false;
  max;;

我使用的 GHC 版本是 7.8.3。

Answer 1

let max = ... 在这里看起来很可疑:

lPathFun !nodes !nodeID !visited = do
  UMV.write visited (fromIntegral nodeID) True
  let max = CM.foldM acc (0::Int32) (nodes V.! (fromIntegral nodeID))
  UMV.write visited (fromIntegral nodeID) False
  max

您的代码相当于:

  UMV.write ... True
  UMV.write ... False
  CM.foldM acc ...

但我确定你想要:

  UMV.write visited ... True
  max <- CM.foldM ...
  UMV.write visited ... False
  return max