Iterative Version eines rekursiven Algorithmus langsamer

Question

Ich versuche, eine iterative Version von Tarjan der stark verbundenen Komponenten (SKG) zu implementieren, reproduzierte hier für Ihre Bequemlichkeit (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 folgenden Knoten 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 ist langsamer, und ich bin mir nicht sicher, warum. Kann mir jemand einen kleinen Einblick auf meiner Implementierung geben? Gibt es einen besseren Weg, um den rekursiven Algorithmus iterativ zu implementieren?

Answer 1

Ein rekursiven Algorithmus verwendet den Stapel als Speicherbereich. In der iterativen Version, verwenden Sie einige Vektoren, die sich auf Heapzuordnung verlassen. Stack-basierte Zuordnung ist bekannt, sehr schnell sein, da es nur eine Frage der Bewegung einen End-of-Stack-Pointer ist, während Heapzuordnung wesentlich langsamer sein kann. Dass die iterative Version langsamer ist nicht vollständig überraschend.

Generell, wenn das Problem bei der Hand paßt gut in einem Stapel-nur rekursive Modell, dann mit allen Mitteln, recurse.