Morris遍歷與二叉樹遞歸有序的性能

在採訪之前我正在做一些準備工作，並且我剛剛瞭解了Morris Traversal。Morris遍歷與二叉樹遞歸有序的性能

這是莫里斯遍歷代碼，我在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

這裏是我的了有序方法代碼：

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");

結果令我感到驚訝！

這些都是結果：

莫里斯穿越了：637毫秒

遞歸按序了：367毫秒

注意 - 當我做這個測試我評論所有的System.out .println（...）來自morrisTraversal（）和recInOrderHelper（）方法。

這些結果讓我吃驚，因爲我認爲莫里斯遍歷會更快，因爲它的反覆（不打開堆棧幀等），並在訂單是遞歸（打開約7000萬堆棧幀每個遞歸調用）

我知道他們都是O（n），所以很顯然我錯了一些事情，但是哪些？我錯過了什麼？爲什麼Morris遍歷比遞歸的In-Order慢得多？

編輯 - 我也做了下一個測試：而不是插入70000000個節點樹的我插入100000個節點而且我也跑了下面的代碼：

//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");

而且結果是：

遞歸按序了：214434毫秒

莫里斯穿越了：502786毫秒

正如你可以看到，與遞歸的In-Order相比，Morris Traversal仍然非常緩慢。所以我做了另外一個測試，只插入1000個節點和運行每個代碼只10000次，其結果是：

遞歸按序了：44毫秒

莫里斯穿越了97毫秒

我還不明白嗎？爲什麼莫里斯遍歷速度較慢？

來源

2013-02-06 thelegend

有人可以解釋爲什麼Morris遍歷速度較慢？ – thelegend

如果不將性能估計分解爲其組件，很難分辨出來，但是當使用假右邊部分追溯節點時，Morris遍歷基本上遍歷樹的一部分。你在Morris循環中也做了更多的工作，所以常數因子會更大。奇怪的是它幾乎是2倍，但是我不會在沒有進一步細節的情況下依靠這種實際成本。

來源

2013-02-06 00:17:51 dfb

您沒有熱身通行證。您應該首先執行兩種方法，然後再按時執行。您也忽略了大多數Java代碼在長時間運行的進程中運行的事實，最終編譯爲機器代碼。我會嘗試使用更小的樹並執行遍歷多次。

來源

2013-02-06 00:33:45

Morris遍歷與二叉樹遞歸有序的性能

回答

相關問題