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 matrices más simple, en un proceso denominado direccionamiento directo . El ahorro en tiempo de procesamiento puede ser significativo, porque recuperar un valor de la memoria suele ser más rápido que realizar un cálculo "costoso" o una operación de entrada/salida . [1] Las tablas pueden calcularse previamente y almacenarse en un almacenamiento de programa estático , calcularse (o "captarse previamente" ) como parte de la fase de inicialización de un programa ( memorizació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 comparándolos 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 de etiquetas) para procesar la entrada coincidente. Los FPGA también hacen un uso extensivo de tablas de búsqueda reconfigurables implementadas por hardware para proporcionar 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 hay una función hash , es decir , se utiliza para calcular la ranura, mientras que en el caso de las LUT, el valor es almacenado en la ranura , por lo que es directamente direccionable. [2] : 466
Antes de la llegada de las computadoras, se usaban tablas de búsqueda de valores para acelerar los cálculos manuales de funciones complejas, como en trigonometría , logaritmos y funciones estadísticas de densidad. [3]
En la India antigua (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 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 comenzaba con mil y descendía de centenas a uno". cien, luego descendiendo de decenas a diez, luego de unidades 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 " tablas de multiplicar " para evitar cálculos de los números más utilizados ( hasta 9 x 9 o 12 x 12).
Al principio 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 dinámicas precargadas para contener solo los elementos de datos que ocurren con mayor 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 elementos de datos que rara vez cambian, o nunca.
Las tablas de búsqueda fueron una de las primeras funcionalidades implementadas en las hojas de cálculo de las computadoras , y la versión inicial de VisiCalc (1979) incluyó 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 pueden haber dos entidades o valores con la misma clave . Cuando el tamaño del universo —donde se dibujan 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 de función hash trivial , el valor de datos sin firmar sin firmar 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 ramas y ejecutándose en tiempo constante . [6]
Un problema discreto que es costoso de resolver en muchas computadoras es el de contar el número de bits que están establecidos 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 configurados en "1" binario. [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 ; mientras ( x ! = 0 ) { x = x & ( x - 1 ); resultado ++ ; } devolver resultado ; } La implementación anterior requiere 32 operaciones para evaluar un valor de 32 bits, lo que potencialmente puede tomar varios ciclos de reloj debido a la bifurcació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 un bit establecido en cada valor de byte posible (por ejemplo, 0x00 = 0, 0x01 = 1, 0x02 = 1, etc.). Aunque se puede usar 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 usa una tabla precalculada, aunque se podría usar un script en tiempo de compilación para generar y agregar dinámicamente la tabla. al archivo fuente . La suma de unos en cada byte del número entero se puede calcular mediante una búsqueda trivial de una función hash en cada byte; por lo tanto, se evitan bifurcaciones de manera efectiva, lo que resulta en una mejora considerable en el rendimiento. [7] : 284
int count_ones ( int input_value ) { unión cuatro_bytes { int big_int ; char cada_byte [ 4 ]; } operando = valor_entrada ; const int bits_set [ 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 }; return ( bits_set [ operando . each_byte [ 0 ]] + bits_set [ operando . each_byte [ 1 ]] + bits_set [ operando . each_byte [ 2 ]] + bits_set [ operando . each_byte [ 3 ]]); }} 
"Las tablas de búsqueda (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 solicitudes de datos que se encuentran entre las muestras de la tabla, un algoritmo de interpolación puede generar aproximaciones razonables promediando muestras cercanas ". [8]
En aplicaciones de análisis de datos, como el procesamiento de imágenes , se utiliza una tabla de búsqueda (LUT) para transformar los datos de entrada en un formato de salida más deseable. Por ejemplo, una imagen en escala de grises del planeta Saturno se transformará en una imagen en color para resaltar las diferencias en sus anillos.
En el procesamiento de imágenes, las tablas de búsqueda a menudo se denominan LUT (o 3DLUT) y brindan un valor de salida para cada uno de un rango de valores de índice. Un LUT común, llamado 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 , "ventana" 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 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. Calcular funciones trigonométricas puede ralentizar sustancialmente una aplicación informática. La misma aplicación puede finalizar mucho antes cuando precalcula por primera vez el seno de una cantidad de valores, por ejemplo, para cada número entero de grados (la tabla se puede definir como variables estáticas en el momento de la compilación, lo que reduce los costos de tiempo de ejecución repetidos). Cuando el programa requiere el seno de un valor, puede usar la tabla de búsqueda para recuperar el valor del 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 tanto, los coprocesadores matemáticos en los sistemas informáticos utilizan tablas de búsqueda . 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 el seno y el coseno) se pueden implementar mediante una matriz simple. Las funciones que involucran dos o más variables requieren técnicas de indexación de matrices multidimensionales. Por lo tanto, el último caso puede emplear una matriz bidimensional de potencia [x][y] para reemplazar una función para calcular xy para un rango limitado de valores de xey. Las funciones que tienen más de un resultado se pueden implementar con tablas de búsqueda que son matrices de estructuras.
Como se mencionó, existen soluciones intermedias que usan tablas en combinación con una pequeña cantidad de cálculo, a menudo usando 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 calculados previamente. Esta técnica requiere un poco más de tiempo para realizarse, pero puede mejorar en gran medida la precisión en aplicaciones que la requieran. Dependiendo de los valores que se calculan previamente, 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.
Si bien suele ser eficaz, emplear una tabla de búsqueda puede resultar en una penalización severa 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 mediante el cálculo de fórmulas simples. La posibilidad de contaminar el caché también puede convertirse en un problema. Es casi seguro que los accesos a tablas grandes provocarán una pérdida de caché . Este fenómeno se está convirtiendo cada vez más en un problema a medida que los procesadores superan a 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 verificación de límites obligatoria que implica una comparación y una rama adicionales para cada búsqueda.
Existen dos limitaciones fundamentales sobre cuándo es posible construir una tabla de búsqueda para una operación requerida. Uno 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. El otro es el tiempo necesario para calcular los valores de la tabla en primera instancia; aunque normalmente esto sólo debe hacerse una vez, si lleva un tiempo prohibitivo, puede hacer que el uso de una tabla de búsqueda sea una solución inapropiada. Sin embargo, como se indicó anteriormente, las tablas se pueden definir estáticamente en muchos casos.
La mayoría de las computadoras solo realizan operaciones aritméticas básicas y no pueden calcular directamente el seno de un valor determinado. 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: [9] : 5
Sin embargo, esto puede resultar costoso de calcular, especialmente en procesadores lentos, y hay muchas aplicaciones, particularmente en gráficos por computadora tradicionales , que necesitan calcular muchos miles de valores sinusoidales por 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 mediante 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. [9] : 6 Por ejemplo: [10] : 545–548
matriz real sine_table [ - 1000 .. 1000 ] para x de - 1000 a 1000 sine_table [ x ] = seno ( pi * x / 1000 ) función lookup_sine ( x ) return sine_table [ ronda ( 1000 * x / pi )] 
Desafortunadamente, 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 usar menos muestras, pero entonces nuestra precisión empeorará significativamente. Una buena solución es la interpolación lineal , que traza 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 fluidas como la función seno. A continuación se muestra un ejemplo que utiliza la interpolación lineal:
función lookup_sine ( x ) x1 = piso ( x * 1000 / pi ) y1 = sine_table [ x1 ] y2 = sine_table [ x1 + 1 ] return y1 + ( y2 - y1 ) * ( x * 1000 / pi - x1 ) La interpolación lineal proporciona una función interpolada que es continua, pero que, en general, no tendrá derivadas continuas . Para una interpolación más suave de la búsqueda en una tabla que sea continua y tenga una primera derivada continua , se debe utilizar la spline cúbica de Hermite .
Cuando se usa la interpolación, el tamaño de la tabla de búsqueda se puede reducir usando un muestreo no uniforme , lo que significa que cuando la función es casi recta, usamos pocos puntos de muestra, mientras que cuando cambia el valor rápidamente usamos más puntos de muestra para mantener la aproximación. cerca de la curva real. Para obtener más información, consulte interpolación .
Las cachés de almacenamiento (incluidas las cachés de disco para archivos o las cachés de procesador para código o datos) también funcionan como una tabla de búsqueda. La tabla está construida 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 (o disco) externa (en particular, los bits más bajos de cualquier dirección externa posible). :
Se realiza una búsqueda única (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 dirección de memoria es alcanzada por el caché. Cuando se encuentra un resultado, no se necesita acceso a la memoria externa (excepto para operaciones de escritura, donde es posible que el valor almacenado en caché deba actualizarse de forma asincrónica a la memoria más lenta después de un tiempo, o si la posición en el caché debe reemplazarse para almacenar en caché otro DIRECCIÓN).
En lógica digital , se puede implementar una tabla de búsqueda 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 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 los LUT con 4 a 6 bits de entrada son, de hecho, el componente clave de los modernos conjuntos de puertas programables en campo (FPGA, por sus siglas en inglés) que proporcionan capacidades lógicas de hardware reconfigurables.
En los sistemas de control y adquisición 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 consulta para estos cálculos.
{{cite web}}: Mantenimiento CS1: URL no apta ( enlace )