strtok() c++

Lo que es más eficiente una caja de conmutación o un estándar:: mapa

Question

Estoy pensando en el tokenizer aquí.
Cada token llama a una función diferente dentro del analizador.
¿Qué es más eficiente?

• Un mapa de std :: functions / boost :: funciones
• Una caja de interruptor

Answer 1

¿Cuál es su definición de "eficiente"? Si quiere decir más rápido, entonces probablemente deba perfilar algún código de prueba para obtener una respuesta definitiva. Sin embargo, si busca código flexible y fácil de ampliar, hágase un favor y use el enfoque de mapa. Todo lo demás es solo una optimización prematura ...

Answer 2

Como dijo Yossi1981, un switch podría optimizarse para ser una tabla de búsqueda rápida, pero no hay garantía, cada compilador tiene otros algoritmos para determinar si implementar el switch como ifs consecutivos o como tabla de búsqueda rápida, o tal vez una combinación de ambos.

Para obtener un cambio rápido, sus valores deben cumplir con la siguiente regla: deben ser consecutivos, es decir, por ejemplo, 0,1,2,3,4. Puede dejar algunos valores pero es muy poco probable que se optimicen cosas como 0,1,2,34,43.

La pregunta realmente es: ¿es el rendimiento de tal importancia en su aplicación? ¿Y un mapa que cargue sus valores dinámicamente desde un archivo no sería más legible y mantenible en lugar de un enunciado enorme que abarque varias páginas de código?

Answer 3

El estándar de C ++ no dice nada sobre el rendimiento de sus requisitos, solo que la funcionalidad debe estar allí.

Este tipo de preguntas sobre cuál es mejor o más rápido o más eficiente no tiene sentido a menos que indique la implementación de la que está hablando. Por ejemplo, el manejo de cadenas en una cierta versión de una determinada implementación de JavaScript era atroz, pero no se puede extrapolar a eso como una característica del estándar relevante.

Incluso llegaría a decir que no importa, independientemente de la implementación, ya que la funcionalidad proporcionada por switch y std::map es diferente (aunque hay superposición).

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

Answer 4

No dices qué tipo son tus tokens. Si no son enteros, no tiene opción: los cambios solo funcionan con tipos enteros.

Answer 5

STL Map que viene con visual studio 2008 le dará O (log (n)) para cada llamada de función ya que oculta una estructura de árbol debajo. Con el compilador moderno (dependiendo de la implementación), una instrucción switch le dará O (1), el compilador lo traduce a algún tipo de tabla de búsqueda. Entonces, en general, el cambio es más rápido.

Sin embargo , considere los siguientes hechos:

La diferencia entre el mapa y el interruptor es que: el mapa se puede construir dinámicamente mientras que el interruptor no. El mapa puede contener cualquier tipo arbitrario como clave, mientras que el cambio está muy limitado a los tipos primitivos de c ++ (char, int, enum, etc.).

Por cierto, puede usar un mapa hash para lograr casi O (1) despacho (aunque, dependiendo de la implementación de la tabla hash, a veces puede ser O (n) en el peor de los casos). Aunque, el cambio seguirá siendo más rápido.

Editar

Escribo lo siguiente solo por diversión y por el tema de la discusión

Puedo sugerirle una buena optimización, pero depende de la naturaleza de su idioma y de si puede esperar el uso de su idioma.

Cuando escribe el código: divide sus tokens en dos grupos, un grupo será de muy alta frecuencia y el otro de baja frecuencia. También ordena los tokens usados ​​frecuentemente. Para los tokens con mayor frecuencia, usted escribe una serie if-else con el más alto usado frecuentemente en primer lugar. para el bajo usado frecuentemente, escribe una declaración de cambio.

La idea es utilizar la predicción de bifurcación de CPU para evitar incluso otro nivel de indirección (suponiendo que la comprobación de condición en la instrucción if sea prácticamente gratuita). en la mayoría de los casos, la CPU elegirá la rama correcta sin ningún nivel de indirección. Sin embargo, serán pocos los casos en que la sucursal irá al lugar equivocado. Dependiendo de la naturaleza de su idioma, estadísticamente puede proporcionar un mejor rendimiento.

Editar : debido a algunos comentarios a continuación, se modificó la oración diciendo que los compiladores siempre traducirán un cambio a LUT.

Answer 6

Sugeriría leer interruptor () vs. tabla de búsqueda? de Joel en Software. Particularmente, esta respuesta es interesante:

"Primer ejemplo de personas perdiendo el tiempo tratando de optimizar lo menos significativo".

Si y no. En una máquina virtual, normalmente llama a pequeñas funciones que hacen muy poco. No es la llamada / devolución lo que le duele tanto como el preámbulo y la rutina de limpieza para cada función, a menudo representando un porcentaje significativo del tiempo de ejecución. Esto ha sido investigado hasta la muerte, especialmente por personas que han implementado intérpretes enhebrados.

En las máquinas virtuales, las tablas de búsqueda que almacenan direcciones computadas para llamar son generalmente preferidas a los conmutadores. (el enhebrado directo, o "etiquetar como valores" llama directamente a la dirección de etiqueta almacenada en la tabla de búsqueda) Esto es porque permite, en ciertas condiciones, reducir errores de predicción de ramificaciones , que es extremadamente costoso en CPUs de largo recorrido (obliga a enjuagar la tubería). Sin embargo, hace que el código sea menos portátil.

Este tema se ha debatido ampliamente en la comunidad de VM, le sugiero que busque documentos académicos en este campo si desea leer más al respecto. Ertl y Gregg escribieron un excelente artículo sobre este tema en 2001, The Behavior of Efficient Virtual Machine Interpreters on Modern Architectures.

Pero como se mencionó, estoy bastante seguro de que estos detalles no son relevantes para su código. Estos son pequeños detalles, y no deberías concentrarte demasiado en eso. El intérprete de Python está utilizando switches, porque creen que hace que el código sea más legible. ¿Por qué no escoges el uso con el que te sientes más cómodo? El impacto en el rendimiento será más bien pequeño; será mejor que se centre en la legibilidad del código por ahora;)

Editar : si es importante, usar una tabla hash siempre será más lento que una tabla de búsqueda. Para una tabla de búsqueda, usa tipos enum para sus "claves", y el valor se recupera usando un solo salto indirecto. Esta es una operación de ensamblaje único. O (1). Una búsqueda de tablas hash primero requiere calcular un hash, luego recuperar el valor, que es mucho más caro.

Usar una matriz donde se almacenan las direcciones de las funciones y acceder a ellas utilizando los valores de una enumeración es bueno. Pero usar una tabla hash para hacer lo mismo agrega una sobrecarga importante

En resumen, tenemos:

• costo (Hash_table) >> costo (direct_lookup_table)
• costo (direct_lookup_table) ~ = costo (cambio) si su compilador traduce interruptores en tablas de búsqueda.
• cost (switch) >> cost (direct_lookup_table) (O (N) vs O (1)) si su compilador no traduce los switches y usa los condicionales, pero no puedo pensar en ningún compilador que lo haga.
• Pero el enhebrado directo integrado hace que el código sea menos legible.