1

Haskellで接続されたすべてのサブグラフを見つける問題を解決しようとしています。使用するアルゴリズムについては、こちらで説明しています。その論文からの引用：

すべてのパス アルゴリズムと同様に、前進ステップと後退ステップがあります。与えられた接続されたサブグラフがエッジ k の追加によって拡張できる場合、つまり、エッジ k がまだ与えられたサブグラフの一部ではない場合、k が与えられたサブグラフの少なくとも 1 つのエッジに隣接している場合、さらに次の場合にステップ フォワードが行われます。のエッジ k は、以下に示すいくつかの制限によって禁止されていません。指定された接続されたサブグラフをそれ以上引き伸ばすことができなくなるとすぐに、ステップ バックが実行されます。この場合、最後に追加されたエッジが文字列から削除され、一時的に「禁止」ステータスが与えられ、以前の長い文字列からのバックトラックによって禁止された他のエッジが同時に再び「許可」されます。対照的に、現在のものよりも短い文字列から削除することによって禁止されているエッジは、禁止されたままです。

このアルゴリズムを実行するために、グラフをエッジのリストとして表しました。

 type Edge =  (Int,Int)
 type Graph = [Edge]

まず、addEdgeグラフを拡張できるかどうかを確認し、不可能な場合は返すNothingか、拡張する関数を作成しEdgeました。

私は"parent"グラフとグラフを持っているので、グラフに存在し、グラフに接続され、グラフにまだ含まれておらず、セットに含まれていない"extensible"エッジを1つだけ見つけようとします。 "parent""extensible""extensible"forbidden

この関数を以下に書きました。

addEdge :: Graph -> Graph -> [Edge] -> Maybe Edge
addEdge !parent !extensible !forb = listToMaybe $ intersectBy (\ (i,j) (k,l) -> (i == k || i == l || j == k || j == l)) (parent \\ (extensible `union` forb)) extensible

仕事だ！しかし、プログラム全体のプロファイリングからわかるようにaddEdge、最も重い関数です。私のコードが最適ではないことは確かです。少なくとも、 intersectBy考えられるすべての解を見つける関数ですが、必要なのは 1 つだけです。このコードをより速くする方法はありますか? たぶん、標準のリストを使用しないでくださいSet from Data.Set。まず注目ポイントです。

以下に示す主な再帰関数ext:

ext :: Graph -> [Graph] -> Maybe Graph -> [(Edge,Int)] -> Int -> [Graph]
ext !main !list !grow !forb !maxLength      | isEnd  == True = (filter (\g -> (length g /= 1)) list) ++ (group main) 
                                            | ((addEdge main workGraph forbEdges) == Nothing) || (length workGraph) >= maxLength = ext main list (Just workGraph) forbProcess maxLength
                                            | otherwise = ext main ((addedEdge:workGraph):list) Nothing forb  maxLength where 
                                                workGraph = if grow == Nothing then (head list) else (bite (fromJust grow)) -- [Edge] graph now proceeded
                                                workGraphLength = length workGraph
                                                addedEdge = fromJust  $ addEdge'
                                                addEdge' = addEdge main workGraph forbEdges
                                                bite xz = if (length xz == 1) then (fromJust (addEdge main xz forbEdges)):[] else tail xz 
                                                forbProcess = (head workGraph,workGraphLength):(filter ((<=workGraphLength).snd) forb)
                                                forbEdges = map fst forb -- convert from (Edge,Level) to [Edge]                     
                                                isEnd = (grow /= Nothing) && (length (fromJust grow) == 1) && ((addEdge main (fromJust grow) forbEdges) == Nothing)

グラフでプログラムをテストします

c60 = [(1,4),(1,3),(1,2),(2,6),(2,5),(3,10),(3,7),(4,24),(4,21),(5,8),(5,7),(6,28),(6,25),
    (7,9),(8,11),(8,12),(9,16),(9,13),(10,20),(10,17),(11,14),(11,13),(12,28),(12,30),(13,15),
    (14,43),(14,30),(15,44),(15,18),(16,18),(16,17),(17,19),(18,47),(19,48),(19,22),(20,22),(20,21),
    (21,23),(22,31),(23,32),(23,26),(24,26),(24,25),(25,27),(26,35),(27,36),(27,29),(28,29),(29,39),
    (30,40),(31,32),(31,33),(32,34),(33,50),(33,55),(34,37),(34,55),(35,36),(35,37),(36,38),(37,57),
    (38,41),(38,57),(39,40),(39,41),(40,42),(41,59),(42,45),(42,59),(43,44),(43,45),(44,46),(45,51),
    (46,49),(46,51),(47,48),(47,49),(48,50),(49,53),(50,53),(51,52),(52,60),(52,54),(53,54),(54,56),(55,56),(56,58),(57,58),(58,60),(59,60)] :: Graph

たとえば、長さが 1 ～ 7 のサブグラフをすべて検索します。

length $ ext c60 [[(1,2)]] Nothing [] 7
>102332

問題は計算速度が遅すぎることです。元の記事で指摘したように、プログラムはFORTRAN 77150MHz ワークステーションで作成および起動され、最新の i5 プロセッサで私のコードよりも少なくとも 30 倍速くテスト タスクを実行します。理解できません。なぜ私のプログラムはこんなに遅いのですか? このコードをリファクタリングする方法はありますか? または、C に移植し、FFI 経由で C ライブラリにバインディングを書き込むのが最善の解決策ですか?

