La bifurcación de múltiples vías es el cambio al flujo de control de un programa basado en un valor que coincide con un criterio seleccionado. Es una forma de declaración condicional . Una bifurcación de múltiples vías es a menudo el método más eficiente para pasar el control a uno de un conjunto de etiquetas de programa , especialmente si se ha creado un índice de antemano a partir de los datos sin procesar .
Ejemplos de
- Mesa de sucursales
- Declaración de cambio : consulte también las alternativas a continuación
- Despacho múltiple : donde se invoca una subrutina y se realiza una devolución
Alternativas
Una rama de múltiples vías puede, con frecuencia, ser reemplazada con una búsqueda de tabla indexada eficiente (usando el valor de los datos en sí o una derivada calculada del valor de los datos, como el índice de una matriz ) [1]
" ... la implementación de una instrucción de cambio se ha equiparado con la de una rama de múltiples vías. Sin embargo, para muchos usos de la instrucción de cambio en código real, es posible evitar la ramificación por completo y reemplazar el cambio con una o más tablas de apariencia -ups. Por ejemplo, el
Has30Days
ejemplo [presentado anteriormente] se puede implementar de la siguiente manera: [C ejemplo] "
"Un análisis superoptimizador de la generación de código de rama de múltiples vías" por Roger Anthony Sayle
switch ( x ) { / * x es el mes no * / caso 4 : / * abril * / caso 6 : / * junio * / caso 9 : / * septiembre * / caso 11 : / * noviembre * / return true ; }
se puede reemplazar, utilizando una técnica de "hash seguro", con:
unsigned int t = x | 2 ; switch ( t ) { caso 6 : caso 11 : devuelve verdadero ; }
o se puede reemplazar, usando una búsqueda de tabla de mapeo de índice , con -
x % = 12 ; / * para asegurarse de que x esté en el rango 0-11 * / static const int T [ 12 ] = { 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 1 }; / * Tabla basada en 0 'si 30 días = 1, en caso contrario 0' * / return T [ x ]; / * retorna con booleano 1 = verdadero, 0 = falso * /
(En vista de la simplicidad del último caso, sería preferible implementarlo en línea, ya que la sobrecarga de usar una llamada de función puede ser mayor que la búsqueda indexada en sí).
Citas
La ramificación de múltiples vías es una técnica de programación importante que con demasiada frecuencia se reemplaza por una secuencia ineficiente de pruebas if. Peter Naur me escribió recientemente que considera el uso de tablas para controlar el flujo de programas como una idea básica de la informática que ha sido casi olvidada; pero espera que esté listo para redescubrirlo en cualquier momento. Es la clave de la eficiencia en todos los mejores compiladores que he estudiado.
- Donald Knuth , Programación estructurada con ir a Declaraciones
Ver también
Referencias
- ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 27 de febrero de 2012 . Consultado el 18 de noviembre de 2009 .CS1 maint: copia archivada como título ( enlace )
enlaces externos
- Codificación de ramas de múltiples vías utilizando funciones hash personalizadas de HG Dietz
- Aprendiendo Python por Mark Lutz
- Programación en C ++ Por Nell B. Dale, Chip Weems
- Un análisis superoptimizador de la generación de código de rama de múltiples vías por Roger Anthony Sayle