En informática , una tabla de búsqueda ( LUT ) es una matriz que reemplaza el cálculo en tiempo de ejecución con una operación de indexación de matriz más simple, en un proceso denominado direccionamiento directo . Los ahorros en tiempo de procesamiento pueden ser significativos, porque recuperar un valor de la memoria a menudo es más rápido que realizar un cálculo "costoso" o una operación de entrada/salida . [1] Las tablas pueden precalcularse y almacenarse en el almacenamiento estático del programa, calcularse (o "pre-obtenerse" ) como parte de la fase de inicialización de un programa ( memoización ), o incluso almacenarse en hardware en plataformas específicas de la aplicación. Las tablas de búsqueda también se utilizan ampliamente para validar valores de entrada al compararlos con una lista de elementos válidos (o no válidos) en una matriz y, en algunos lenguajes de programación, pueden incluir funciones de puntero (o desplazamientos a etiquetas) para procesar la entrada coincidente. Los FPGA también hacen un uso extensivo de tablas de búsqueda reconfigurables, implementadas en hardware, para proporcionar una funcionalidad de hardware programable. Las LUT se diferencian de las tablas hash en que, para recuperar un valor con clave , una tabla hash almacenaría el valor en la ranura donde es una función hash , es decir, se utiliza para calcular la ranura, mientras que en el caso de LUT, el valor se almacena en la ranura , por lo que es directamente direccionable. [2] : 466
Antes de la llegada de las computadoras, se utilizaban tablas de búsqueda de valores para acelerar los cálculos manuales de funciones complejas, como en trigonometría , logaritmos y funciones de densidad estadística. [3]
En la antigua India (499 d. C.), Aryabhata creó una de las primeras tablas de senos , que codificó en un sistema numérico basado en letras sánscritas. En el año 493 d. C., Victorio de Aquitania escribió una tabla de multiplicar de 98 columnas que daba (en números romanos ) el producto de cada número de 2 a 50 veces y las filas eran "una lista de números que empezaba con mil, descendía de centenas a cien, luego descendía de decenas a diez, luego de unos a uno, y luego las fracciones hasta 1/144" [4]. A los niños de las escuelas modernas a menudo se les enseña a memorizar las " tablas de multiplicar " para evitar los cálculos de los números más utilizados (hasta 9 x 9 o 12 x 12).
En los comienzos de la historia de las computadoras, las operaciones de entrada y salida eran particularmente lentas, incluso en comparación con las velocidades de los procesadores de la época. Tenía sentido reducir las costosas operaciones de lectura mediante una forma de almacenamiento en caché manual mediante la creación de tablas de búsqueda estáticas (integradas en el programa) o matrices precargadas dinámicas para contener solo los elementos de datos que aparecen con más frecuencia. A pesar de la introducción del almacenamiento en caché en todo el sistema que ahora automatiza este proceso, las tablas de búsqueda a nivel de aplicación aún pueden mejorar el rendimiento de los elementos de datos que rara vez cambian, o nunca lo hacen.
Las tablas de consulta fueron una de las primeras funcionalidades implementadas en las hojas de cálculo de computadora , con la versión inicial de VisiCalc (1979) incluyendo una LOOKUPfunción entre sus 20 funciones originales. [5] A esto le siguieron hojas de cálculo posteriores, como Microsoft Excel , y se complementó con funciones especializadas VLOOKUPy HLOOKUPpara simplificar la búsqueda en una tabla vertical u horizontal. En Microsoft Excel, la XLOOKUPfunción se implementó a partir del 28 de agosto de 2019.
Aunque el rendimiento de una LUT está garantizado para una operación de búsqueda, no puede haber dos entidades o valores con la misma clave . Cuando el tamaño del universo (donde se extraen las claves) es grande, puede resultar poco práctico o imposible almacenarlo en la memoria . Por lo tanto, en este caso, una tabla hash sería una alternativa preferible. [2] : 468
Para una búsqueda trivial con una función hash , el valor de datos sin signo se utiliza directamente como índice de una tabla unidimensional para extraer un resultado. Para rangos pequeños, esta puede ser una de las búsquedas más rápidas, incluso superando la velocidad de búsqueda binaria con cero ramificaciones y ejecutándose en tiempo constante . [6]
Un problema discreto que resulta costoso de resolver en muchas computadoras es el de contar la cantidad de bits que se establecen en 1 en un número (binario), a veces llamado función de población . Por ejemplo, el número decimal "37" es "00100101" en binario, por lo que contiene tres bits que se establecen en binario "1". [7] : 282
Un ejemplo simple de código C , diseñado para contar los bits 1 en un int , podría verse así: [7] : 283
int count_ones ( unsigned int x ) { int resultado = 0 ; while ( x != 0 ) { x = x & ( x - 1 ); resultado ++ ; } return resultado ; } La implementación anterior requiere 32 operaciones para evaluar un valor de 32 bits, lo que potencialmente puede llevar varios ciclos de reloj debido a la ramificación . Se puede " desenrollar " en una tabla de búsqueda que, a su vez, utiliza una función hash trivial para un mejor rendimiento. [7] : 282-283
La matriz de bits, bits_set con 256 entradas, se construye dando el número de bits establecidos en cada valor de byte posible (por ejemplo, 0x00 = 0, 0x01 = 1, 0x02 = 1, etc.). Aunque se puede utilizar un algoritmo de tiempo de ejecución para generar la matriz bits_set , es un uso ineficiente de los ciclos de reloj cuando se tiene en cuenta el tamaño, por lo que se utiliza una tabla precalculada, aunque se podría utilizar un script de tiempo de compilación para generar dinámicamente y agregar la tabla al archivo de origen . La suma de unos en cada byte del entero se puede calcular a través de una búsqueda de función hash trivial en cada byte; por lo tanto, se evitan eficazmente las bifurcaciones, lo que resulta en una mejora considerable en el rendimiento. [7] : 284
int count_ones ( int valor_entrada ) { unión cuatro_bytes { int big_int ; char cada_byte [ 4 ]; } operando = valor_entrada ; constante int conjunto_bits [ 256 ] = { 0 , 1 , 1 , 2 , 1 , 2 , 2 , 3 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 5 , 6 , 6 , 7 , 6 , 7 , 7 , 8 }; devolver ( bits_set [ operando . cada_byte [ 0 ]] + bits_set [ operando . cada_byte [ 1 ]] + bits_set [ operando . cada_byte [ 2 ]] + bits_set [ operando . cada_byte [ 3 ]]); }} 
"Las tablas de consulta (LUT) son una técnica excelente para optimizar la evaluación de funciones que son costosas de calcular y económicas de almacenar en caché... Para las solicitudes de datos que se encuentran entre las muestras de la tabla, un algoritmo de interpolación puede generar aproximaciones razonables promediando las muestras cercanas". [8]
En aplicaciones de análisis de datos, como el procesamiento de imágenes , se puede utilizar una tabla de consulta (LUT) para transformar los datos de entrada en un formato de salida más adecuado. Por ejemplo, una imagen en escala de grises del planeta Saturno se podría transformar en una imagen en color para enfatizar las diferencias en sus anillos.
En el procesamiento de imágenes, las tablas de búsqueda se denominan a menudo LUT (o 3DLUT) y proporcionan un valor de salida para cada uno de los valores de un rango de índices. Una LUT común, llamada mapa de colores o paleta , se utiliza para determinar los colores y los valores de intensidad con los que se mostrará una imagen en particular. En tomografía computarizada , "ventanas" se refiere a un concepto relacionado para determinar cómo mostrar la intensidad de la radiación medida.
Un ejemplo clásico de reducción de los cálculos en tiempo de ejecución mediante tablas de búsqueda es obtener el resultado de un cálculo trigonométrico , como el seno de un valor. [9] El cálculo de funciones trigonométricas puede ralentizar sustancialmente una aplicación informática. La misma aplicación puede terminar mucho antes si primero precalcula el seno de una serie de valores, por ejemplo para cada número entero de grados (la tabla se puede definir como variables estáticas en tiempo de compilación, lo que reduce los costos de tiempo de ejecución repetido). Cuando el programa requiere el seno de un valor, puede utilizar la tabla de búsqueda para recuperar el valor de seno más cercano de una dirección de memoria, y también puede interpolar al seno del valor deseado, en lugar de calcular mediante una fórmula matemática. Por lo tanto, las tablas de búsqueda pueden ser utilizadas por coprocesadores matemáticos en sistemas informáticos. Un error en una tabla de búsqueda fue responsable del infame error de división de punto flotante de Intel .
Las funciones de una sola variable (como seno y coseno) pueden implementarse mediante una matriz simple. Las funciones que involucran dos o más variables requieren técnicas de indexación de matrices multidimensionales. El último caso puede emplear una matriz bidimensional de potencia[x][y] para reemplazar una función para calcular x e y para un rango limitado de valores x e y. Las funciones que tienen más de un resultado pueden implementarse con tablas de búsqueda que son matrices de estructuras.
Como se mencionó, existen soluciones intermedias que utilizan tablas en combinación con una pequeña cantidad de cálculo, a menudo mediante interpolación . El cálculo previo combinado con la interpolación puede producir una mayor precisión para los valores que se encuentran entre dos valores precalculados. Esta técnica requiere un poco más de tiempo para realizarse, pero puede mejorar en gran medida la precisión en las aplicaciones que la requieren. Según los valores que se precalculen, el cálculo previo con interpolación también se puede utilizar para reducir el tamaño de la tabla de búsqueda manteniendo la precisión.
Aunque a menudo es eficaz, el uso de una tabla de búsqueda puede, no obstante, dar lugar a una penalización grave si el cálculo que reemplaza la LUT es relativamente simple. El tiempo de recuperación de la memoria y la complejidad de los requisitos de memoria pueden aumentar el tiempo de operación de la aplicación y la complejidad del sistema en relación con lo que se requeriría con un cálculo de fórmula simple. La posibilidad de contaminar la memoria caché también puede convertirse en un problema. Los accesos a tablas grandes casi con certeza provocarán una falla de caché . Este fenómeno se está convirtiendo cada vez más en un problema a medida que los procesadores superan la memoria. Un problema similar aparece en la rematerialización , una optimización del compilador . En algunos entornos, como el lenguaje de programación Java , las búsquedas de tablas pueden ser incluso más costosas debido a la comprobación obligatoria de límites que implica una comparación y una bifurcación adicionales para cada búsqueda.
Existen dos limitaciones fundamentales en cuanto a cuándo es posible construir una tabla de búsqueda para una operación requerida. Una es la cantidad de memoria disponible: no se puede construir una tabla de búsqueda más grande que el espacio disponible para la tabla, aunque es posible construir tablas de búsqueda basadas en disco a expensas del tiempo de búsqueda. La otra es el tiempo requerido para calcular los valores de la tabla en primera instancia; aunque esto generalmente debe hacerse solo una vez, si lleva un tiempo prohibitivamente largo, puede hacer que el uso de una tabla de búsqueda sea una solución inadecuada. Sin embargo, como se dijo anteriormente, las tablas se pueden definir estáticamente en muchos casos.
La mayoría de las computadoras sólo realizan operaciones aritméticas básicas y no pueden calcular directamente el seno de un valor dado. En su lugar, utilizan el algoritmo CORDIC o una fórmula compleja como la siguiente serie de Taylor para calcular el valor del seno con un alto grado de precisión: [10] : 5
Sin embargo, esto puede ser costoso de calcular, especialmente en procesadores lentos, y hay muchas aplicaciones, particularmente en gráficos de computadora tradicionales , que necesitan calcular muchos miles de valores de seno cada segundo. Una solución común es calcular inicialmente el seno de muchos valores distribuidos uniformemente y luego, para encontrar el seno de x, elegimos el seno del valor más cercano a x a través de la operación de indexación de matrices. Esto estará cerca del valor correcto porque el seno es una función continua con una tasa de cambio acotada. [10] : 6 Por ejemplo: [11] : 545–548
matriz real seno_tabla [ - 1000 .. 1000 ] para x desde - 1000 hasta 1000 seno_tabla [ x ] = seno ( pi * x / 1000 ) función lookup_sine ( x ) devuelve seno_tabla [ round ( 1000 * x / pi )] 
Lamentablemente, la tabla requiere bastante espacio: si se utilizan números de punto flotante de doble precisión IEEE, se necesitarían más de 16.000 bytes. Podemos utilizar menos muestras, pero entonces nuestra precisión empeorará significativamente. Una buena solución es la interpolación lineal , que dibuja una línea entre los dos puntos de la tabla a cada lado del valor y ubica la respuesta en esa línea. Esto sigue siendo rápido de calcular y mucho más preciso para funciones suaves como la función seno. Aquí hay un ejemplo que utiliza la interpolación lineal:
función búsqueda_seno ( x ) x1 = piso ( x * 1000 / pi ) y1 = tabla_seno [ x1 ] y2 = tabla_seno [ x1 + 1 ] devolver y1 + ( y2 - y1 ) * ( x * 1000 / pi - x1 ) La interpolación lineal permite obtener una función interpolada que es continua, pero que, en general, no tiene derivadas continuas . Para lograr una interpolación más fluida de una consulta en una tabla que sea continua y tenga una primera derivada continua , se debe utilizar la spline cúbica de Hermite .
Al utilizar la interpolación, el tamaño de la tabla de búsqueda se puede reducir mediante el uso de un muestreo no uniforme , lo que significa que cuando la función es casi recta, utilizamos pocos puntos de muestra, mientras que cuando cambia de valor rápidamente, utilizamos más puntos de muestra para mantener la aproximación cerca de la curva real. Para obtener más información, consulte interpolación .
Los cachés de almacenamiento (incluidos los cachés de disco para archivos o los cachés de procesador para código o datos) también funcionan como una tabla de búsqueda. La tabla se construye con una memoria muy rápida en lugar de almacenarse en una memoria externa más lenta, y mantiene dos datos para un subrango de bits que componen una dirección de memoria externa (o disco) (en particular, los bits más bajos de cualquier dirección externa posible):
Se realiza una única búsqueda (rápida) para leer la etiqueta en la tabla de búsqueda en el índice especificado por los bits más bajos de la dirección de almacenamiento externo deseada y para determinar si la memoria caché coincide con la dirección de memoria. Cuando se encuentra un resultado, no se necesita acceder a la memoria externa (excepto para las operaciones de escritura, donde el valor almacenado en caché puede necesitar actualizarse de forma asincrónica a la memoria más lenta después de un tiempo, o si la posición en la memoria caché debe reemplazarse para almacenar en caché otra dirección).
En lógica digital , una tabla de búsqueda se puede implementar con un multiplexor cuyas líneas de selección son controladas por la señal de dirección y cuyas entradas son los valores de los elementos contenidos en la matriz. Estos valores pueden estar cableados, como en un ASIC cuyo propósito es específico para una función, o pueden proporcionarse mediante pestillos D que permiten valores configurables. ( ROM , EPROM , EEPROM o RAM ).
Una LUT de n bits puede codificar cualquier función booleana de n entradas almacenando la tabla de verdad de la función en la LUT. Esta es una forma eficiente de codificar funciones lógicas booleanas , y las LUT con 4-6 bits de entrada son, de hecho, el componente clave de las matrices de puertas programables en campo (FPGA) modernas que brindan capacidades lógicas de hardware reconfigurables.
En los sistemas de adquisición y control de datos , las tablas de búsqueda se utilizan comúnmente para realizar las siguientes operaciones en:
En algunos sistemas, también se pueden definir polinomios en lugar de tablas de búsqueda para estos cálculos.
{{cite web}}: CS1 maint: unfit URL (link){{cite web}}: CS1 maint: multiple names: authors list (link)