Comment un ganglion sentinelle offrir des avantages plus NULLE?

Question

Sur le ganglion Sentinelle page wikipédia il est dit que les avantages d'un ganglion sentinelle sur NULL sont :

• L'augmentation de la vitesse des opérations
• Réduit algorithmique de la taille du code
• Augmentation de la structure de données de la robustesse (sans aucun doute).

Je ne comprends pas vraiment comment les contrôles à l'encontre d'un ganglion sentinelle serait plus rapide (ou comment les mettre en œuvre dans une liste ou un arbre), donc je suppose que c'est plus un question:

1. Quelles sont les causes du ganglion sentinelle pour être un meilleur design que NULLE?
2. Comment voulez-vous mettre en œuvre un ganglion sentinelle dans (par exemple) une liste?

Answer 1

Je pense qu'un petit exemple de code serait une meilleure explication que d'une théorie de la discussion.

Voici le code pour le nœud de suppression dans une liste à double liaison de nœuds où NULL est utilisé pour marquer la fin de la liste et où les deux pointeurs first et last sont utilisés pour contenir l'adresse de la première et de la dernière nœud:

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

et c'est le même code, où au lieu de cela, il existe un mannequin nœud pour marquer la fin de la liste et lorsque l'adresse du premier nœud de la liste est stockée dans l' next domaine du nœud spécial et où le dernier nœud de la liste est stockée dans l' prev domaine de la spéciale mannequin nœud:

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

Le même genre de simplification est également présent pour le nœud d'insertion; par exemple, pour insérer un nœud n avant que le nœud x (ayant x == NULL ou x == &dummy sens d'insertion en dernière position), le code serait:

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

et

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

Comme vous pouvez le voir le mannequin nœud approche supprimé pour un doublement lié liste de tous les cas particuliers et à toutes les conditions.

La photo suivante représente les deux approches pour la même liste en mémoire...

Answer 2

Il n'y a pas d'avantage avec des sentinelles si vous êtes juste faire simple itération et ne pas regarder les données dans les éléments.

Cependant, il y a un peu de réel gain lorsque vous l'utilisez pour "trouver" algorithmes de type. Imaginez, par exemple, une liste, de liste std::list où vous souhaitez trouver une valeur spécifique à l' x.

Ce que vous feriez sans sentinelles est:

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

Mais avec des sentinelles (bien sûr, la fin doit en fait être un véritable nœud de ce...):

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

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

return i;

Vous voyez il n'y a pas besoin de la branche supplémentaire pour tester pour la fin de la liste - la valeur est toujours la garantie d'être là, de sorte que vous retournez automatiquement end() si x ne peut pas être trouvé dans votre "valide" éléments.

Pour un autre cool et vraiment utile à l'application de sentinelles, voir "intro-tri", qui est l'algorithme de tri utilisé dans la plupart des std::sort des implémentations. Il a un frais variante de l'algorithme de partition qui utilise des sentinelles pour supprimer quelques branches.

Answer 3

La réponse à votre question (1) est dans la dernière phrase de la page Wikipédia: "en tant Que nœuds qui serait normalement lien vers NULL maintenant le lien "néant" (y compris le néant lui-même), il supprime le besoin d'une coûteuse opération de branche pour vérifier la valeur NULL."

Normalement, vous devez tester un nœud NULL avant d'y accéder. Si au contraire vous avez un valide néant nœud, alors vous n'avez pas besoin de faire ce premier essai, l'enregistrement d'une comparaison et d'une branche conditionnelle, qui peut par ailleurs être cher moderne superscalar Cpu lorsque la direction générale est mal prédit.

Answer 4

Je vais essayer de répondre dans le contexte de la bibliothèque de modèles standard:

1) Dans un appel à next()", NULL n'indique pas nécessairement en fin de liste. Que faire si une erreur de mémoire s'est produite? Retour d'un ganglion sentinelle, est une manière définitive à indiquer que la fin de la liste en avait eu lieu, et non pas une autre issue. En d'autres termes, NULL pourrait indiquer une variété de choses, et pas seulement en fin de liste.

2) Ce n'est qu'une méthode: lorsque vous créez votre liste, créer un privé nœud qui n'est pas partagée à l'extérieur de la classe (appelée "lastNode", par exemple). Lors de la détection que vous avez itéré jusqu'à la fin de la liste, ont "next()" de retour d'une référence à "lastNode". Ont également une méthode appelée "end()" de retour d'une référence à "lastNode". Enfin, en fonction de la façon dont vous mettez en œuvre votre classe, vous pourriez avoir besoin pour remplacer l'opérateur de comparaison pour que cela fonctionne correctement.

Exemple:

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