Case de commutateur de table de saut question

Question

J'essaie de comprendre certaines choses à propos des tables de sauts et de sa relation entre 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, ce qui rend la recherche de valeurs essentiellement aussi rapide que possible. Cependant, dans certains cas, un Hashtable/Dictionary peut être plus rapide. On m'a également dit que cela ne fonctionnera que si le boîtier de commutateur contient des valeurs de données ordered. Est-ce que quelqu'un peut confirmer ou nier cela et expliquer ce qu'est une table de saut, son importance et la complexité du temps 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 transférer le contrôle à un autre emplacement. Goto, continue et break sont similaires, sauf qu'ils sont toujours transférés vers un emplacement spécifique au lieu d'une possibilité parmi plusieurs. En particulier, ce flux de contrôle n'est pas identique à un appel de fonction. (L'article de Wikipedia sur branch tables est lié.)

Une instruction switch est comment écrire des tables de saut en C/C++. Seule une forme limitée est fournie (ne peut que commuter sur des types entiers) pour rendre les implémentations plus faciles et plus rapides dans ce cas courant. (Comment implémenter efficacement les tables de sauts a été étudié beaucoup plus pour les types entiers que pour le cas général.) Un exemple classique est Duff's Device.

Cependant, la capacité complète d'une table de saut n'est souvent pas nécessaire, comme lorsque chaque cas doit avoir une déclaration de rupture. Ces "tables de sauts limitées" sont un motif différent, qui ne tire parti que de l'efficacité bien étudiée d'une table de saut, et sont courantes lorsque chaque "action" est indépendante des autres.

---

Les mises en œuvre réelles de tables de sauts prennent différentes formes, différant principalement dans la manière dont la mise en correspondance d'index est effectuée. Ce mappage est l'endroit où les termes "dictionnaire" et "table de hachage" entrent en jeu, 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 ayez une recherche O (1).

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

Vous devriez étudier les structures de données pour avoir une idée des différentes exigences de complexité qui leur sont imposées. Brièvement, si par "dictionnaire" vous voulez dire un arbre binaire équilibré, alors c'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 a des informations complètes, il peut générer un perfect hash function ce qui signifie une recherche O (1). Cependant, ne vous perdez pas en regardant simplement la complexité algorithmique globale: elle cache des facteurs importants.

Answer 2

La compilation d'une instruction switch peut prendre plusieurs formes, selon les cas. Si les cas sont proches les uns des autres, cela ne pose aucun problème: utilisez une table de saut. Si les cas sont éloignés, utilisez if (cas == valeur) ou utilisez une carte. Ou un compilateur peut utiliser une combinaison: des îlots de tables de sauts déterminés par si des contrôles de la gamme de tables de sauts.

Answer 3

Supposons que vous ayez une série 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 acceptez un caractère (de az) d'entrée de l'utilisateur et exécuter fc:

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

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

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

Naturellement, vous pourriez augmenter la taille de la table Ce ne sera pas nécessaire.

Le compilateur ferait ceci pour le code arbitraire, pas nécessairement seulement les appels de fonction, et le ferait en stockant l'adresse à sauter à (essentiellement, un goto). C ne supporte pas directement n'importe quel type de goto calculé (indexation dans une table ou autre), mais les instructions de CPU pour cela sont plutôt simples.

Answer 4

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 susceptible d'être généré lorsque vos cas sont denses (c'est-à-dire que vous avez un cas pour chaque valeur possible dans une plage). Par exemple, étant donné une déclaration 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](); 

Cela a O (K) complexité. Une table de hachage typique a aussi approximativement O (K) complexité attendue, bien que le cas le plus défavorable soit typiquement O (N). La table des sauts 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/dictionnaire de hachage fonctionne assez bien même si les cas sont assez clairsemés.

Answer 5

Une table de saut est simple un tableau de pointeurs de fonction, vous pouvez l'image d'une table de saut à peu près comme ceci:

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

