C++ Declaración de conmutación larga o buscar con un mapa?

Question

En mi aplicación C++, tengo algunos valores que actúan como códigos para representar otros valores. Para traducir los códigos, he estado debatiendo entre utilizar una instrucción switch o un mapa stl. El interruptor se vería algo como esto:

int code; 
int value; 
switch(code) 
{ 
case 1: 
    value = 10; 
    break; 
case 2: 
    value = 15; 
    break; 
} 

El mapa sería un stl::map<int, int> y la traducción sería una simple búsqueda con el código utilizado como el valor de la clave.

¿Cuál es mejor/más eficiente/limpiador/aceptado? ¿Por qué?

Answer 1

Personalmente, usaría el mapa, ya que su uso implica una búsqueda de datos: usar un interruptor generalmente indica una diferencia en el comportamiento del programa. Además, la modificación de la asignación de datos es más fácil con un mapa que con un cambio.

Si el rendimiento es un problema real, la creación de perfiles es la única forma de obtener una respuesta utilizable. Un cambio puede no ser más rápido si las predicciones erróneas ocurren con la frecuencia suficiente.

Otro enfoque para pensar acerca de esto es que si no tendría más sentido para combinar el código y el valor asociado a una estructura de datos, especialmente si el rango de códigos y valores es estática:

struct Code { int code; int value; }; 

Code c = ... 

std::cout << "Code " << c.code << ", value " << c.value << std::end; 

Answer 2

Digo mapa si todo lo que hace es asignar un valor. Mi razón es que es extensible sin cambiar el código, que no es su declaración de cambio.

por cierto, ¿qué tal un enum?

Answer 3

Si los códigos son lo suficientemente contigua y su permiso de rango que estarían mucho mejor con la antigua matriz sencillo, algo así como

int lookup[] = {-1, 10, 15, -1 222}; 

continuación, la sentencia switch se puede reescribir como simplemente como

valor = búsqueda [código];

todas las otras opciones introducen un costo adicional hasta cierto punto.

Answer 4

Creo que el código generado de la estructura del conmutador puede crecer bastante si la cantidad de "códigos" aumenta, en cuyo caso creo que stl :: map es más apropiado.

Answer 5

La instrucción de cambio sería más rápida, pero si esto no está en el cuello de botella de rendimiento de su aplicación, realmente no debería preocuparse por eso.

Vaya por lo que hace que su código sea más fácil de mantener a largo plazo.

Su muestra es demasiado corta para realizar cualquier llamada significativa al respecto.

Answer 6

Se más bien depende de cuáles son los códigos y cuántos hay. Los buenos compiladores tienen varios trucos que utilizan para optimizar las sentencias de cambio, algunas de las cuales no emplearán con enunciados directos si/entonces. La mayoría son lo suficientemente brillantes como para hacer cálculos simples o usar tablas de búsqueda/salto para los casos 0, 1, 2 o 3, 6, 9, por ejemplo.

Por supuesto que algunos no lo hacen, y muchos se frustran fácilmente con conjuntos de valores inusuales o irregulares. Además, si el código para manejar varios casos se ve notablemente similar, cortar y pegar puede ocasionar problemas de mantenimiento.Si usted tiene muchos códigos, pero se pueden dividir de forma algorítmica en grupos, es posible considerar varios/anidada sentencias switch, por ejemplo, en lugar de:

switch (code) { 
    case 0x0001: ... 
    case 0x0002: ... 
    ... 
    case 0x8001: ... 
    case 0x8002: ... 
    ... 
} 

Es posible utilizar:

if (code & 0x8000) { 
    code &= ~0x8000; 
    switch (code) { 
     case 0x0001: ... // actually 0x8001 
     case 0x0002: ... // actually 0x8002 
     ... 
    } 
} 
else { 
    switch (code) { 
     case 0x0001: ... 
     case 0x0002: ... 
     ... 
    } 
} 

Muchos intérpretes de lengua decodifican Opcodes de esta manera, ya que un código de operación de un solo byte puede tener información adicional empaquetada en varios bits, y la transcripción de todas las combinaciones posibles y sus manejadores sería repetitiva y frágil. Por otro lado, el exceso de manipulación de bits puede vencer cualquier optimización por parte del compilador y ser contraproducente.

A menos que esté seguro de que se trata de un cuello de botella de rendimiento real, evitaría una optimización prematura: hágalo de cualquier manera que le parezca razonablemente robusta y rápida de implementar. Como y si su aplicación se ejecuta muy lentamente, perfórela y optimícela según corresponda.

Answer 7

• Leer los números enteros en una matriz/vector
• ordenar la matriz/vector
• uso bsearch en la matriz subyacente

Answer 8

soy parcial a las operaciones de búsqueda mesas mí mismo, porque el interruptor inusualmente largo las declaraciones me parecen confundir una separación entre código y datos. También creo que las tablas se prestan mejor para futuros cambios y mantenimiento.

Todo en mi humilde opinión, por supuesto.

Answer 9

Si puede usar tr1 puede usar unordered_map para calcular los valores (los hash también pueden ser muy rápidos), lo que debería hacer que la mayoría de las búsquedas sean constantes.

Sin embargo, a menos que tenga datos de creación de perfiles para indicar que esto es un cuello de botella en su programa, codifíquelo en el enfoque que tenga más sentido desde el punto de vista del diseño.

Answer 10

Sugiero usar una tabla estática, constante, de pares. Esta es otra forma de la tabla de consulta:

struct Table_Entry 
{ 
    int code; 
    int value; 
}; 

static const Table_Entry lookup_table[] = 
{ 
    {1, 10}, 
    {2, 15}, 
    {3, 13}, 
}; 

static const unsigned int NUM_TABLE_ENTRIES = 
    sizeof(lookup_table)/sizeof(lookup_table[0]); 

Una ventaja de esto es que la tabla se genera en tiempo de compilación, a diferencia de un std::map que debe ser inicializado durante el tiempo de ejecución. Si las cantidades son grandes, puede usar std::lower_bound para encontrar la entrada, siempre que la tabla esté ordenada.

Otra ventaja es que esta técnica se basa en datos. Los datos pueden cambiar sin cambios en el motor de búsqueda. Los cambios en el código o el proceso pueden requerir pruebas de regresión serias, pero los cambios en los datos pueden no serlo; YMMV.

Esto es similar a lo que podría generar un compilador.

Answer 11

Normalmente, sugiero un mapa o matriz de búsqueda o incluso un monstruo híbrido de búsqueda (suponiendo que se está optimizando la velocidad o el tamaño del código en lugar de la legibilidad, por supuesto), pero vale la pena señalar que las nuevas versiones de GCC son lo suficientemente inteligentes como para reemplazar asignaciones de interruptor/caja como esta para buscar tablas. Si bien esto no es tan bueno para las claves totalmente dispersas, puede ser si sus claves están en grupos como: 0, 1, 2, 3, 4, 5, 11, 12, 13, 14, 15, 193, 194 , 195, 196, 197, 198 ...

Por supuesto si es posible que te guste algo de aritmático para hacer la conversión, incluso mejor (generalmente).Nunca pases por alto cambiar, intercambiar endiancias o matemáticas más tradicionales cuando hagas algo como esto.