¿Cómo ofrece un nodo centinela beneficios por encima de NULL?

Question

Por Sentinel Node wikipedia page se dice que los beneficios de un ganglio centinela sobre NULL son:

• Aumento de la velocidad de las operaciones
• reducido tamaño de código algorítmico
• Mayor robustez estructura de datos (posiblemente).

Realmente no entiendo cómo las verificaciones en un ganglio centinela serían más rápido (o cómo poner en práctica adecuadamente en una lista o árbol ligado), así que supongo que esto es más una cuestión de dos partes:

1. ¿Qué causa que el nodo centinela sea un mejor diseño que NULO?
2. ¿Cómo implementaría un nodo centinela en (por ejemplo) una lista?

Answer 1

No hay ninguna ventaja con centinelas si sólo está haciendo iteración simple y sin mirar a los datos de los elementos.

Sin embargo, hay una ganancia real cuando se usa para algoritmos de tipo "encontrar". Por ejemplo, imagine una lista de la lista vinculada std::list donde desea encontrar un valor específico x.

Lo que se puede prescindir de centinelas es:

for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here 
{ 
    if (*i == x) // second branch here 
    return i; 
} 
return list.end(); 

Pero con centinelas (por supuesto, en realidad final tiene que ser un nodo real para este ...):

iterator i=list.begin(); 
*list.end() = x; 

while (*i != x) // just this branch! 
    ++i; 

return i; 

Usted ve que no hay necesidad de que la rama adicional para poner a prueba para el final de la lista - el valor siempre está garantizado para estar allí, por lo que volverá automáticamente end() si x que no se encuentra en su " "elementos válidos"

Para otra aplicación útil y realmente útil de centinelas, vea "intro-sort", que es el algoritmo de clasificación que se usa en la mayoría de las implementaciones std::sort. Tiene una variante genial del algoritmo de partición que usa centinelas para eliminar algunas ramas.

Answer 2

La respuesta a su pregunta (1) está en la última frase de la entrada de la Wikipedia vinculado: "A medida que los nodos que normalmente vincular a NULL ahora vincular a 'nulo' (incluidas las negativas en sí), que elimina la necesita una costosa operación de sucursal para verificar NULL ".

Normalmente debe probar un nodo para NULL antes de acceder a él. Si en su lugar tiene un nodo válido nil, entonces no necesita hacer esta primera prueba, guardando una comparación y una bifurcación condicional, que de otro modo podría ser costosa en las CPU superescalares modernas cuando la derivación se predice erróneamente.

Answer 3

voy a tratar de responder en el contexto de la biblioteca de plantillas estándar:

1) En una llamada a "next()", NULL no indica necesariamente al final de la lista. ¿Qué ocurre si se produce un error de memoria? Devolver un nodo centinela es una forma definitiva de indicar que se ha producido el fin de lista, y no algún otro resultado. En otras palabras, NULL podría indicar una variedad de cosas, no solo el final de la lista.

2) Este es solo un método posible: cuando crea su lista, cree un nodo privado que no se comparta fuera de la clase (llamado "lastNode" por ejemplo). Al detectar que ha iterado hasta el final de la lista, haga que "next()" devuelva una referencia a "lastNode". También tenga un método llamado "end()" devuelva una referencia a "lastNode". Por último, dependiendo de cómo implemente su clase, es posible que deba anular el operador de comparación para que esto funcione correctamente.

Ejemplo:

class MyNode{ 

}; 

class MyList{ 

public: 
    MyList() : lastNode(); 

    MyNode * next(){ 

     if (isLastNode) return &lastNode; 
     else return //whatever comes next 
    } 

    MyNode * end() { 

     return &lastNode; 
    } 

    //comparison operator 
    friend bool operator == (MyNode &n1, MyNode &n2){ 

     return (&n1 == &n2); //check that both operands point to same memory 
    } 


private: 
    MyNode lastNode; 
}; 


int main(){ 

    MyList list; 
    MyNode * node = list.next(); 

    while (node != list.end()){ 

    //do stuff! 

    node = list.next(); 
    } 

    return 0; 
} 

Answer 4

Creo que un pequeño ejemplo de código sería una mejor explicación que una discusión teórica.

El siguiente es el código para la eliminación de nodo en una lista doblemente enlazada de nodos donde NULL se utiliza para marcar el final de la lista y en donde dos punteros first y last se utilizan para mantener la dirección del primero y último nodo:

// Using NULL and pointers for first and last 
if (n->prev) n->prev->next = n->next; 
     else first = n->next; 
if (n->next) n->next->prev = n->prev; 
     else last = n->prev; 

y este es el mismo código en el lugar hay un nodo ficticio especial para marcar el final de la lista y cuando la dirección del primer nodo de la lista se almacena en el campo del nodo especial y donde next el último nodo de la lista se almacena en el campo prev del nodo ficticio especial:

// Using the dummy node 
n->prev->next = n->next; 
n->next->prev = n->prev; 

El mismo tipo de simplificación también está presente para la inserción del nodo; por ejemplo para insertar nodo n antes nodo x (que tiene x == NULL o x == &dummy significado inserción en última posición) el código sería:

// Using NULL and pointers for first and last 
n->next = x; 
n->prev = x ? x->prev : last; 
if (n->prev) n->prev->next = n; 
     else first = n; 
if (n->next) n->next->prev = n; 
     else last = n; 

y

// Using the dummy node 
n->next = x; 
n->prev = x->prev; 
n->next->prev = n; 
n->prev->next = n; 

Como se puede ver el enfoque nodo ficticio eliminado una lista doblemente vinculada todos los casos especiales y todos los condicionales.

El siguiente cuadro representa los dos enfoques para la misma lista en la memoria ...