Jump Table Switch Caso pregunta

Question

Estoy tratando de entender algunas cosas sobre las tablas de salto y su relación entre una declaración de cambio de mayúsculas y minúsculas.

Me dijeron que una tabla de salto es una estructura O (1) que el compilador genera, lo que hace que la búsqueda de valores sea tan rápida como sea posible. Sin embargo, en algunos casos, un Hashtable/Dictionary puede ser más rápido. También me dijeron que esto solo funcionará si la caja del interruptor contiene ordered valores de datos.

¿Puede alguien confirmar o negar esto y explicar qué es una tabla de salto, su importancia y la complejidad del tiempo versus el uso de un diccionario o hashtable? Gracias.

Answer 1

A tabla de salto es una estructura abstracta utilizada para control de transferencia a otra ubicación. Goto, continuar y romper son similares, excepto que siempre se transfieren a una ubicación específica en lugar de a una posibilidad de muchos. En particular, este flujo de control no es lo mismo que una llamada a función. (El artículo de Wikipedia sobre branch tables está relacionado.)

Una declaración interruptor es cómo escribir saltar tablas en C/C++. Solo se proporciona una forma limitada (solo puede activar tipos integrales) para hacer que las implementaciones sean más fáciles y rápidas en este caso común. (Cómo implementar tablas de saltos de manera eficiente se ha estudiado mucho más para los tipos integrales que para el caso general.) Un ejemplo clásico es Duff's Device.

Sin embargo, a menudo no se requiere la capacidad completa de una tabla de salto, como cuando cada caso tiene una declaración de interrupción. Estas "tablas de salto limitados" son un patrón diferente , que sólo se está aprovechando de la eficiencia bien estudiado de una tabla de saltos, y son comunes cuando cada "acción" es independiente de los demás.

---

Las implementaciones reales de las tablas de salto toman diferentes formas, la mayoría difieren en cómo se realiza la asignación de la clave para indexar. Ese mapeo es donde entran términos como "diccionario" y "tabla hash", y esas técnicas se pueden usar independientemente de una tabla de salto. Decir que algún código "usa una tabla de salto" no implica por sí solo que tiene una búsqueda O (1).

El compilador es libre de elegir el método de búsqueda para cada instrucción switch, y no hay garantía de que obtendrá una implementación particular; sin embargo, se deben tener en cuenta las opciones del compilador, como optimizar para la velocidad y optimizar para el tamaño.

Debe estudiar para estudiar las estructuras de datos para conocer los diferentes requisitos de complejidad que imponen. En resumen, si por "diccionario" te refieres a un árbol binario equilibrado, entonces es O (log n); y una tabla hash depende de su función hash y estrategia de colisión. En el caso particular de las instrucciones switch, dado que el compilador tiene información completa, puede generar un perfect hash function que significa O (1) búsqueda. Sin embargo, no te pierdas simplemente observando la complejidad algorítmica general: oculta factores importantes.

Answer 2

La compilación de una instrucción de cambio puede tomar muchas formas, dependiendo de los casos. Si los casos están muy juntos, es obvio: use una mesa de saltos. Si los casos están muy separados, use if (case == value) o use un mapa. O un compilador puede usar una combinación: islas de tablas de salto determinadas por si las verificaciones de la tabla de saltos varían.

Answer 3

Supongamos que tenemos una serie de procedimientos:

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

... 

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



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

Supongamos que se acepta un carácter (de AZ) de entrada del usuario y ejecuta fc:

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

Idealmente, debería ser reemplazado por algo como:

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

Naturalmente, puede hacer que la tabla sea más grande para que el rango compruebe wo no será necesario.

El compilador haría esto por código arbitrario, no necesariamente llamadas de función solamente, y lo haría almacenando la dirección para saltar a (esencialmente, un goto). C no admite directamente ningún tipo de goto calculado (indexación en una tabla o de otro modo), pero las instrucciones de la CPU son bastante simples.

Answer 4

Una tabla de salto es básicamente una matriz de punteros a trozos de código para manejar los diversos casos en la declaración de cambio. Es más probable que se genere cuando sus casos son densos (es decir, tiene un caso para cada valor posible en un rango). Por ejemplo, dada una declaración como:

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

podría generar código más o menos equivalente a algo como esto:

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

Esta O (K) tiene complejidad. Una tabla hash típica también tiene aproximadamente O (K) complejidad esperada, aunque el peor caso suele ser O (N). La tabla de salto generalmente será más rápida, pero generalmente solo se usará si la tabla será bastante densa, mientras que una tabla/diccionario de hash funciona bastante bien incluso cuando los casos sean bastante escasos.

mesa

Answer 5

Un salto es simple una matriz de punteros de función, usted puede representar una tabla de saltos más o menos así:

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

Desde mi entender, esto se utiliza con una declaración de caso de este modo: cada condición , caso _, será un índice en esta matriz, así por ejemplo:

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

cada caso, se transforma para convertirse simplemente funciones [a]. Esto significa que acceder a las funciones [9] es tan rápido como acceder a las funciones [1]. Te da el tiempo O (1) que mencionaste.

Obviamente, si tiene el caso 1, y el caso 4907, este no será un buen método, y los métodos de la tabla hash/diccionario que mencionó pueden entrar en juego.

Answer 6

estudiar más en detalle Jerry's answer y otros

Dado:

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

que podría tener algo como lo siguiente:

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

El compilador podría utilizar una tabla de saltos para indexar {f1, f2, f3}

El compilador puede hacer inlining al crear la tabla que tiene f1, f2, f3 estableciendo x directamente a 6,9,8

Pero si usted escribió las funciones, y rodó su propia tabla de saltos, f1,f2,f3 podría estar en cualquier lugar, pero el compilador sabrá ponerlos cerca de la switch crear mucho mejor código localidad de lo que podría.

Tenga en cuenta que en muchos casos el compilador generará un guardia para comprobar si i está en el rango (o manejar la default) y si está seguro de que siempre es uno de los casos, usted podría saltar esa

lo interesante es que por debajo de un pequeño número de casos, y bajo diferentes parámetros del compilador (compilador dependiente) la switch no necesita usar una tabla, sino que sólo lo hacen IFS, similar a:

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

o podría optimice esto (donde las pruebas simples son una instrucción) a:

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

El mejor consejo es buscar en el conjunto generado para ver lo que el compilador hizo a tu código en su arquitectura, g ++ en Linux/Intel va a generar algo como lo siguiente, si hay una tabla de saltos

(nota que tenía que ir a 5 case declaraciones para forzar la tabla de saltos, se utilizan IFS por debajo de ese número de case declaraciones)

Tenga en cuenta que los pequeños agujeros estarán en la tabla de saltos para hacer el 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; 
} 

generaría el siguiente código ensamblador (// comentarios son míos):

 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