반복 알고리즘의 반복 버전이 느립니다.

Question

사용자 편의를 위해 여기서 재현 한 Tarjan의 강력한 연결 구성 요소 (SCC)의 반복 버전을 구현하려고합니다 (출처 : http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm).

Input: Graph G = (V, E) 

index = 0       // DFS node number counter 
S = empty       // An empty stack of nodes 
forall v in V do 
    if (v.index is undefined)  // Start a DFS at each node 
    tarjan(v)      // we haven't visited yet 

procedure tarjan(v) 
    v.index = index     // Set the depth index for v 
    v.lowlink = index 
    index = index + 1 
    S.push(v)      // Push v on the stack 
    forall (v, v') in E do   // Consider successors of v 
    if (v'.index is undefined) // Was successor v' visited? 
     tarjan(v')    // Recurse 
     v.lowlink = min(v.lowlink, v'.lowlink) 
    else if (v' is in S)   // Was successor v' in stack S? 
     v.lowlink = min(v.lowlink, v'.lowlink) 
    if (v.lowlink == v.index)  // Is v the root of an SCC? 
    print "SCC:" 
    repeat 
     v' = S.pop 
     print v' 
    until (v' == v) 

내 반복 버전은 다음 노드 구조체를 사용합니다.

void Graph::runTarjan(int out[]) { //You can ignore out. It's a 5-element array that keeps track of the largest 5 SCCs 
     int index = 0; 
tarStack = new stack<Node *>(); 
    onStack = new bool[numNodes]; 
    for (int n = 0; n < numNodes; n++) { 
    if (nodes[n].index == unvisited) { 
     tarjan_iter(&nodes[n], index); 
    } 
    } 
} 

void Graph::tarjan_iter(Node *u, int &index) { 
    u->index = index; 
    u->lowlink = index; 
    index++; 
    u->vindex = 0; 
    tarStack->push(u); 
    u->caller = NULL;   //Equivalent to the node from which the recursive call would spawn. 
    onStack[u->id - 1] = true; 
    Node *last = u; 
    while(true) { 
     if(last->vindex < last->nodeVector->size()) {  //Equivalent to the check in the for-loop in the recursive version 
      Node *w = (*(last->nodeVector))[last->vindex]; 
      last->vindex++;         //Equivalent to incrementing the iterator in the for-loop in the recursive version 
      if(w->index == unvisited) { 
       w->caller = last;      
       w->vindex = 0; 
       w->index = index; 
       w->lowlink = index; 
       index++; 
       tarStack->push(w); 
       onStack[w->id - 1] = true; 
       last = w; 
      } else if(onStack[w->id - 1] == true) { 
       last->lowlink = min(last->lowlink, w->index); 
      } 
     } else { //Equivalent to the nodeSet iterator pointing to end() 
      if(last->lowlink == last->index) { 
       numScc++; 
       Node *top = tarStack->top(); 
       tarStack->pop(); 
       onStack[top->id - 1] = false; 
       int size = 1; 

       while(top->id != last->id) { 
        top = tarStack->top(); 
        tarStack->pop(); 
        onStack[top->id - 1] = false; 
        size++; 
       } 
       insertNewSCC(size); //Ranks the size among array of 5 elements 
      } 

      Node *newLast = last->caller; //Go up one recursive call 
      if(newLast != NULL) { 
       newLast->lowlink = min(newLast->lowlink, last->lowlink); 
       last = newLast; 
      } else { //We've seen all the nodes 
       break; 
      } 
     } 
    } 
} 

내 반복 버전이 실행되고 나에게 재귀 버전과 동일한 출력을 제공 :

struct Node { 
    int id; //Signed int up to 2^31 - 1 = 2,147,483,647 
    int index; 
    int lowlink;   
    Node *caller;     //If you were looking at the recursive version, this is the node before the recursive call 
    unsigned int vindex;    //Equivalent to the iterator in the for-loop in tarjan 
    vector<Node *> *nodeVector;  //Vector of adjacent Nodes 
}; 

는 여기가 반복 버전에 무슨 짓을했는지. 문제는 반복 버전의 속도가 느리며 이유가 확실하지 않다는 것입니다. 아무도 내 구현에 대한 통찰력을 줄 수 있습니까? 재귀 알고리즘을 반복적으로 구현하는 더 좋은 방법이 있습니까?

Answer 1

재귀 알고리즘은 저장 영역으로 스택을 사용합니다. 반복 버전에서는 힙 할당에 의존하는 벡터를 사용합니다. 스택 기반 할당은 스택 끝 포인터를 이동하는 문제 일 뿐이므로 힙 할당은 상당히 느릴 수 있지만 매우 빠르다는 것이 알려져 있습니다. 반복 버전이 더 느리다는 것은 전혀 놀라운 일이 아닙니다.

일반적으로 말하자면, 문제가 스택 전용 재귀 모델 내에서 잘 맞으면 재발입니다.