Jump Table Switch Fall Frage

Question

Ich versuche, einige Dinge über Jump-Tabellen und seine Beziehung zwischen einer Switch-Case-Anweisung zu verstehen.

Mir wurde gesagt, dass eine Jump-Tabelle eine O (1) -Struktur ist, die der Compiler generiert, die das Nachschlagen von Werten im Wesentlichen so schnell wie möglich macht. In manchen Fällen ist ein Hashtable/Dictionary jedoch schneller. Mir wurde auch gesagt, dass dies nur funktioniert, wenn der Switch-Fall ordered Datenwerte enthält.

Kann jemand bitte bestätigen oder leugnen dies und erklären, was eine Sprungtabelle ist, ist es wichtig und die Zeit Komplexität im Vergleich zu einem Wörterbuch oder Hashtable. Vielen Dank.

Answer 1

Eine Sprungtabelle ist eine abstrakte Struktur verwendet, um die Kontrolle an einen anderen Ort zu übertragen. Goto, Fortfahren und Pause sind ähnlich, nur dass sie immer an einen bestimmten Ort übertragen werden und nicht nur eine Möglichkeit von vielen. Insbesondere ist dieser Kontrollfluss nicht der gleiche wie ein Funktionsaufruf. (Wikipedia Artikel auf branch tables ist verwandt.)

Eine switch Anweisung ist, wie Sprungtabellen in C/C++ schreiben. Es ist nur eine eingeschränkte Form vorgesehen (kann nur integrierte Typen einschalten), um Implementierungen in diesem häufigen Fall einfacher und schneller zu machen. (Wie Sprungtabellen effizient implementiert werden, wurde viel mehr für ganzzahlige Typen als für den allgemeinen Fall untersucht.) Ein klassisches Beispiel ist Duff's Device.

Allerdings die volle Fähigkeit einer Sprungtabelle ist oft nicht erforderlich, wie wenn jeder Fall eine Pause-Anweisung hätte. Diese "begrenzten Sprungtabellen" sind ein anderes Muster, das nur die Vorteile einer gut untersuchten Effizienz der Sprungtabelle ausnutzt, und die üblich sind, wenn jede "Aktion" unabhängig von den anderen ist.

---

Tatsächliche Implementierungen von Sprungtabellen nehmen verschiedene Formen, meist in unterschiedlichen, wie der Schlüssel zum Indexabbildung erfolgt. Diese Zuordnung ist, wo Begriffe wie "Wörterbuch" und "Hash-Tabelle" kommen, und diese Techniken können unabhängig von einer Sprungtabelle verwendet werden. Zu sagen, dass ein Code "eine Sprungtabelle verwendet" bedeutet nicht, dass Sie O (1) Lookup haben.

Der Compiler kann die Lookup-Methode für jede Switch-Anweisung frei wählen, und es gibt keine Garantie, dass Sie eine bestimmte Implementierung erhalten; Compileroptionen wie Optimize-for-Speed ​​und Optimize-for-Size sollten jedoch berücksichtigt werden.

Sie sollten in die Untersuchung von Datenstrukturen Einblick in die verschiedenen Komplexität Anforderungen durch sie auferlegt bekommen. Kurz gesagt, wenn Sie mit "Wörterbuch" einen ausgeglichenen binären Baum meinen, dann ist es O (log n); und eine Hash-Tabelle hängt von ihrer Hash-Funktion und Kollisionsstrategie ab. Im speziellen Fall von switch-Anweisungen kann der Compiler, da er vollständige Informationen hat, eine perfect hash function generieren, was O (1) Lookup bedeutet. Gehen Sie jedoch nicht verloren, wenn Sie nur die algorithmische Komplexität betrachten: Sie versteckt wichtige Faktoren.

Answer 2

Kompilieren für eine Switch-Anweisung kann je nach Fall viele Formen annehmen. Wenn die Fälle nahe beieinander liegen, ist es kein Kinderspiel: Verwenden Sie eine Sprungtabelle. Wenn die Fälle weit auseinander liegen, verwende if (case == value) oder verwende eine Map. Oder ein Compiler kann eine Kombination verwenden: Inseln von Sprungtabellen, die durch Überprüfungen der Sprungtabelle bestimmt werden.

Answer 3

Angenommen, Sie eine Reihe von Verfahren hatte:

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

... 

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



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

