La versione iterativa di un algoritmo ricorsivo è più lenta

Question

Sto provando ad implementare una versione iterativa delle componenti fortemente connesse (SCC) di Tarjan, qui riprodotte per comodità (fonte: 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) 

La mia versione iterativa utilizza la seguente struttura di nodi.

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

Ecco quello che ho fatto per la versione iterativa:

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

miei iterativi corre versione e mi dà la stessa uscita della versione ricorsiva. Il problema è che la versione iterativa è più lenta, e non sono sicuro del perché. Qualcuno può darmi qualche informazione sulla mia implementazione? Esiste un modo migliore per implementare iterativamente l'algoritmo ricorsivo?

Answer 1

Un algoritmo ricorsivo utilizza la pila come area di stoccaggio. Nella versione iterativa, si utilizzano alcuni vettori, che si basano sull'allocazione dell'heap. allocazione stack-based è noto per essere molto veloce, in quanto è solo questione di muovere un puntatore di fine pila, mentre allocazione mucchio può essere sostanzialmente più lento. Che la versione iterativa sia più lenta non è del tutto sorprendente.

generale, se il problema in esame si adatta bene all'interno di un modello ricorsivo pila sola, poi, con tutti i mezzi, si ripete.