13

木をすばやく横断する必要があり、並行して実行したいと思います。スレッドの束を手動でスピンアップするよりも、並列拡張機能を使用したいと思います。

私の現在のコードは次のようになります。

   public void Traverse(Node root)
    {
        var nodeQueue = new Queue<Node>();
        nodeQueue.Enqueue(root);
        while (nodeQueue.Count!=0)
        {
            var node = nodeQueue.Dequeue();
            if (node.Property = someValue) DoSomething(node);
            foreach (var node in node.Children)
            {
                nodeQueue.Enqueue(node);
            }
        }
    }

Parallel.ForEachにParallel.Whileアナログがあることを本当に望んでいました。Parallel.ForEachを使用したParallelの実装に関するStephenToubの記事に出くわしました。正しく読み取った場合、反復しようとしているキューを変更しているため、これはまだ機能しません。

タスクファクトリと再帰を使用する必要がありますか（そしてそれは危険ですか？）？または私が見落としているいくつかの簡単な解決策はありますか？

編集：@svick

ツリーには250,000を超えるノードがあります。現在の最大深度は、ルートを含めて14ノードです。

ルートから約500のノードがあり、その後のバランスはかなりランダムに分布しています。私はすぐに分布に関するいくつかのより良い統計を得るでしょう。

@Enigmativity：

はい、ツリーは多くのユーザーによって同時に変更されていますが、通常、ツリーまたはサブツリーの共有読み取りロックを使用するか、ダーティ読み取りを許可します。

node.Childrenへの呼び出しはアトミックと見なすことができます。

DoSomethingは、実際にはいくつかのデリゲートの1つです。一部の高価な操作では、ノードのスナップショットリストを収集し、トラバーサルの外部で処理します。

おそらく一般的なケース（ツリー全体ではなくサブツリーがトラバースされている）を確認する必要があることに気付きました。そのために、ツリーのすべてのノードでトラバースを実行し、合計時間を確認しました。

各トラバーサルアルゴリズムにParallel.ForEach（nodes、Traverse）を使用しました。ここで、ノードには約25万個のノードがすべて含まれていました。これは、多くの異なるノードを同時に要求する多くのユーザーをシミュレートした（一種の）ものです。

00256ms幅優先シーケンシャル

00323ms幅優先探索（作業あり）（静的カウンターを「作業」としてインクリメントしました）

01495msカークス最初の答え

01143msSvicks2番目の回答

00000ms再帰シングルスレッドは60秒後に終了しませんでした

00000ms謎の答えは60秒後に終了しませんでした

@エニグマ、私はあなたのブログをどうにかして台無しにした可能性があると思います。

結果は控えめに言っても私を驚かせた。コンパイラーがトラバーサルを魔法のように最適化していないことを確信するために、幅優先探索にいくつかの作業を追加する必要がありました。

頭を1回トラバースする場合、最初のレベルを並列化すると最高のパフォーマンスしか得られませんでした。しかし、ほんのわずかに、この数は、第2レベルにノードを追加したときに改善されました（500ではなく2000）。

4

5 に答える 5

8

最も直接的な方法は、Task子ノードごとにを作成し、それらすべてを待つことです。

public void Traverse(Node root)
{
    if (node.Property == someValue)
        DoSomething(node);

    var tasks = new List<Task>();

    foreach (var node in node.Children)
    {
        // tmp is necessary because of the way closures close over loop variables
        var tmp = node;
        tasks.Add(Task.Factory.StartNew(() => Traverse(tmp)));
    }

    Task.WaitAll(tasks.ToArray());
}

Taskかなり軽量なので、それらをたくさん作成するとかなりうまくいきます。ただし、オーバーヘッドがいくらかあるため、キューを共有するいくつかのタスクを作成するなど、より複雑な処理を行う方がおそらく高速になります。それがあなたが行く方法であるならば、空のキューがすべての仕事が終わったことを意味しないことを忘れないでください。このようにすると、名前空間のクラスSystem.Collections.Concurrentが便利になります。

編集：ツリーの形状（ルートには約500の子があります）のため、最初のレベルだけを並行して処理すると、優れたパフォーマンスが得られるはずです。

public void Traverse(Node root, bool parallel = true)
{
    if (node.Property == someValue)
        DoSomething(node);

    if (parallel)
    {
        Parallel.ForEach(node.Children, node =>
        {
            Traverse(node, false);
        });
    }
    else
    {
        foreach (var node in node.Children)
        {
            Traverse(node, false);
        }
    }
}
于 2011-08-17T23:47:25.420 に答える
3

ツリーのトラバースは非常に高速であり、呼び出しはアトミックであり、並行して実行する必要があるChildrenのはデリゲートの高価な性質であるため、これが解決策についての私の見解です。DoSomething

私は、ノードをパラメーターとして受け取り、実行するタスクを作成し、DoSomethingそれ自体を再帰的に呼び出してすべての子ノードのタスクを作成し、最後にすべての内部タスクを待機するタスクを返す関数が必要であるという考えから始めました。完了する必要があります。

ここにあります：

