2

为了好玩，我正在尝试编写朴素最长路径算法的实现（用于查找循环图中最长非循环路径的长度）。我从命令式算法的直接移植开始，该算法运行良好且执行得相当好。

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

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

然后，我尝试使其更具功能性，方法是将其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

但是，此版本无法完成，运行了几分钟（另一个版本为相同的输入需要几秒钟），然后以out of memory (requested 1048576 bytes). 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。

4

1 回答 1

5

这里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
于 2014-11-30T09:45:00.137 回答