De ma compréhension, il est utilisé avec une déclaration de cas comme ceci: chaque condition , cas _, sera un index dans ce tableau, donc 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, transforme pour devenir simplement des fonctions [a]. Cela signifie que l'accès aux fonctions [9] est aussi rapide que l'accès aux fonctions [1]. Vous donner le O (1) fois que vous avez mentionné. De toute évidence, si vous avez le cas 1 et le cas 4907, cela ne va pas être une bonne méthode, et les méthodes de table de hachage/dictionnaire que vous avez mentionnées peuvent entrer en jeu.

Answer 6

pour élaborer davantage sur Jerry's answer et d'autres

Vu:

int x=1; 
switch (i) { 
    case 1: x=6; break; 
    case 2: x++; 
    // Fall through 
    case 3: x+=7; break; 
} 

vous pourriez avoir quelque chose comme ce qui suit:

int f1() {return 6;} 
int f2() {return 1+f3();} 
int f3() {return 8;} 

Le compilateur peut utiliser une table de saut à l'index {f1, f2, f3}

Le compilateur peut faire inline lors de la création de la table ayant f1, f2, f3 de réglage x directement à 6,9,8

Mais si vous avez écrit les fonctions et rouliez votre propre table de saut, f1,f2,f3 pourrait être partout, mais le compilateur saura les mettre près de la switch créer beaucoup mieux localité de code que vous pourriez.

Notez que dans de nombreux cas, le compilateur génère un garde pour vérifier si i est à portée (ou gérer la default) et si vous êtes sûr qu'il est toujours l'un des cas, vous pouvez sauter cette

la chose intéressante est que pour moins d'un petit nombre de cas, et sous différents drapeaux du compilateur (dépend du compilateur) le switch ne serait pas utiliser une table, mais se contentait de faire ifs, semblable à:

if (i==1) x=f1(); 
else if (i==2) x=f2(); 
else if (i==3) x=f3(); 

ou il pourrait optimiser ceci (où les tests simples sont une instruction) à:

x=(i==1) ? f1() 
: (i==2) ? f2() 
: (i==3) ? f3() 
: x; 

Le meilleur conseil est de regarder l'ensemble généré pour voir ce que le compilateur a fait à votre code sur votre architecture, g ++ sur Linux/Intel va générer quelque chose comme ce qui suit, s'il y a une table de saut

(note que je devais aller à 5 case déclarations pour forcer la table de saut, il a utilisé ifs dessous de ce nombre de case déclarations)

Notez que les petits trous seront dans la table de saut pour faire le default

int foo(int i) 
{ 
    int x=1; 
    switch (i) { 
     case 1: x=6; break; 
     case 2: x++; 
     // Fall through 
     case 3: x+=7; break; 
     case 4: x+=2; break; 
     case 5: x+=9; break; 
    } 
    return x; 
} 

générerait le code assembleur suivant (// commentaires sont les miens):

 cmp  edi, 5      //make sure it is not over 5 
     ja  .L2      //jump to default case 
     mov  edi, edi 
     jmp  [QWORD PTR .L4[0+rdi*8]] // use the jump table at label L4: 
.L4: 
     .quad .L2      // if i=0, set x=1 (default) 
     .quad .L9      // f1() see below 
     .quad .L10      // f2() see below 
     .quad .L6      // f3() see below 
     .quad .L7      // f4() see below 
     .quad .L8      // f5() see below 
.L10: 
     mov  eax, 9      // x=9 
     ret 
.L9: 
     mov  eax, 6      // x=6 
     ret 
.L8: 
     mov  eax, 10     // x=10 
     ret 
.L6: 
     mov  eax, 8      // x=8 
     ret 
.L7: 
     mov  eax, 3      // x=3 
     ret 
.L2: 
     mov  eax, 1      // default, x was 1, noop is: x=1 
     ret