4

2 に答える 2

2

を使用して、論文に記載されているアルゴリズムを実装することにしましたfgl。完全なコードは次のとおりです。

{-# LANGUAGE NoMonomorphismRestriction #-}

import Data.Graph.Inductive
import Data.List
import Data.Tree

uniq = map head . group . sort . map (\(a, b) -> (min a b, max a b))
delEdgeLU (from, to) = delEdge (from, to) . delEdge (to, from)
insEdgeDU (from, to) = insEdge (from, to, ()) . insNodeU to . insNodeU from where
    insNodeU n g = if gelem n g then g else insNode (n, ()) g

nextEdges subgraph remaining
    | isEmpty subgraph = uniq (edges remaining)
    | otherwise = uniq $ do
        n  <- nodes subgraph
        n' <- suc remaining n
        return (n, n')

search_ subgraph remaining
    = Node subgraph
    . snd . mapAccumL step remaining
    $ nextEdges subgraph remaining
    where
    step r e = let r' = delEdgeLU e r in (r', search_ (insEdgeDU e subgraph) r')

search = search_ empty

mkUUGraph :: [(Int, Int)] -> Gr () ()
mkUUGraph es = mkUGraph ns (es ++ map swap es) where
    ns = nub (map fst es ++ map snd es)
    swap (a, b) = (b, a)

-- the one from the paper
sampleGraph = mkUUGraph cPaper
cPaper = [(1, 2), (1, 5), (1, 6), (2, 3), (3, 4), (4, 5)]

トップレベルで使用したい関数はmkUUGraph、エッジのリストからグラフを構築する とsearch、ノードがその入力の接続されたサブグラフであるツリーを構築する です。たとえば、論文の「Scheme 1」の下部に示されている統計を計算するには、次のようにします。

*Main> map length . tail . levels . search . mkUUGraph $ [(1, 2), (1, 5), (1, 6), (2, 3), (3, 4), (4, 5)]
[6,7,8,9,6,1]
*Main> sum it
37

のすべての引数が何をすべきかを理解していないため、実装と比較するのに少し苦労しましたext。ext特に、 37 の結果が得られるように論文の隣接グラフを呼び出す方法がわかりませんでした。おそらく、バグがあります。

いずれにせよ、私はあなたのコードがやろうとしていることをエミュレートするために最善を尽くしました: 最大 7 つのエッジを持つグラフを見つけ、確かにエッジを含みます(1, 2)(あなたのコードは を含まない多くのグラフを出力するという事実にもかかわらず(1, 2))。このコードを追加しました：

mainHim = print . length $ ext c60 [[(1,2)]] Nothing [] 7
mainMe  = print . length . concat . take 7 . levels $ search_ (mkUUGraph [(1,2)]) (mkUUGraph c60)

私のコードは 3301 のそのようなグラフを見つけます。あなたのものは 35571 を見つけました。私はその不一致がどこから来たのかを理解するのに一生懸命努力しませんでした。ghci では、mainHim36.45 秒かかります。mainMe0.13秒かかります。でコンパイルすると-O2、mainHim4.65 秒かかります。mainMe0.05秒かかります。の数は、デフォルトのものではなくグラフの実装mainMeを使用することで再び半分に減らすことができ、おそらくプロファイリングといくつかの考えでさらに減らすことができます. PatriciaTree理由mainMeが非常に速いのは、非常に少ないグラフを見つけるためである場合に備えて、変更mainしたものもテストしました。

main = print . length . concat . take 8 . levels $ (search (mkUUGraph c60) :: Tree (Gr () ()))

これにより 35853 が出力されるため、テスト コマンドとほぼ同じ数のグラフが検出されます。でコンパイルすると、ghci で 0.72 秒、0.38 秒かかります-O2。

于 2013-09-30T09:58:03.420 に答える
0

または、C に移植し、FFI 経由で C ライブラリにバインディングを書き込むのが最善の解決策ですか?

いいえ、C で書く必要はありません。GHC によって生成されたコードは、C よりもそれほど遅くはありません。この大きな速度の違いは、別のアルゴリズムを実装していることを示唆しています。したがって、別の言語で書き直す代わりに、Haskell コードを書き直す必要があります。

あなたのコードの問題は、あなたが...

  1. セットの代わりにリストを使用する
  2. 深さ優先列挙の代わりに幅優先を使用します (不明)
  3. どのエッジがどのセットに含まれているかを巧みに追跡するのではなく、エッジのセット全体に対して操作を使用する
  4. 再帰呼び出しを使用する代わりに、アルゴリズムの再帰構造を手動でエンコードします。

私はあなたのコードを完全には理解していないことを認めなければなりません。しかし、リンク先の論文を読みましたが、そこで説明されているアルゴリズムは、すべての結果の単純な力ずくの列挙のようです。したがって、Haskell の実装ではリスト モナド (またはリスト内包表記) を使用してすべてのサブグラフを列挙し、列挙中に接続されていないサブグラフを除外する必要があると思います。これまでにリスト モナドを使ってコードを書いたことがない場合は、すべてのサブグラフを列挙するだけで良い出発点になるかもしれません。

于 2013-09-29T09:56:43.247 に答える