9

私は C# で四分木を実装しましたが、逆のように見えるにもかかわらず、反復よりも再帰の方が優れているように見えるという奇妙な出来事に遭遇しました。

私のノードは次のようになります。

class QuadNode
{
    private QuadNode topLeft;
    private QuadNode topRight;
    private QuadNode bottomRight;
    private QuadNode bottomLeft;
    // other fields...
}

ツリーをトラバースするために、ルート ノードで呼び出す次の再帰メソッドを使用しました。

Traverse()
{
    // visit 'this'

    if (topLeft != null)
        topLeft.Traverse();
    if (topRight != null)
        topRight.Traverse();
    if (bottomRight != null)
        bottomRight.Traverse();
    if (bottomLeft != null)
        bottomLeft.Traverse();
}

ほとんど興味がなく、ツリーをトラバースするための反復メソッドを作成しようとしました。

各ノードに次のフィールドを追加しましprivate QuadNode nextたnext。基本的に、ツリーのノードから片方向リストを作成しました。
この時点で、次の方法でツリーをトラバースできます。

Traverse()
{
    QuadNode node = this;
    while (node != null)
    {
        // visit node

        node = node.next;
    }
}

各メソッドのパフォーマンスをテストした後、反復バージョンが再帰バージョンよりも一貫して著しく遅いことを知って非常に驚きました. 巨大なツリーと小さなツリーの両方でこれをテストしましたが、再帰的な方法は常に高速です。（Stopwatchベンチマークには を使用しました）
両方の方法がツリー全体を正常にトラバースし、反復バージョンは計画どおりに各ノードに 1 回だけアクセスすることを確認したため、それらの間のリンクに問題はありません。

反復バージョンの方がパフォーマンスが優れていることは明らかです...これの原因は何でしょうか? 再帰バージョンの方が速い理由について、明らかな理由を見落としているのでしょうか?

私は Visual Studio 2012 を使用しており、リリースの下でコンパイルされ、任意の CPU (32 ビットのチェックなしを優先) を使用しています。

編集:
新しいプロジェクトを開き、結果を確認する簡単なテストを作成しました。
完全なコードは次のとおりです: http://pastebin.com/SwAsTMjQ
コードはコメントされていませんが、自己文書化されていると思います。

4

2 に答える 2

4

キャッシュの局所性は速度を落としています。試す：

public void LinkNodes()
{
    var queue = new Queue<QuadNode>();
    LinkNodes(queue);

    QuadNode curr = this;

    foreach (var item in queue)
    {
        curr.next = item;
        curr = item;
    }
}

public void LinkNodes(Queue<QuadNode> queue)
{
    queue.Enqueue(this);

    if (topLeft != null)
        topLeft.LinkNodes(queue);
    if (topRight != null)
        topRight.LinkNodes(queue);
    if (bottomRight != null)
        bottomRight.LinkNodes(queue);
    if (bottomLeft != null)
        bottomLeft.LinkNodes(queue);
}

これで、反復バージョンは再帰バージョンよりも 30/40% 速くなるはずです。

遅い理由は、反復アルゴリズムが深さ優先ではなく幅優先になるためです。要素を深さ優先で作成したため、メモリ内で深さ優先で並べ替えられます。私のアルゴリズムは、トラバース リスト Depth First を作成します。

(分かりやすくするためにQueueinを使用しましたが、実際にはなくても構いません)LinkNodes()

public QuadNode LinkNodes(QuadNode prev = null)
{
    if (prev != null)
    {
        prev.next = this;
    }

    QuadNode curr = this;

    if (topLeft != null)
        curr = topLeft.LinkNodes(curr);

    if (topRight != null)
        curr = topRight.LinkNodes(curr);

    if (bottomRight != null)
        curr = bottomRight.LinkNodes(curr);

    if (bottomLeft != null)
        curr = bottomLeft.LinkNodes(curr);

    return curr;
}
于 2013-09-17T08:21:30.343 に答える
0

コードを見ると、両方の方法が同じように機能しているように見えますが、再帰的な方法では「ループ」で4つのノードにアクセスします。つまり、3つのテスト間で「ジャンプ」しないのに対し、反復では「ジャンプ」します各実行のループの開始。ほぼ同様の動作を見たい場合は、反復ループを次のようなものに展開する必要があります。

Traverse(int depth)
{
    QuadNode node = this;
    while (node != null)
    {
        // visit node

        node = node.next;
        if (node!=null) node=node.next;
        if (node!=null) node=node.next;
        if (node!=null) node=node.next;

    }
}
于 2013-09-17T07:09:38.653 に答える