Sie ein Zeichen (von az) akzeptieren Angenommen, der Eingaben vom Benutzer und laufen fc:

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

Idealer werden dies würde ersetzt durch etwas wie:

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

Natürlich könnten Sie die Tabelle größer machen, so dass die Bereichsprüfung wo Es ist nicht nötig.

Der Compiler würde dies für beliebigen Code tun, nicht unbedingt nur für Funktionsaufrufe, und würde dies tun, indem er die Adresse speichert, zu der gesprungen werden soll (im Wesentlichen ein Goto). C unterstützt nicht direkt irgendeine Art von berechnetem Goto (Indizierung in eine Tabelle oder anders), aber die CPU-Anweisungen dafür sind ziemlich einfach.

Answer 4

Eine Jump-Tabelle ist im Grunde ein Array von Zeigern auf Teile des Codes, um die verschiedenen Fälle in der switch-Anweisung zu behandeln. Es wird am wahrscheinlichsten generiert, wenn Ihre Fälle dicht sind (d. H. Sie haben einen Fall für jeden möglichen Wert in einem Bereich). Um zum Beispiel eine Aussage wie angegeben:

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](); 

Dies hat O (K) Komplexität:

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

es Code entspricht in etwa so etwas wie diese erzeugen könnte. Eine typische Hash-Tabelle hat auch ungefähr die Komplexität, obwohl der schlechteste Fall typischerweise 0 (N) ist. Die Sprungtabelle wird normalerweise schneller sein, aber sie wird normalerweise nur verwendet, wenn die Tabelle ziemlich dicht ist, wohingegen eine Hashtabelle/ein Wörterbuch ziemlich gut funktioniert, selbst wenn die Fälle ziemlich spärlich sind.

Answer 5

Eine Sprungtabelle ist einfach ein Array von Funktionszeigern, können Sie eine Sprungtabelle wie so grob Bild:

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

Von meinem Verständnis ist dies mit einem Fall-Anweisung wie folgt: jede Bedingung , Fall _ wird ein Index in diesem Array sein, so zum Beispiel:

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 
     ... 

Jeder Fall einfach Funktionen werden verwandelt [a]. Das bedeutet, dass der Zugriff auf Funktionen [9] genauso schnell ist wie der Zugriff auf Funktionen [1]. Ihnen die O (1) Zeit geben, die Sie erwähnten.

Offensichtlich, wenn Sie Fall 1 und Fall 4907 haben, wird dies nicht eine gute Methode sein, und die Hash-Tabelle/Dictionary-Methoden, die Sie erwähnten, können ins Spiel kommen.

Answer 6

weiter zu erarbeiten auf Jerry's answer und andere

Gegeben:

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

Sie könnte so etwas wie die folgenden:

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

Der der Compiler eine Sprungtabelle zu indizieren verwenden könnte {f1, f2, f3}

Der Compiler kann inlining wenn Erstellen der Tabelle mit f1, f2, f3x direkt an 6,9,8

Einstellung Aber wenn Sie die Funktionen geschrieben, und Ihre eigenen Sprungtabelle gerollt, f1,f2,f3 könnte überall sein, aber der Compiler wissen sie in der Nähe der switch viel besser zu schaffen setzen Code-Ort als Sie könnten.

Beachten Sie, dass in vielen Fällen der Compiler eine Wache generieren zu überprüfen, ob i in Reichweite ist (oder die default zu behandeln), und wenn Sie sicher sind, dass es immer eine der Fälle ist, könnten Sie überspringen, dass

das interessante daran ist, dass für die unter einer kleinen Anzahl von Fällen und unter verschiedenem Compiler-Flags (Compiler-abhängig) die switch keine Tabelle verwenden würde, würde aber ifs nur tun, ähnlich wie:

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

oder es könnte Optimiere dies (wobei einfache Tests eine Anweisung sind) an:

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

Der beste Rat ist bei der Montage sehen erzeugt, um zu sehen, was der Compiler den Code auf Ihrer Architektur haben, g ++ auf Linux/Intel etwas wie die folgende erzeugen wird, wenn es eine Sprungtabelle ist

(note I bis 5 case Aussagen gehen musste die Sprungtabelle zu zwingen, verwendet es ifs unterhalb dieser Anzahl von case Aussagen)

Beachten sie, dass kleine Löcher in der Sprungtabelle wird die default

zu tun

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

den folgenden Assembler-Code generieren würde (// Kommentare sind Mine):

 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