¿El orden del caso en la declaración de Switch puede variar el rendimiento?

Question

Let decir que tengo una sentencia switch de la siguiente manera

switch(alphabet) { 

    case "f": 
     //do something 
     break; 

    case "c": 
     //do something 
     break; 

    case "a": 
     //do something 
     break; 

    case "e": 
     //do something 
     break; 

} 

Supongamos ahora que sé que la frecuencia de tener Alphabet e es más alto seguido por A, C y F, respectivamente. Por lo tanto, sólo reestructurado el orden comunicado case y les hacen como sigue:

switch(alphabet) { 

    case "e": 
     //do something 
     break; 

    case "a": 
     //do something 
     break; 

    case "c": 
     //do something 
     break; 

    case "f": 
     //do something 
     break; 
} 

Será la segunda declaración switch ser más rápido que la primera switch declaración? Si es así y si en mi programa necesito llamar a esta declaración switch decir muchas veces, ¿será una mejora sustancial? O si no, ¿cómo puedo usar mi conocimiento de frecuencia para mejorar el rendimiento?

Answer 1

No tanto que deba preocuparse. Ciertamente no es algo que pueda predecirse.

Con etiquetas de mayúsculas y minúsculas, el compilador realmente utiliza una tabla hash interna que asigna las cadenas a los índices en una tabla de salto. Entonces, la operación es realmente O (1), independientemente del número de etiquetas.

Para etiquetas enteras, creo que el código real que se genera depende del número de etiquetas y si los números son consecutivos (o "casi" consecutivos). Si son consecutivos (1, 2, 3, 4, ...), se transformarán en una mesa de saltos. Si hay muchos de ellos, entonces se usará la tabla de salto Hashtable + (como con cuerdas). Si solo hay unas pocas etiquetas y no son tablas para transformarlas inmediatamente en una tabla de salto, solo entonces se transformará en una serie de sentencias if..then..else.

En general, sin embargo, debe escribir código para que lo lea, no para que el compilador pueda producir código "más rápido".

(Nota mi descripción anterior es un detalle de implementación de cómo el compilador de C# funciona internamente: no se debe confiar en él siempre trabajando así - de hecho, puede que ni siquiera funciona exactamente igual que ahora , pero al menos es la idea general).

Answer 2

Creo que la forma en que cambia la carcasa del detector es que recorrerá todas las cajas de arriba a abajo para encontrar coincidencias. Si coincide, se detiene allí.

Por lo tanto, si realizó cambios para priorizar los casos de frecuencia, la respuesta es sí, de alguna manera puede ayudar con el rendimiento. Pero creo que no ayudará mucho.

Answer 3

Tienen el mismo rendimiento para un conjunto relativamente pequeño de valores. Traté de comprobar el código ensamblador del programa C antes, el compilador crea una tabla de salto de todos los valores que tiene en su declaración de cambio.

Pero si los valores de los casos son demasiados, es una apuesta segura que degenerarán en ifelse if, por lo que poner su caso 'E' en la parte superior seguramente aceleraría las cosas.

También es applicable en C#, C# también produce una tabla de salto para instrucciones de cambio con un conjunto pequeño, aunque solo para valores adyacentes. Entonces es O (1), no hay pruebas múltiples, incluso si los primeros valores no coinciden.

Answer 4

Depende de cómo el compilador implementa la instrucción switch.

En primer lugar, no puede permutar arbitrariamente el pedido; si tiene un bloque de casos en un lenguaje tipo C (C, C++, C#, Java, ...), y ese bloque de casos no termina en rotura, no puede reorganizar los casos porque no está el quiebre significa que el compilador debe implementar el fall-through para el siguiente caso. Si ignoramos esta situación especial, puede permutar el resto de los casos.

Si el número de casos es pequeño, el compilador puede implementar las pruebas de caso mediante una secuencia de comparaciones. Si el número de casos es modesto, puede construir un árbol binario equilibrado de los casos. Si el número de casos es grande, la mayoría de los compiladores implementan una bifurcación indexada en el valor del conmutador si es de un conjunto denso. Si partes del conjunto de valores de caso son densas, y las partes son no, el compilador puede dividir las cajas en grupos utilizando un árbol binario para seleccionar qué conjunto denso y un salto indexado dentro del conjunto denso. (De hecho, el compilador puede hacer técnicamente cualquier cosa que pase el control al caso apropiado , pero la mayoría de las veces es una de las anteriores).

Puede ver que el orden puede importar, o no, dependiendo de cómo el compilador implementa el interruptor. Para la mayoría de los buenos compiladores, no importa mucho.