Iterative Version eines rekursiven Algorithmus ist langsamer

Question

Ich versuche, eine iterative Version von Tarjans stark verbundenen Komponenten (SCCs), reproduziert hier für Ihre Bequemlichkeit zu implementieren (Quelle: 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) 

Meine iterative Version verwendet die folgende Node-Struktur.

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 
}; 

Hier ist, was ich für die iterative Version tat

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; 
      } 
     } 
    } 
} 

Meine iterative Version läuft und gibt mir die gleiche Ausgabe wie die rekursive Version. Das Problem ist, dass die iterative Version langsamer ist, und ich bin mir nicht sicher warum. Kann mir jemand einen Einblick in meine Umsetzung geben? Gibt es einen besseren Weg, den rekursiven Algorithmus iterativ zu implementieren?

Answer 1

Ein rekursiver Algorithmus verwendet den Stapel als Speicherbereich. In der iterativen Version verwenden Sie einige Vektoren, die ihrerseits auf die Heap-Zuweisung angewiesen sind. Es ist bekannt, dass die stapelbasierte Zuweisung sehr schnell ist, da es nur darum geht, einen Ende-des-Stapel-Zeigers zu bewegen, wohingegen die Heap-Zuordnung wesentlich langsamer sein kann. Dass die iterative Version langsamer ist, ist nicht völlig überraschend.

Im Allgemeinen, wenn das vorliegende Problem gut in ein rekursives Modell passt, dann recurse.