La versión iterativa de un algoritmo recursivo es más lenta

Question

Estoy tratando de implementar una versión iterativa de los componentes fuertemente conectados de Tarjan (SCC), reproducida aquí para su conveniencia (fuente: 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) 

Mi versión iterativa usa la siguiente estructura de nodo.

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

Aquí es lo que hice para la versión 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; 
      } 
     } 
    } 
} 

mi versión iterativos carreras y me da el mismo resultado que la versión recursiva. El problema es que la versión iterativa es más lenta, y no estoy seguro de por qué. ¿Alguien puede darme una idea de mi implementación? ¿Hay una mejor manera de implementar iterativamente el algoritmo recursivo?

Answer 1

Un algoritmo recursivo utiliza la pila como área de almacenamiento. En la versión iterativa, usted usa algunos vectores, que a su vez dependen de la asignación del montón. Se sabe que la asignación basada en pila es muy rápida, ya que solo se trata de mover un puntero al final de la pila, mientras que la asignación del montón puede ser sustancialmente más lenta. Que la versión iterativa es más lenta no es del todo sorprendente.

En términos generales, si el problema en cuestión encaja bien dentro de un modelo recursivo de solo pila, entonces, por supuesto, recurse.