In che modo un nodo sentinella offre vantaggi rispetto a NULL?

Sulla pagina wikipedia del nodo Sentinel si dice che i vantaggi di un nodo sentinella su NULL sono:

  • Aumento della velocità delle operazioni
  • Ridotte dimensioni del codice algoritmico
  • Maggiore robustezza della struttura dei dati (discutibilmente).

Non capisco in realtà come i controlli su un nodo sentinella siano più veloci (o su come implementarli correttamente in un elenco o albero collegato), quindi suppongo che si tratti di una domanda in due parti:

  1. Cosa fa sì che il nodo sentinella sia un design migliore di NULL?
  2. Come implementeresti un nodo sentinella in (per esempio) un elenco?

Non c’è alcun vantaggio con le sentinelle se si sta solo facendo una semplice iterazione e non guardando i dati negli elementi.

Tuttavia, c’è un vero guadagno quando lo si utilizza per algoritmi di tipo “trova”. Ad esempio, immagina un elenco di liste collegate std::list dove vuoi trovare un valore specifico x .

Quello che faresti senza sentinelle è:

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

Ma con le sentinelle (ovviamente, la fine deve essere un vero nodo per questo …):

 iterator i=list.begin(); *list.end() = x; while (*i != x) // just this branch! ++i; return i; 

Vedete che non è necessario che il ramo aggiuntivo verifichi la fine dell’elenco – il valore è sempre garantito, quindi tornerete automaticamente end() se x non può essere trovato negli elementi “validi”.

Per un’altra interessante e utile applicazione di sentinelle, vedi “intro-sort”, che è l’algoritmo di ordinamento utilizzato nella maggior parte delle implementazioni di std::sort . Ha una variante interessante dell’algoritmo di partizione che utilizza le sentinelle per rimuovere alcuni rami.

Penso che un piccolo esempio di codice sarebbe una spiegazione migliore di una discussione teorica.

Di seguito è riportato il codice per l’eliminazione dei nodes in un elenco di nodes con collegamento doppio in cui NULL viene utilizzato per contrassegnare la fine dell’elenco e in cui due puntatori first e last vengono utilizzati per contenere l’indirizzo del primo e dell’ultimo 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; 

e questo è lo stesso codice dove invece c’è uno speciale nodo fittizio per segnare la fine della lista e dove l’indirizzo del primo nodo della lista è memorizzato nel next campo del nodo speciale e dove l’ultimo nodo nella lista è memorizzato nel campo prev del nodo fittizio speciale:

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

Lo stesso tipo di semplificazione è presente anche per l’inserimento del nodo; per esempio per inserire il nodo n prima del nodo x (avendo x == NULL o x == &dummy significa l’inserimento nell’ultima posizione) il codice sarebbe:

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

e

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

Come si può vedere, l’approccio del nodo fittizio è stato rimosso per un elenco con doppia connessione tutti i casi speciali e tutti i condizionali.

L’immagine seguente rappresenta i due approcci per lo stesso elenco in memoria …

Alternative al nodo NULL / fittizio per una lista doppiamente collegata

La risposta alla tua domanda (1) si trova nell’ultima frase della voce di Wikipedia collegata: “Poiché i nodes che normalmente collegano a NULL ora collegano a” nil “(incluso lo stesso nil), rimuove la necessità di un’operazione di branch costosa per controlla per NULL. “

Normalmente è necessario testare un nodo per NULL prima di accedervi. Se invece si dispone di un nodo nil valido, non è necessario eseguire questo primo test, salvando un confronto e un ramo condizionale, che può essere altrimenti costoso sulle moderne CPU superscalari quando il ramo viene erroneamente predetto.

Proverò a rispondere nel contesto della libreria di modelli standard:

1) In una chiamata a “next ()”, NULL non indica necessariamente la fine dell’elenco. Cosa succede se si è verificato un errore di memoria? Restituire un nodo sentinella è un modo definitivo per indicare che si è verificata la fine dell’elenco e non qualche altro risultato. In altre parole, NULL potrebbe indicare una varietà di cose, non solo la fine della lista.

2) Questo è solo un metodo ansible: quando crei la tua lista, crea un nodo privato che non è condiviso al di fuori della class (chiamato “lastNode” per esempio). Dopo aver rilevato di aver iterato alla fine dell’elenco, fare in modo che “next ()” restituisca un riferimento a “lastNode”. Anche un metodo chiamato “end ()” restituisce un riferimento a “lastNode”. Infine, a seconda di come si implementa la class, potrebbe essere necessario sovrascrivere l’operatore di confronto affinché funzioni correttamente.

Esempio:

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