0

面接に行く前にいくつかの準備をしていて、モリス・トラバーサルについて知りました.

これは私がJavaで書いたモリス・トラバーサルのコードです(その動作):

protected void morrisTraversal(){
    BinaryNode pre = null;//BinaryNode is a class which represent a node in the tree
    BinaryNode current = this.root;//root is the root of the tree
    while(current != null){
        if(current.getLeftChild() == null){
            System.out.println(current.getNodeData().getId());//id is unique
            current = current.getRightChild();
        }//if
        else{
            pre = current.getLeftChild();
            while(pre.getRightChild() != null && pre.getRightChild().getNodeData().getId() != current.getNodeData().getId())
                pre = pre.getRightChild();
            if(pre.getRightChild() == null){
                pre.setRightChild(current);
                current = current.getLeftChild();
            }//if
            else{
                System.out.println(current.getNodeData().getId());
                current = current.getRightChild();
                pre.setRightChild(null);
            }//else
        }//else
    }//while
}//MorrisTraversal

In-Order メソッドのコードは次のとおりです。

protected void recInOrder() {
    if(this.root != null)
        recInOrderHelper(this.root);
    else
        System.out.println("The Tree Is Empty");;
}//recInOrder


private void recInOrderHelper(BinaryNode node)  {
    if(node != null){
        recInOrderHelper(node.getLeftChild());
        System.out.println(node.getNodeData().getId());
        recInOrderHelper(node.getRightChild());
    }
}//recInOrderHelper

そして、私がメインで行ったことは次のとおりです。バイナリツリーに70,000,000ノードを挿入し、次の小さなチェックを行いました:

long start = System.currentTimeMillis();
tree4.morrisTraversalInOrder();
System.out.println("morris traversal TOOK: " + (System.currentTimeMillis() - start) + " ms");

start = System.currentTimeMillis();
tree4.recInOrder();
System.out.println("recursive in-order TOOK: " + (System.currentTimeMillis() - start) + " ms");

そして、結果は私を驚かせました！

それらは結果です：

モリス トラバーサル TOOK: 637 ミリ秒

再帰インオーダー TOOK: 367 ミリ秒

注意 - このテストを行ったとき、morrisTraversal() および recInOrderHelper() メソッドからのすべての System.out.println(...) にコメントを付けました。

Morris Traversal は反復的 (スタック フレームなどを開かない) であり、In-Order は再帰的であるため (再帰呼び出しごとに約 70,000,000 スタック フレームを開く)、高速になると思っていたので、これらの結果は私を驚かせました。

私はそれらの両方がO(n)であることを知っているので、明らかに私はいくつかのことについて間違っていますが、どれですか? 私は何が欠けていますか？Morris Traversal が再帰的な In-Order よりも遅いのはなぜですか?

編集-次のテストも行いました。ツリーに70,000,000ノードを挿入する代わりに、100,000ノードを挿入し、次のコードを実行しました:

//running the two algorithms one time before doing the actual test(but in the same execution)
tree4.recInOrder();
tree4.morrisTraversalInOrder();

//starting the actual test
long start = System.currentTimeMillis();
for(i = 0; i < 100000; i++){
    tree4.recInOrder(); 
}
System.out.println("Recursive In-Order TOOK: " + (System.currentTimeMillis() - start) + " ms");

start = System.currentTimeMillis();
for(i = 0; i < 100000; i++){
    tree4.morrisTraversalInOrder(); 
}
System.out.println("Morris Traversal TOOK: " + (System.currentTimeMillis() - start) + " ms");

結果は次のとおりです。

再帰インオーダー TOOK: 214434 ミリ秒

モリス トラバーサル TOOK: 502786 ミリ秒

ご覧のとおり、Morris Traversal は、再帰的な In-Order に比べて依然として非常に遅いです。そこで、別のテストを行い、1,000 個のノードのみを挿入し、各コードを 10,000 回だけ実行しました。結果は次のとおりです。

再帰インオーダー TOOK: 44 ミリ秒

モリス トラバーサル TOOK: 97 ミリ秒

まだわからないの？Morris Traversal が遅いのはなぜですか?

4

3 に答える 3

0

パフォーマンスの見積もりをコンポーネントに分割せずに判断するのは困難ですが、Morris Traversalは、偽の右側の部分でノードをトレースバックするときに、基本的にツリーの一部を2回トラバースします。また、Morrisループ内でより多くの作業を行っているため、定数係数は大きくなります。ほぼ2倍になるのは不思議ですが、それ以上の詳細がなければ、実際のコストに依存することはありません。

于 2013-02-06T00:17:51.843 に答える
0

ウォームアップ パスがありません。最初に両方のメソッドを実行してから、タイミングを合わせて再度実行する必要があります。また、ほとんどの Java コードは長時間実行されるプロセスで実行され、最終的にはマシン コードにコンパイルされるという事実も無視しています。小さいツリーを使用して、トラバーサルを何度も実行してみます。

于 2013-02-06T00:33:45.123 に答える