Lo que es más eficiente un caso interruptor o un std :: mapa

Question

Estoy pensando en la tokenizer aquí.
Cada ficha llama a una función diferente dentro del analizador.
Lo que es más eficiente:

• Un mapa de std :: Funciones / boost :: funciones
• Un caso interruptor

Answer 1

STL mapa que viene con Visual Studio 2008 le dará O (log (n)) para cada llamada a la función ya que se esconde debajo de una estructura de árbol. Con compilador moderna (dependiendo de la aplicación), una sentencia switch le dará O (1), el compilador traduce a una especie de tabla de consulta. Así que, en general, el interruptor es más rápido.

Sin embargo , tenga en cuenta los siguientes hechos:

La diferencia entre el mapa y el interruptor es que: Mapa se puede construir dinámicamente mientras el interruptor no puede. Mapa puede contener cualquier tipo arbitrario como una tecla mientras el interruptor está muy limitada a C ++ tipos primitivos (char, int, enumeración, etc ...).

Por cierto, se puede utilizar un mapa hash para alcanzar casi el O (1) enviar (aunque, dependiendo de la aplicación tabla hash, a veces puede ser O (n) en el peor caso). A pesar de que, el interruptor todavía será más rápido.

Editar

Les escribo lo siguiente solamente por diversión y para el asunto de la discusión

puedo sugerir una optimización agradable para usted, pero depende de la naturaleza de su idioma y si se puede esperar cómo se utilizará su idioma.

Cuando se escribe el código: Se divide sus fichas en dos grupos, un grupo será de muy alta frecuencia utilizada y el otro de baja frecuencia utilizada. También ordenar las altas fichas de uso frecuente. Para la alta frecuencia fichas se escribe un serie if-else con la más alta utilizada con frecuencia viene primero. por el bajo utilizado con frecuencia, se escribe una sentencia switch.

La idea es utilizar la predicción de ramificación CPU con el fin de evitar incluso otro nivel de indirección (suponiendo que la condición de verificación en la sentencia if es casi sin costo). en la mayoría de los casos la CPU escogerá la rama correcta sin ningún nivel de indirección. Serán pocos los casos sin embargo, que la rama irá al lugar equivocado. Dependiendo de la naturaleza de su languege, Statisticly puede dar un mejor rendimiento.

Editar . Debido a algunos comentarios a continuación, cambiaron la frase diciendo que los compiladores Allways traducir un interruptor para LUT

Answer 2

Yo sugeriría lectura () vs búsqueda en la tabla? de Joel on Software. En particular, esta respuesta es interesante:

  

" El primer ejemplo de las personas que pierden el tiempo   se trata de optimizar la menor   Lo significativo ".

     

Sí y no. En una máquina virtual, por lo general   llamar pequeñas funciones que cada uno haga muy   pequeño. Es el no la llamada / retorno   que duele tanto como el preámbulo   y la rutina de limpieza para cada función   siendo a menudo un porcentaje significativo   del tiempo de ejecución. Esto ha sido   investigado hasta la muerte, especialmente por   gente que ha implementado roscado   intérpretes.

En las máquinas virtuales, tablas de búsqueda almacenar direcciones calcula que llamar por lo general se prefieren a los interruptores. (Threading directa, o "etiqueta como valores". Llamadas directamente la dirección de etiqueta almacenada en la tabla de búsqueda) Eso es debido a que permite, bajo ciertas condiciones, para reducir predicción errónea rama , que es extremadamente caro en las CPU de larga pipeline (que obliga a limpiar la tubería). Es, sin embargo, hace que el código sea menos portátil.

Esta cuestión se ha debatido ampliamente en la comunidad VM, sugeriría usted para buscar documentos eruditos en este campo si desea leer más sobre él. Ertl y Gregg escribió un gran artículo sobre este tema en 2001, El comportamiento de eficiente Máquinas virtuales Intérpretes en arquitecturas modernas

Sin embargo, como se mencionó, estoy bastante seguro de que estos detalles no son relevantes para su código. Son pequeños detalles, y usted no debe centrarse demasiado en ella. intérprete de Python es el uso de interruptores, ya que creo que hace que el código sea más legible. ¿Por qué no coges el uso que usted es el más cómodo? Impacto en el rendimiento será más bien pequeña, es mejor que se centra en la legibilidad del código por ahora;)

Editar : si importa, utilizando una tabla hash siempre más lenta que una tabla de búsqueda. Para una tabla de búsqueda, utiliza tipos de enumeración para sus "claves", y el valor se recupera mediante un solo salto indirecta. Esta es una única operación de montaje. O (1). Una búsqueda en la tabla de hash requiere en primer lugar de calcular un hash, a continuación, para recuperar el valor, que es mucho más caro.

Uso de una matriz en donde se almacenan las direcciones de función, y se accede mediante los valores de una enumeración es bueno. Pero el uso de una tabla hash para hacer lo mismo añade una sobrecarga importante

En resumen, tenemos:

• Coste (tabla_hash) >> coste (direct_lookup_table)
• Coste (direct_lookup_table) ~ = costo (interruptor) si su compilador traduce interruptores en las tablas de búsqueda.
• Coste (interruptor) >> coste (direct_lookup_table) (O (N) vs O (1)) si el compilador no se traduce interruptores y utilizar los condicionales, pero no puedo pensar en cualquier compilador de hacer esto.
• Pero rosca directa inline hace que el código sea menos legible.

Answer 3

¿Cuál es su definición de "eficiente"? Si se refiere más rápido, entonces probablemente debería perfilar un cierto código de prueba para una respuesta definitiva. Si estás después de código flexible y fácil de extender, sin embargo, a continuación, hágase un favor y utilizar el método de la hoja. Todo lo demás es simplemente la optimización prematura ...

Answer 4

Al igual que yossi1981 Dicho esto, un interruptor puede ser optimizado de beeing una tabla de consulta rápida, pero no se garantiza, cada compilador tiene otros algoritmos para determinar si se debe implementar el conmutador como reincidente, si de o tabla de búsqueda tan rápido, o tal vez una combinación de ambos.

Para obtener una rápida cambiar sus valores deben cumplir con la siguiente regla: que deben ser consecutivos, es decir, por ejemplo, 0,1,2,3,4. Puede dejar algunos valores fuera, pero cosas como 0,1,2,34,43 es extremadamente improbable que ser optimizado.

La pregunta realmente es: es el rendimiento de tal importancia en su aplicación? Y no sería un mapa que carga sus valores de forma dinámica a partir de un archivo sea más legible y fácil de mantener en lugar de una declaración enorme, que abarca varias páginas de código?

Answer 5

Usted no dice qué tipo son sus fichas. Si no son números enteros, usted no tiene una opción - interruptores sólo se trabaja con tipos enteros.

Answer 6

El estándar de C ++ no dice nada sobre el cumplimiento de sus requisitos, sólo que la funcionalidad debería estar allí.

Este tipo de preguntas sobre lo que es mejor o más rápido o más eficiente no tienen sentido si usted afirma que aplicación que está hablando. Por ejemplo, el manejo de una determinada versión de una determinada implementación de JavaScript cadena fue atroz, pero no se puede extrapolar que al ser una característica de la norma en cuestión.

Incluso iría tan lejos como para decir que no importa, independientemente de la aplicación, desde la funcionalidad proporcionada por switch y std::map es diferente (aunque no hay solapamiento).

Este tipo de micro-optimizaciones son casi nunca es necesario, en mi opinión.