나는 인터뷰에 가기 전에 몇 가지 준비를하고 있으며, Morris Traversal에 대해 방금 배웠습니다.Morris Traversal의 성능과 이진 트리의 순차적 순회 비교
이 내가 자바 (그 작업)에 쓴 모리스 순회 코드 :
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");
그리고 결과는 나를 놀라게했다! 나는 모든 System.out에 댓글을 달았이 테스트를했을 때 - 367 MS
주의 사항 :
모리스 순회 걸린 : 637 MS
재귀에서 주문 걸린
그
결과입니다 morrisTraversal() 및 recInOrderHelper() 메소드의 .println (...). 내가과에서 주문이 재귀 반복 (금지 스택 프레임 등을한다) 그 때문에 모리스 순회은 (각 재귀 호출에 대해 약 70,000,000 스택 프레임을 엽니 다) 더 빠를 것이라고 생각했기 때문에그 결과는 나를 놀라게
나는 둘 다 O (n) 인 것을 안다. 그래서 분명히 나는 어떤 것들에 대해서는 틀렸다. 그러나 그것은 무엇인가? 내가 뭘 놓치고 있니? Morris Traversal이 반복적 인 In-Order보다 왜 훨씬 느린가요? -
편집 나는 또한 다음 시험했다 : 트리에 70,000,000 노드를 삽입하는 대신 나는 10 만 개 노드 을 삽입 그리고 나는 다음 코드를 실행 않았다
//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 MS
모리스 순회가 나섭니다 : 502786 MS
Morris Traversal은 반복적 인 In-Order에 비해 여전히 매우 느린 것을 볼 수 있습니다. 그래서 나는 또 다른 테스트를했다 만 1,000 노드를 삽입 10,000 회 그 결과는 각각의 코드를 실행 :
재귀 인 - 주문에 나섭니다 : 44 MS
모리스 순회가 나섭니다 : 97 MS
나는 아직도 그것을 얻지 못합니까? Morris Traversal이 왜 더 느린가요?
누군가가 왜 Morris Traversal이 더 느린 지 설명 할 수 있습니까? – thelegend