임의의 깊이 트리를 삭제하는 가장 빠른 방법은 무엇입니까?

필자 자신의 연습을 위해 필자는 XML 파서를 작성하고있다. 트리를 채우려면 보통 std::stack을 사용하고 마지막 노드의 자식으로 만든 후에 맨 위에있는 현재 노드를 밀어 넣으십시오 (깊이 우선이어야합니까?). 그래서 이제는 노드를 삭제할 때도 똑같은 작업을 수행합니다. 더 빠른 방법이 있는지 알고 싶습니다. 삭제
현재 코드 :임의의 깊이 트리를 삭제하는 가장 빠른 방법은 무엇입니까?

struct XmlNode{ 
    // ignore the rest of the node implementation for now 
    std::vector<XmlNode*> children_; 
}; 
XmlNode* root_ = new XmlNode; 

// fill root_ with child nodes... 
// and then those nodes with child nodes and so fort... 

std::stack<XmlNode*> nodes_; 
nodes_.push(root_); 
while(!nodes_.empty()){ 
    XmlNode* node = nodes_.top(); 
    if(node->children_.size() > 0){ 
     nodes_.push(node->children_.back()); 
     node->children_.pop_back(); 
    }else{ 
     delete nodes_.top(); 
     nodes_.pop(); 
    } 
}

완전히 잘 작동하지만 좀 느린 보인다. 이렇게 더 빠르고 더 나은/일반적인 방법이 있습니까?

출처

2011-02-16 Xeo

"다소 느리다고"알고리즘의 성능에 대한 허용되는 설명이 아닙니다. 코드를 프로파일 링하고 코드가 얼마나 빨라 졌는지 보셨습니까? 하드 데이터가 있습니까? –

@Xeo : 재귀를 피하는 이유는 무엇입니까? 정말 위험할까요? – Mehrdad

'if (... size()> 0)'내부에서 더 엄격한 루프를 가질 수 있습니다. 자식 노드를 자식 노드와 함께 스택에 푸시하거나 자식 노드가없는 노드를 삭제 한 다음'clear()'를 호출 할 수 있습니다. (어떤 사람들은'! ... children_.empty()'를 모든 컨테이너에 대해 empty()의 상수 시간으로 추천하지만, 컨테이너를 변경하면 유지 보수 포인트가 하나 줄어들지 만,'size()'는 스택의 상수 시간이다). –

당신이 발생하지 않습니다 재귀 버전이 부족 (예 : 스택 오버 플로우) 중 하나입니다 또는 느리게 (입증하지 않는 한, 쉽게 반복적으로 무엇을 할 수 있는지 반복적으로을 할 비켜 가지 마세요 스택 오버플로를 시작하지 않으면 OS가 강제로 확장되거나 충돌 할 수 있습니다.)

즉, 일반적으로 선형 구조에는 반복을 사용하고 트리 구조에는 반복을 사용합니다.

Compared to recursion, 반복 방법은 내 컴퓨터에서 약 3 배 느립니다. XML 심도가 실제 XML 문서에서 본 적이없는 몇백 개의 중첩을 초과하지 않는다는 것을 확신 할 수 있다면 재귀는 문제가되지 않습니다.

반복은 인간입니다. 되풀이하다, 신성하다. :)

출처

2011-02-16 06:10:36 Mehrdad

임의의 깊이 트리를 삭제하는 가장 빠른 방법은 무엇입니까?

답변

관련 문제