Question sur le boîtier du commutateur de la table de saut

Question

J'essaie de comprendre certaines choses sur les tables de saut et leur relation avec une déclaration de cas de commutation.

On m'a dit qu'une table de saut est une structure O(1) que le compilateur génère et qui rend la recherche de valeurs essentiellement aussi rapide que possible. Cependant, dans certains cas, une table de hachage/dictionnaire peut être plus rapide. On m'a également dit que cela ne fonctionnera que si le switch case contient ordered les valeurs des données.

Quelqu'un peut-il confirmer ou infirmer cette affirmation et expliquer ce qu'est une table de saut, son importance et sa complexité par rapport à l'utilisation d'un dictionnaire ou d'une table de hachage ? Merci.

Answer 1

A table de saut est une structure abstraite utilisée pour contrôle des transferts à un autre endroit. Goto, continue, et break sont similaires, sauf qu'ils transfèrent toujours vers un emplacement spécifique au lieu d'une possibilité parmi plusieurs. En particulier, ce flux de contrôle n'est pas le même qu'un appel de fonction. (L'article de Wikipedia sur tables de branchement est lié).

A déclaration de commutation est comment écrire des tables de saut en C/C++. Seule une forme limitée est fournie (peut seulement commuter sur les types intégraux) pour rendre les implémentations plus faciles et plus rapides dans ce cas commun. (La manière d'implémenter efficacement les tables de saut a été étudiée beaucoup plus pour les types intégraux que pour le cas général). Un exemple classique est Dispositif de Duff .

Cependant, la capacité totale d'une table de saut n'est souvent pas requise comme lorsque chaque cas aurait une déclaration de rupture. Ces "tables de saut limitées" sont une schéma différent qui ne fait que profiter de l'efficacité bien étudiée d'une table de saut, et sont courantes lorsque chaque "action" est indépendante des autres.

---

Les implémentations réelles des tables de saut prennent différentes formes, qui diffèrent principalement dans la façon dont le mappage de la clé à l'index est effectué. C'est dans cette mise en correspondance qu'interviennent des termes comme "dictionnaire" et "table de hachage", et ces techniques peuvent être utilisées indépendamment d'une table de saut. Dire qu'un code "utilise une table de saut" n'implique pas en soi que vous avez une recherche O(1).

Le compilateur est libre de choisir la méthode de recherche pour chaque instruction switch, et il n'y a aucune garantie que vous obtiendrez une implémentation particulière ; cependant, les options du compilateur telles que l'optimisation pour la vitesse et l'optimisation pour la taille doivent être prises en compte.

Vous devez envisager d'étudier les structures de données pour appréhender les différentes exigences de complexité qu'ils imposent. En bref, si par "dictionnaire" vous entendez un arbre binaire équilibré, alors il est O(log n) ; et une table de hachage dépend de sa fonction de hachage et de sa stratégie de collision. Dans le cas particulier des instructions switch, puisque le compilateur dispose de toutes les informations, il peut générer un dictionnaire O(log n). fonction de hachage parfaite ce qui signifie une recherche O(1). Cependant, ne vous perdez pas en regardant uniquement la complexité algorithmique globale : cela cache des facteurs importants.

Answer 2

Une table de saut est essentiellement un tableau de pointeurs vers des morceaux de code pour gérer les différents cas dans l'instruction switch. Il est plus probable qu'elle soit générée lorsque vos cas sont denses (c'est-à-dire que vous avez un cas pour chaque valeur possible dans une plage). Par exemple, avec une instruction comme :

switch (i) {
   case 1: printf("case 1"); break;
   case 2: printf("case 2"); break;
   case 3: printf("case 3"); break;
}

il pourrait générer un code à peu près équivalent à quelque chose comme ceci :

void case1() { printf("case 1"); }
void case2() { printf("case 2"); }
void case3() { printf("case 3"); }

typedef void (*pfunc)(void);

pfunc functions[3] = {case1, case2, case3};

if ((unsigned)i<3)    
    functions[i]();

La complexité est de O(K). Une table de hachage typique a également une complexité approximative de O(K) attendu complexité, bien que le pire cas soit typiquement O(N). La table de saut sera généralement plus rapide, mais elle ne sera généralement utilisée que si la table est assez dense, alors qu'une table de hachage/dictionnaire fonctionne assez bien même si les cas sont assez épars.

Answer 3

Supposons que vous ayez un tableau de procédures :

void fa() { 
 printf("a\n");
}

...

void fz() { 
 printf("it's z!\n");
}

typedef void (*F)();
F table[26]={fa,fb,...,fz};

Supposons que vous acceptiez un caractère (de a à z) en entrée de l'utilisateur et que vous exécutiez fc :

char c;
switch(c) {
   case 'a': fa();break;
   case 'b': fb();break;
   ...
   case 'z': fz();break;       
   default: exit(-1);
}

Idéalement, cela serait remplacé par quelque chose comme :

if (c<'a' || c>'z') exit(-1);
else (*table[c-'a'])();

Naturellement, vous pourriez agrandir la table pour que la vérification de la portée ne soit pas nécessaire.

Le compilateur le ferait pour un code arbitraire, pas nécessairement uniquement pour les appels de fonction, et le ferait en stockant l'adresse à laquelle sauter (essentiellement, un goto). Le C ne supporte pas directement une sorte de goto calculé (indexation dans une table ou autre), mais les instructions du CPU pour cela sont assez simples.

Answer 4

La compilation pour une déclaration de switch peut prendre plusieurs formes, selon les cas. Si les cas sont proches les uns des autres, il n'y a pas de problème : utilisez une table de saut. Si les cas sont éloignés les uns des autres, utilisez if (case == value) ou utilisez une carte. Le compilateur peut aussi utiliser une combinaison : des îlots de tables de saut déterminés par des vérifications if des plages de tables de saut.

Answer 5

Une table de saut est simplement un tableau de pointeurs de fonctions, vous pouvez vous représenter une table de saut comme suit :

int (*functions[10])(); /* Array of 10 Function Pointers */

D'après ce que j'ai compris, cela s'utilise avec une instruction case comme suit : chaque condition, case _, sera un index dans ce tableau, par exemple :

switch( a ) {
    case 1:  // (*functions[1])() // Call function containing actions in case of 1
        ...  
    case 2:  // (*functions[2])() // Call function containing actions in case of 2
        ...

Chaque cas, se transforme pour devenir simplement des fonctions[a]. Cela signifie que l'accès aux fonctions[9] est tout aussi rapide que l'accès aux fonctions[1]. Vous obtenez ainsi le temps O(1) que vous avez mentionné.

Évidemment, si vous avez le cas 1 et le cas 4907, ce ne sera pas une bonne méthode, et les méthodes de table de hachage/dictionnaire que vous avez mentionnées peuvent entrer en jeu.