¿Qué sucede si el switch tiene más de 5000 case. ¿Cuáles son los inconvenientes y cómo podemos reemplazarlo con algo más rápido?Declaración de cambio con un gran número de casos
Nota: No espero utilizar una matriz para almacenar casos, ya que es lo mismo.
No hay ninguna razón específica para pensar que desee algo más que un enunciado de cambio/caso (y de hecho espero activamente que no sea útil). El compilador debe crear un código de despacho eficiente, que podría implicar una combinación de tablas estáticas [dispersas] e indexación directa, binario de ramificación, etc .; tiene una idea de los valores estáticos de los casos y debería hacer un excelente trabajo (reajustarlo sobre la marcha cada vez que cambie los casos, mientras que los nuevos valores que no encajan bien con un enfoque artesanal, como valores tremendamente diferentes) cuando tenía una búsqueda de matriz bastante compactada, podría requerir la reelaboración del código o causar silenciosamente la saturación de la memoria o una caída del rendimiento).
La gente realmente se preocupaba por este tipo de cosas cuando C intentaba convencer a los programadores de ensamblaje de núcleo duro ... los compiladores eran responsables de generar un buen código. Dicho de otra manera: si no se rompe (mensurablemente), no lo arregles.
De manera más general, es muy bueno para ser curioso acerca de este tipo de cosas y obtener ideas de la gente sobre alternativas y sus consecuencias en el rendimiento, pero si realmente cuidado y la diferencia de rendimiento podría hacer una diferencia útil para su programa (sobre todo si el perfilado lo sugiere), luego siempre comparativa con su programa haciendo un trabajo real.
Sí, creo que el compilador hará efectivo el cambio de conmutador, aunque 5000 casos no son normales. Probablemente la matriz de indicadores de función sea mejor, al menos el código se verá mejor. – Mine
@Mine: la matriz del puntero a la función hará que el código sea legible. pero estoy buscando una solución más rápida. – MarsRover
@MarsRover la matriz del puntero de función ES rápida. Una multiplicación, deferencia, un puntero y una llamada. Es difícil tener menos instrucciones. Además, estoy de acuerdo con Tony, si el diseño no es un problema, ¿estás seguro de que el rendimiento sufre? –
Intenta usar la clase de diccionario con los valores de delegado. Al menos hace que el código sea un poco más legible.
El único requisito explícito de la pregunta era "algo más rápido" ... un mapa hash probablemente sea significativamente más lento, al igual que una llamada forzada fuera de línea (que suele ser un orden de magnitud más lento que el código en línea para una única operación trivial) que es donde importa la velocidad de la conmutación) especialmente si los casos no se distribuyen aleatoriamente en un amplio rango. –
Como reflexión ... en caso de que uno se quede atrapado con un compilador viejo/defectuoso/ineficiente o simplemente adore la piratería.
El trabajo interno de switch declaración consta de dos partes. Encontrar la dirección para saltar, y saltar bien allí. Para la primera parte necesita usar una tabla para encontrar la dirección. Si aumenta el número de casos, la tabla se hace más grande: la búsqueda de la dirección para saltar lleva tiempo. Este es el punto que los compiladores intentan optimizar, combinando varias técnicas, pero un enfoque fácil es usar la tabla directamente, que depende del espacio de valor de caso.
En una parte posterior del ejemplo de la servilleta;
switch (n) {
case 1: foo(); break;
case 2: bar(); break;
case 3: baz(); break;
}
con tal pieza de compilador de código puede crear una matriz de jump_addresses y directamente obtener la dirección de array [n]. Ahora la búsqueda acaba de tomar O (1). Pero si tuviera un interruptor, como a continuación:
switch (n) {
case 10: foo(); break;
case 17: bar(); break;
case 23: baz(); break;
// and a lot other
}
compilador necesita para generar una tabla que contiene CASE_ID, pares jump_address y el código para buscar a través de esa estructura que la peor aplicación puede tomar O (n). (Los compiladores decentes optimizan el infierno de tal escenario cuando se desencadenan completamente habilitando sus indicadores de optimización en un grado tal que cuando necesite depurar dicho código optimizado su cerebro empiece a freír).
Entonces, ¿se puede hacer esta pregunta? todo usted mismo en el nivel C para vencer al compilador? y lo curioso es que al crear tablas y buscarlas parece fácil, saltar a un punto variable usando goto no es posible en el estándar C. Entonces existe la posibilidad de que si no va a utilizar punteros a función debido a la estructura de código o sobrecarga, estás atascado ... bueno si no estás usando GCC. GCC tiene una función no estándar llamada Labels as Values que le ayuda a obtener punteros a las etiquetas.
Para completar el ejemplo, se puede escribir la segunda sentencia switch con "etiquetas como valores" característica de esta manera:
const void *cases[] = {&&case_foo, &&case_bar, &&case_baz, ....};
goto *labels[n];
case_foo:
foo();
goto switch_end;
case_bar:
bar();
goto switch_end;
case_baz:
baz();
goto switch_end;
// and a lot other
switch_end:
Por supuesto, si usted está hablando cerca de 5000 casos, es mucho mejor si se escribe una una pieza de código para crear este código para usted, y probablemente sea la única forma de mantener dicho software.
Como notas de cierre; ¿Esto mejorará tu trabajo diario? No. ¿Esto mejorará tus habilidades? Sí, y hablando por experiencia, una vez descubrí que mejoraba un algoritmo de seguridad en una tarjeta inteligente simplemente optimizando los valores de los casos. Es un mundo extraño.
gracias por la respuesta, esto no es parte de mi diseño, pero alguien me hizo esta pregunta y traté de explicarlo usando una matriz de puntero a la función. Pero esa no fue una manera rápida. Yo mismo estaba buscando una forma más rápida, no estoy hablando de legibilidad o diseño aquí. – MarsRover
La declaración de cambio grande, generalmente autogenerada, puede tardar mucho tiempo en compilarse. Pero me gusta la idea de que el compilador optimice la declaración de cambio.
Una forma de separar la instrucción switch es usar bucketing,
int getIt(int input)
{
int bucket = input%16;
switch(bucket)
{
case 1:
return getItBucket1(input);
case 2:
return getItBucket2(input);
...
...
}
return -1;
}
Así que en el código anterior, nos separamos nuestra sentencia switch en 16 partes. Es fácil cambiar la cantidad de depósitos en el código generado automáticamente.
Este código ha agregado el costo de ejecución de una capa de direccionamiento indirecto o función-llamada. . Pero considerando los cubos definidos en diferentes archivos, es más rápido compilarlos en paralelo.
¿Por qué le gustaría comparar 5000 casos? ¿No puedes comprimir/refactorizar el código para que tengas menos casos en cada segmento de código? – mmoment
Puede usar ** una serie de indicadores de funciones **, es mucho más rápido que cualquier comparación PERO mi pregunta es ... ¿cómo puede ** administrar y mantener ** el código con una instrucción 'switch/case' con 5000 casos ? –
Si necesita cambiar entre 5000 casos, parece una mala intención de diseño. De lo contrario, iría por punteros de función también. – dtech