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

は、グラフ内の各ノードが現在アクセスされているかどうか、すべてが false に初期化されているかどうか、およびnodesvisitedはノードのベクトルであるかどうかを表す、ボックス化されていない bool の可変ベクトルです。

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誰かが私のコードを見て、私が間違っていることを確認できれば幸いです。私はその中のすべてを厳密にしようとしましたが、それは役に立ちませんでした.また、すべてを怠惰にしようとしましたが、変更はありません. 代わりにstrictに変更type nodeして使用しようとしましたが、役に立ちませんでした。V.Vector routefoldM'

問題はスペースリークだと思います。これは、私がlPathFunOCaml に翻訳しようとしたところ、問題なく動作したためです (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 に答える