c# - usar - Recursión más rápida que la iteración

recursividad vs iteracion

Question

Implementé un árbol cuádruple en C # y me encontré con una extraña ocurrencia donde la recursión parece funcionar mejor que la iteración, a pesar de que parece que debería ser lo contrario.

Mis nodos se ven así:

class QuadNode
{
    private QuadNode topLeft;
    private QuadNode topRight;
    private QuadNode bottomRight;
    private QuadNode bottomLeft;
    // other fields...
}

Para recorrer el árbol utilicé el siguiente método recursivo, que invoco en el nodo raíz:

Traverse()
{
    // visit ''this''

    if (topLeft != null)
        topLeft.Traverse();
    if (topRight != null)
        topRight.Traverse();
    if (bottomRight != null)
        bottomRight.Traverse();
    if (bottomLeft != null)
        bottomLeft.Traverse();
}

En su mayoría por interés, traté de crear un método iterativo para atravesar el árbol.

private QuadNode next el siguiente campo a cada nodo: private QuadNode next , y cuando creo el árbol, realizo un recorrido transversal primero utilizando una cola, vinculando el next campo de cada nodo al siguiente nodo en la línea. Básicamente, creé una lista de enlaces únicos de los nodos del árbol.
En este punto, puedo atravesar el árbol con el siguiente método:

Traverse()
{
    QuadNode node = this;
    while (node != null)
    {
        // visit node

        node = node.next;
    }
}

Después de probar el rendimiento de cada método, me sorprendí al descubrir que la versión iterativa es consistentemente y notablemente más lenta que la recursiva. He probado esto tanto en árboles grandes como en árboles pequeños y el método recursivo siempre es más rápido. (Utilicé un Stopwatch para la evaluación comparativa)
Confirmé que ambos métodos atraviesan con éxito todo el árbol y que la versión iterativa solo visita cada nodo exactamente una vez como se planeó , por lo que no hay problema con la vinculación entre ellos.

Me parece obvio que la versión iterativa funcionaría mejor ... ¿cuál podría ser la causa de esto? ¿Estoy pasando por alto alguna razón obvia de por qué la versión recursiva es más rápida?

_{Estoy usando Visual Studio 2012 y Compiled under Release, Any CPU (prefiero 32 bits sin marcar).}

Editar:
Abrí un nuevo proyecto y creé una prueba simple que también confirma mis resultados.
Aquí está el código completo: http://pastebin.com/SwAsTMjQ
El código no está comentado, pero creo que es bastante autodocumentado.

Answer 1

La localidad de caché está matando la velocidad. Tratar:

public void LinkNodes()
{
    var queue = new Queue<QuadNode>();
    LinkNodes(queue);

    QuadNode curr = this;

    foreach (var item in queue)
    {
        curr.next = item;
        curr = item;
    }
}

public void LinkNodes(Queue<QuadNode> queue)
{
    queue.Enqueue(this);

    if (topLeft != null)
        topLeft.LinkNodes(queue);
    if (topRight != null)
        topRight.LinkNodes(queue);
    if (bottomRight != null)
        bottomRight.LinkNodes(queue);
    if (bottomLeft != null)
        bottomLeft.LinkNodes(queue);
}

Ahora la versión iterativa debe ser 30/40% más rápida que la versión recursiva.

La razón de la lentitud es que su algoritmo iterativo irá primero de ancho en lugar de profundidad primero. Creó sus elementos Primero la profundidad, por lo que se ordenan la profundidad primero en la memoria. Mi algoritmo crea la lista transversal Profundidad primero.

(tenga en cuenta que utilicé una Queue en LinkNodes() para que sea más fácil de seguir, pero en verdad podría hacerlo sin)

public QuadNode LinkNodes(QuadNode prev = null)
{
    if (prev != null)
    {
        prev.next = this;
    }

    QuadNode curr = this;

    if (topLeft != null)
        curr = topLeft.LinkNodes(curr);

    if (topRight != null)
        curr = topRight.LinkNodes(curr);

    if (bottomRight != null)
        curr = bottomRight.LinkNodes(curr);

    if (bottomLeft != null)
        curr = bottomLeft.LinkNodes(curr);

    return curr;
}

Answer 2

Mirando tu código, ambos métodos parecen funcionar igual, PERO en el recursivo visitas 4 nodos en un "bucle", eso significa que no "saltas" entre 3 pruebas mientras que en la iterativa "saltas" al comienzo del ciclo cada carrera. Diría que si quieres ver un comportamiento casi similar, deberás desenrollar el bucle iterativo en algo como:

Traverse(int depth)
{
    QuadNode node = this;
    while (node != null)
    {
        // visit node

        node = node.next;
        if (node!=null) node=node.next;
        if (node!=null) node=node.next;
        if (node!=null) node=node.next;

    }
}