Func<Node, Task> createTask = null;
createTask = n =>
{
    var nt = Task.Factory.StartNew(() =>
    {
        if (n.Property == someValue)
            DoSomething(n);
    });
    var nts = (new [] { nt, })
        .Concat(n.Children.Select(cn => createTask(cn)))
        .ToArray();

    return Task.Factory.ContinueWhenAll(nts, ts => { });
};

それを呼び出してトラバーサルが完了するのを待つために必要なのは、次のとおりです。

createTask(root).Wait();

これをテストするために、ルートから500の子があり、14のレベルがあり、ノードごとに1つまたは2つの子が続くノードのツリーを作成しました。これにより、合計319,501ノードが得られました。

DoSomethingいくつかの作業を実行するメソッドを作成しましたfor (var i = 0; i < 100000 ; i++) { };---次に、上記のコードを実行し、同じツリーを連続して処理することと比較しました。

並列バージョンは5,151ミリ秒かかりました。シーケンシャルバージョン13,746ミリ秒。

また、ノード数を3,196に減らし、処理時間を100倍に増やしたテストも実行しましたDoSomething。TPLは、タスクが迅速に完了すると、非常に巧妙に順次実行に戻ります。そのため、処理時間が長くなると、コードはより並列処理されて実行されます。

現在、並列バージョンは3,203msかかりました。シーケンシャルバージョンは11,581msかかりました。また、createTask(root)関数が完了するのを待たずに関数を呼び出すだけの場合、126ミリ秒しかかかりませんでした。これは、ツリーが非常に高速にトラバースされることを意味します。トラバース中にツリーをロックし、処理が行われているときにロックを解除することは理にかなっています。

これがお役に立てば幸いです。

于 2011-08-18T03:15:38.537 に答える
3

何かが足りないかもしれませんが、その必要性はまったくわかりませんwhile。これwhileは、すべてのノードを反復処理することを保証するだけです。

代わりに、ツリー内のノードごとに関数を再帰的に呼び出します。

public void Traverse(Node root)
{         
    if (root.Property = someValue) DoSomething(node);    
    Parallel.ForEach<Node>(root.Children, node => Traverse(node));
}

編集：もちろん、垂直方向ではなく水平方向に処理することを好み、コストのかかる操作がDoSomethingである場合は、Traverse最初に実行することもできます。

public IEnumerable<Node> Traverse(Node root)
{
    // return all the nodes on this level first, before recurring
    foreach (var node in root.Children)
    {
        if (node.Property == someValue)
            yield return node;
    }

    // next check children of each node
    foreach (var node in root.Children)
    {
        var children = Traverse(node);
        foreach (var child in children)
        {
            yield return child;
        }
    }
}

Parallel.ForEach<Node>(Traverse(n), n => DoSomething(n));
于 2011-08-18T02:16:19.543 に答える
1

p個のプロセッサがあると仮定すると、 Parallel.Foroverroot.Childrenをp個のパーティションで実行する可能性があります。これらはそれぞれ、サブツリーを介して従来のシングルスレッドトラバースを実行し、比較し、DoSomethingではなく、DoSomethingへのデリゲートを並行キューにエンキューします。分布が基本的にランダムでバランスが取れていて、トラバーサルはトラバーサル/エンキューのみを行うため、その部分は1/pの時間かかります。また、トラバーサルは、すべてのDoSomethingが実行される前にそれ自体を使い果たす可能性が高いため、 p個のコンシューマー（DoSomethingの実行者）を持つことができます。）これらすべての操作が独立していると仮定すると、最大の並列実行が可能になります。

ランダムに分散されたサブツリーを持つルートの子の数にまたがるこの素朴なパーティション分割により、トラバーサル自体が高速になります。コンシューマーがプロセッサーごとに大まかに割り当てられると、最大の並列DoSomethingアクションも取得されます。

于 2011-08-18T04:11:31.783 に答える
0

おそらく、キューの代わりにリストまたは配列を使用すると役立つでしょう。また、別のリスト/配列を使用して、次にアクセスするノードにデータを入力します。とにかく最初に幅全体を終了するまで、そのリストを処理することはありません。このようなもの：

List<Node> todoList = new List<Node>();
todoList.Add(node);
while (todoList.Count > 0)
{
    // we'll be adding next nodes to process to this list so it needs to be thread-safe
    // or just sync access to a non-threadsafe list
    // if you know approx how many nodes you expect, you can pre-size the list
    ThreadSafeList<Node> nextList = new ThreadSafeList<Node>();  

    //todoList is readonly/static so can cache Count in simple variable
    int maxIndex  =  todoList.Count-1;
    // process todoList in parallel
    Parallel.For(0, maxIndex, i =>
    {
        // if list reads are thread-safe then no need to sync, otherwise sync
        Node x = todoList[i];

        //process x;
        // e.g. do somehting, get childrenNodesToWorkOnNext, etc.

        // add any child nodes that need to be processed next
        // e.g. nextList.add(childrenNodesToWorkOnNext);
    });

   // done with parallel processing by here so use the next todo list
   todoList = nextList;
)
于 2013-03-14T23:28:27.267 に答える