1

2 つの幅優先探索アルゴリズムの実行時間の違いを比較しています。平行と非平行。しかし、私が作成するすべてのグラフについて、非並列バージョンは並列バージョンよりも 10 倍高速です。

これは並列幅優先検索です。どこに問題があるのか​​ わかりませんが、この方法のどこかにあると思います：

public static int PBFS(Node start, Node end)
{
    var queue = new ConcurrentQueue<Node>();
    queue.Enqueue(start);

    while (queue.Count != 0)
    {
        bool isFinished = false;
        if (isFinished) break;

        Parallel.ForEach<Node>(queue, CurrentNode =>
        {
            if (queue.TryDequeue(out CurrentNode))
            {
                foreach (Node Child in CurrentNode.Children.Keys)
                {
                    if (Child.IsVisited == false)
                    {
                        Child.IsVisited = true; 
                        if (Child == end) { isFinished = true; return; }
                    }
                    queue.Enqueue(Child);
                }
            }  
            return;
        });
    } return 1;
}

これは非並列 BFS です。

public static int BFS(Node start, Node end)
{
    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(start);

    while (queue.Count != 0)
    {
        Node CurrentNode = queue.Dequeue();
        CurrentNode.IsVisited = true;

        foreach (Node Child in CurrentNode.Children.Keys)
        {
            if (Child.IsVisited == false)
            {
                Child.IsVisited = true;
                //Console.Write(Child.Name+" ");
                if (Child == end) return 1;
            }
            queue.Enqueue(Child);
        }
        // Console.WriteLine();
    }

    // Console.WriteLine();
    return 0;
}
4

2 に答える 2

3

共有データの並列化と同時実行には同期が必要です。同期にはコストがかかります。おそらくご覧のとおりです。 ConcurrentQueue独自の同期があり、状況に最適ではない可能性があります。

CPU の数を超えた並列化 (ここでは発生しない可能性がありますが、関連性があります) は、多くのコンテキスト スイッチを発生させます。これは高価であり、並列で実行されているコードの生産性を低下させます。つまり、問題に対してより多くのスレッドを投入するという前提は、逆の効果を生むことがよくあります。

パフォーマンスが懸念される場合は、別の設計、おそらくActor-based、message-passing、またはProducer/Consumerを検討して、共有データを回避し、その共有データの同期を回避することをお勧めします。

于 2012-09-06T17:41:11.173 に答える
1

最初に並列双方向 BFS を作成することをお勧めします: 2 つの検索スレッドを作成します。1 つは開始ノードから「矢印」に沿って進み、もう 1 つは目標ノードから開始して逆方向に進み、検索時に両方のスレッドを終了します。フロンティアが「出会う」。たとえば、Java では[this]のようになります。

于 2013-03-27T12:34:02.343 に答える