El mapeo de índices (o direccionamiento directo , o una función hash trivial ) en informática describe el uso de una matriz , en la que cada posición corresponde a una clave en el universo de valores posibles. [1] La técnica es más eficaz cuando el universo de claves es razonablemente pequeño, de modo que la asignación de una matriz con una posición para cada clave posible es asequible. Su eficacia proviene del hecho de que una posición arbitraria en una matriz se puede examinar en un tiempo constante .
Matrices aplicables
Hay muchos ejemplos prácticos de datos cuyos valores válidos están restringidos dentro de un rango pequeño. Una función hash trivial es una opción adecuada cuando dichos datos deben actuar como una clave de búsqueda. Algunos ejemplos incluyen:
- mes del año (1–12)
- día del mes (1–31)
- día de la semana (1-7)
- edad humana (0-130) - por ejemplo, tablas de actuario de cobertura vital, hipoteca a plazo fijo
- Caracteres ASCII (0-127), que incluyen símbolos de operadores matemáticos comunes, dígitos, signos de puntuación y el alfabeto del idioma inglés.
Ejemplos de
El uso de una función hash trivial, en una búsqueda de tabla no iterativa, puede eliminar las pruebas condicionales y la ramificación por completo, reduciendo la longitud de la ruta de instrucción de un programa de computadora.
Evite las ramificaciones
Roger Sayle da un ejemplo [2] de eliminación de una rama de múltiples vías causada por una declaración de cambio :
inline bool HasOnly30Days ( int m ) { switch ( m ) { caso 4 : // caso 6 de abril : // caso 9 de junio : // caso 11 de septiembre : // retorno de noviembre verdadero ; predeterminado : devuelve falso ; } }
Que se puede reemplazar con una búsqueda de tabla:
inline bool HasOnly30Days ( int m ) { static const bool T [] = { 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 0 }; devuelve T [ m -1 ]; }
Ver también
Referencias
- ^ Cormen, Thomas H. (2009). Introducción a los algoritmos (3ª ed.). Cambridge, Mass .: MIT Press. págs. 253-255. ISBN 9780262033848. Consultado el 26 de noviembre de 2015 .
- ^ Sayle, Roger Anthony (17 de junio de 2008). "Un análisis de superptimizador de generación de código de rama de múltiples vías" (PDF) . Actas de la Cumbre de Desarrolladores del GCC : 103-116 . Consultado el 26 de noviembre de 2015 .