Hispanopedia Wiki
Articulo de referencia

Tabla de búsqueda

En informática , una tabla de búsqueda ( LUT ) es una matriz que reemplaza el cálculo en tiempo de ejecución de una función matemática con una operación de indexación de matriz ...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , una tabla de búsqueda ( LUT ) es una matriz que reemplaza el cálculo en tiempo de ejecución de una función matemática con una operación de indexación de matriz más simple, en un proceso denominado direccionamiento directo . El ahorro en el tiempo de procesamiento puede ser significativo, porque recuperar un valor de la memoria suele ser más rápido que realizar un cálculo o una operación de entrada/salida "costosa" . [ 1 ] Las tablas pueden precalcularse y almacenarse en el almacenamiento estático del programa, calcularse (o "precargarse" ) 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 comparándolos con una lista de elementos válidos (o invá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. Las FPGA también hacen un uso extensivo de tablas de búsqueda reconfigurables e implementadas en hardware para proporcionar funcionalidad de hardware programable. Las LUT se diferencian de las tablas hash en que, para recuperar un valorv{\displaystyle v}con clavek{\displaystyle k}, una tabla hash almacenaría el valorv{\displaystyle v}en la ranurah(k){\displaystyle h(k)}dóndeh{\displaystyle h}es una función hash, es decirk{\displaystyle k}se utiliza para calcular la ranura, mientras que en el caso de LUT, el valorv{\displaystyle v}se almacena en la ranurak{\displaystyle k}, por lo tanto, directamente direccionable. [ 2 ] : 466

Historia

Parte de una tabla de logaritmos comunes del siglo XX en el libro de referencia Abramowitz y Stegun.

Antes de la llegada de las computadoras, se utilizaban tablas de consulta 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 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 del 2 al 50 veces y las filas eran "una lista de números que comenzaba con mil, descendiendo por centenas hasta cien, luego descendiendo por decenas hasta diez, luego por unidades hasta 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 × 9 o 12 × 12).

En los inicios de la informática, las operaciones de entrada/salida eran particularmente lentas, incluso en comparación con la velocidad de los procesadores de la época. Resultaba lógico reducir las costosas operaciones de lectura mediante algún tipo de almacenamiento en caché manual , creando tablas de búsqueda estáticas (integradas en el programa) o matrices dinámicas precargadas que contuvieran solo los datos más frecuentes. A pesar de la introducción del almacenamiento en caché a nivel de sistema, que ahora automatiza este proceso, las tablas de búsqueda a nivel de aplicación aún pueden mejorar el rendimiento para los datos que rara vez, o nunca, cambian.

Las tablas de búsqueda fueron una de las primeras funcionalidades implementadas en las hojas de cálculo , y la versión inicial de VisiCalc (1979) incluía una LOOKUPfunción entre sus 20 funciones originales. [ 5 ] Microsoft Excel incluye varias funciones de búsqueda especializadas, como VLOOKUPla búsqueda vertical (como en un libro de consulta tradicional), HLOOKUPla búsqueda horizontal y (desde 2019) XLOOKUPla generación de varias columnas de salida a la vez. [ 6 ]

Limitaciones

Aunque el rendimiento de una LUT está garantizadoO(1){\displaystyle O(1)}Para una operación de búsqueda, no puede haber dos entidades o valores con la misma clave.k{\displaystyle k}Cuando el tamaño del universoU{\displaystyle U}—donde se extraen las claves— es grande, podría ser poco práctico o imposible almacenarlo en memoria . Hay varias maneras de solucionar esto, incluido el uso de una tabla hash [ 2 ] : 468 si muchas claves comparten un valor, o si las claves representan un valor numérico con cierta precisión, reducir esa precisión puede reducir el universo lo suficiente, y luego se puede usar la interpolación para corregir el error debido a la pérdida de precisión.

Ejemplos

Función hash trivial

Para una búsqueda trivial mediante función hash , el valor de datos sin signo se utiliza directamente como índice en 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 la búsqueda binaria con cero ramificaciones y ejecutándose en tiempo constante . [ 7 ]

Contando bits en una serie de bytes

Un problema discreto cuya resolución resulta costosa en muchos ordenadores es el de contar el número de bits que se establecen en 1 en un número (binario), a veces denominado 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". [ 8 ] : 282

Un ejemplo sencillo de código C , diseñado para contar los bits 1 en un entero , podría verse así: [ 8 ] : 283

int count_ones ( unsigned int x ) { int result = 0 ; while ( x != 0 ) { x = x & ( x - 1 ); result ++ ; } return result ; }

La implementación anterior requiere 32 operaciones para evaluar un valor de 32 bits, lo que puede tardar varios ciclos de reloj debido a las bifurcaciones . Se puede " desenrollar " en una tabla de búsqueda que, a su vez, utiliza una función hash simple para un mejor rendimiento. [ 8 ] : 282-283

El array de bits, bits_set, con 256 entradas, se construye indicando el número de bits a uno en cada valor de byte posible (por ejemplo, 0x00 = 0, 0x01 = 1, 0x02 = 1, etc.). Aunque se puede usar un algoritmo en tiempo de ejecución para generar el array bits_set , su uso de ciclos de reloj es ineficiente si se considera su tamaño; por lo tanto, se utiliza una tabla precalculada, aunque se podría usar un script en tiempo de compilación para generar y añadir dinámicamente la tabla al archivo fuente . La suma de unos en cada byte del entero se puede calcular mediante una búsqueda trivial en una función hash para cada byte; de ​​esta forma, se evitan bifurcaciones, lo que resulta en una mejora considerable del rendimiento. [ 8 ] : 284

int count_ones ( int input_value ) { union four_bytes { int big_int ; char each_byte [ 4 ]; } operand = input_value ; 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 [ operand . each_byte [ 0 ]] + bits_set [ operand . each_byte [ 1 ]] + bits_set [ operand . each_byte [ 2 ]] + bits_set [ operand . each_byte [ 3 ]]); }}

Tablas de consulta en el procesamiento de imágenes

Archivo de ejemplo de tabla de búsqueda de 16 bits: rojo (A), verde (B), azul (C). (Las líneas 14 a 65524 no se muestran).

Las tablas de búsqueda (LUT) son una técnica excelente para optimizar la evaluación de funciones cuyo cálculo es costoso y cuyo almacenamiento en caché es económico. 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. [ 9 ]

En aplicaciones de análisis de datos, como el procesamiento de imágenes , se puede utilizar una tabla de búsqueda (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 podría transformarse en una imagen a color para resaltar las diferencias en sus anillos.

En el procesamiento de imágenes, las tablas de búsqueda (LUT, por sus siglas en inglés) suelen denominarse 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 , el término "ventanado" se refiere a un concepto relacionado que permite determinar cómo mostrar la intensidad de la radiación medida.

Discusión

Un ejemplo clásico de reducción de cálculos en tiempo de ejecución mediante tablas de búsqueda es la obtención del resultado de un cálculo trigonométrico , como el seno de un valor. [ 10 ] 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 varios valores, por ejemplo, para cada número entero de grados (la tabla puede definirse como variables estáticas en tiempo de compilación, reduciendo 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 de seno más cercano de una dirección de memoria, y también puede interpolar al seno del valor deseado, en lugar de calcularlo 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 el seno y el coseno) pueden implementarse mediante un arreglo simple. Las funciones que involucran dos o más variables requieren técnicas de indexación de arreglos multidimensionales. En este último caso, se puede emplear un arreglo bidimensional de potencia[x][y] para reemplazar una función que calcule x e y para un rango limitado de valores de x e y. Las funciones que tienen más de un resultado pueden implementarse con tablas de búsqueda que son arreglos de estructuras.

Como ya se mencionó, existen soluciones intermedias que combinan tablas con cálculos sencillos, a menudo mediante interpolación . El precálculo con interpolación puede ofrecer mayor precisión para valores comprendidos entre dos valores precalculados. Si bien esta técnica requiere un poco más de tiempo, puede mejorar significativamente la precisión en aplicaciones que lo necesiten. Dependiendo de los valores que se precalculen, el precálculo con interpolación también puede utilizarse para reducir el tamaño de la tabla de búsqueda sin comprometer la precisión.

Aunque a menudo eficaz, el uso de una tabla de búsqueda puede resultar en una penalización severa si el cálculo que reemplaza es relativamente simple. El tiempo de recuperación de 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 comparación con lo que se requeriría con el cálculo directo de fórmulas. La posibilidad de contaminar la caché también puede convertirse en un problema. Los accesos a tablas grandes casi con certeza causarán un fallo de caché . Este fenómeno se está convirtiendo cada vez más en un problema a medida que los procesadores superan la capacidad de 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 en tablas pueden ser incluso más costosas debido a la comprobación de límites obligatoria que implica una comparación y bifurcación adicionales para cada búsqueda.

Existen dos limitaciones fundamentales para la creación de tablas de búsqueda para una operación específica. Una es la cantidad de memoria disponible: no se puede crear una tabla de búsqueda que supere el espacio disponible, aunque es posible crear tablas de búsqueda en disco, lo que incrementa el tiempo de búsqueda. La otra es el tiempo necesario para calcular los valores de la tabla inicialmente; si bien esto generalmente solo se realiza una vez, si el tiempo es excesivamente largo, el uso de una tabla de búsqueda puede resultar una solución inapropiada. Sin embargo, como se mencionó anteriormente, en muchos casos las tablas pueden definirse estáticamente.

Calculando senos

La mayoría de las computadoras solo realizan operaciones aritméticas básicas y no pueden calcular directamente el seno de un valor dado. En cambio, 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: [ 11 ] : 5

pecado⁡(incógnita)≈incógnita−incógnita36+incógnita5120−incógnita75040{\displaystyle \operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}}(para x cercano a 0)

However, this can be expensive to compute, especially on slow processors, and there are many applications, particularly in traditional computer graphics, that need to compute many thousands of sine values every second. A common solution is to initially compute the sine of many evenly distributed values, and then to find the sine of x we choose the sine of the value closest to x through array indexing operation. This will be close to the correct value because sine is a continuous function with a bounded rate of change.[11]:6 For example:[12]:545–548

realarraysine_table[-1000..1000]forxfrom-1000to1000sine_table[x]=sine(pi*x/1000)functionlookup_sine(x)returnsine_table[round(1000*x/pi)]
Linear interpolation on a portion of the sine function

Unfortunately, the table requires quite a bit of space: if IEEE double-precision floating-point numbers are used, over 16,000 bytes would be required. We can use fewer samples, but then our precision will significantly worsen. One good solution is linear interpolation, which draws a line between the two points in the table on either side of the value and locates the answer on that line. This is still quick to compute, and much more accurate for smooth functions such as the sine function. Here is an example using linear interpolation:

functionlookup_sine(x)x1=floor(x*1000/pi)y1=sine_table[x1]y2=sine_table[x1+1]returny1+(y2-y1)*(x*1000/pi-x1)

La interpolación lineal proporciona una función interpolada continua, pero, en general, no tendrá derivadas continuas . Para una interpolación más suave de la búsqueda en tablas, 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 muestreo no uniforme . Esto significa que, donde la función es casi recta, se utilizan pocos puntos de muestreo, mientras que donde cambia de valor rápidamente se utilizan más puntos de muestreo para mantener la aproximación lo más cercana posible a la curva real. Para obtener más información, consulte la sección sobre interpolación .

Otros usos de las tablas de búsqueda

Cachés

Las cachés de almacenamiento (incluidas las cachés de disco para archivos o las cachés del procesador para código o datos) también funcionan como una tabla de búsqueda. La tabla se construye con memoria muy rápida en lugar de almacenarse en memoria externa más lenta, y mantiene dos datos para un subconjunto de bits que componen una dirección de memoria externa (o de disco) (en particular, los bits menos significativos de cualquier dirección externa posible):

  • Una parte (la etiqueta) contiene el valor de los bits restantes de la dirección; si estos bits coinciden con los de la dirección de memoria que se va a leer o escribir, entonces la otra parte contiene el valor almacenado en caché para esta dirección.
  • La otra parte almacena los datos asociados a esa dirección.

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 menos significativos de la dirección de almacenamiento externo deseada y determinar si la caché ha accedido a esa dirección de memoria. Cuando se encuentra una coincidencia, no es necesario acceder a la memoria externa (excepto para operaciones de escritura, donde puede ser necesario actualizar el valor almacenado en caché de forma asíncrona en la memoria más lenta después de un tiempo, o si se debe reemplazar la posición en la caché para almacenar en caché otra dirección).

LUTs de hardware

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 el array. Estos valores pueden estar cableados, como en un ASIC cuya función es específica, o bien ser proporcionados por biestables D que permiten valores configurables ( ROM , EPROM , EEPROM o RAM ).

Una tabla de búsqueda (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. Este es un método eficiente para codificar funciones lógicas booleanas , y las LUT con 4 a 6 bits de entrada son, de hecho, el componente clave de las modernas matrices de puertas programables en campo (FPGA), que proporcionan capacidades de lógica de hardware reconfigurables.

Sistemas de adquisición y control de datos

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 algunos sistemas, también se pueden definir polinomios en lugar de tablas de consulta para estos cálculos.

Véase también

Referencias

  1. ↑ McNamee, Paul (21 de agosto de 1998). "Memoria automatizada en C++" . Archivado del original el 16 de abril de 2019.
  2. 1 2 Kwok, W.; Haghighi, K.; Kang, E. (1995). "Una estructura de datos eficiente para la técnica de generación de malla triangular de frente de avance" . Communications in Numerical Methods in Engineering . 11 (5). Wiley & Sons: 465– 473. doi : 10.1002/cnm.1640110511 .
  3. ↑ Campbell-Kelly, Martin ; Croarken, Mary ; Robson, Eleanor , eds. (2003). La historia de las tablas matemáticas: desde Sumeria hasta las hojas de cálculo . Oxford University Press.
  4. ↑ Maher, David WJ y John F. Makowski. « Evidencia literaria de la aritmética romana con fracciones », «Filología clásica» (2001), vol. 96, n.º 4, págs. 376-399. (Véase la página 383).
  5. ↑ Bill Jelen: "Desde 1979: ¡VisiCalc y LOOKUP!" , por MrExcel East, 31 de marzo de 2012
  6. ↑ "Función XLOOKUP - Soporte técnico de Microsoft" . support.microsoft.com . Consultado el 19 de enero de 2026 .
  7. ↑ Cormen, Thomas H. (2009). Introducción a los algoritmos (3.ª ed.). Cambridge, Mass.: MIT Press. pp. 253–255 . ISBN   9780262033848Consultado el 26 de noviembre de 2015 .
  8. 1 2 3 4 Jungck P.; Dencan R.; Mulcahy D. (2011). Desarrollo para el rendimiento. En: Programación en packetC . Apress. doi : 10.1007/978-1-4302-4159-1_26 . ISBN 978-1-4302-4159-1.
  9. ↑ nvidia gpu gems2  : usar tablas de búsqueda para acelerar el color
  10. ↑ Sasao, T.; Butler, JT; Riedel, MD "Aplicación de cascadas LUT a generadores de funciones numéricas" . Centro de Información Técnica de Defensa . ESCUELA NAVAL DE POSGRADO MONTEREY CA DEPARTAMENTO DE INGENIERÍA ELÉCTRICA E INFORMÁTICA . Consultado el 17 de mayo de 2024 .{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )
  11. 1 2 Sharif, Haidar (2014). "Funciones matemáticas de alto rendimiento para arquitecturas de un solo núcleo" . Journal of Circuits, Systems and Computers . 23 (4). World Scientific. doi : 10.1142/S0218126614500510 .
  12. ↑ Randall Hyde (1 de marzo de 2010). El arte del lenguaje ensamblador, 2.ª edición (PDF) . No Starch Press. ISBN 978-1593272074– vía Instituto de Computación de la Universidad de Campinas.
  • Búsqueda rápida en tablas utilizando el carácter de entrada como índice para tablas de ramificación.
  • El arte del ensamblaje: Cálculos mediante búsquedas en tablas
  • "Trucos de manipulación de bits" (incluye tablas de consulta) Por Sean Eron Anderson de la Universidad de Stanford
  • Memorización en C++ por Paul McNamee, Universidad Johns Hopkins que muestra ahorros
  • "La búsqueda de un censo de población acelerado" por Henry S. Warren Jr.
Lecturas relacionadas
6 articulos
Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Array (data structure)In computer science , an array is a data structure consisting of a collection of elements ( values or variables ), of same memory size, each identi...Ejecución (computación)Ejecución (computación)La ejecución en ingeniería informática y de software es el proceso mediante el cual una computadora o máquina virtual interpreta y actúa según las ...{\displaystyle f(x)=x^{2}+1;}Function (mathematics)In mathematics, a function from a set X to a set Y assigns to each element of X exactly one element of Y.[1] The set X is called the domain of the ...PrecomputaciónPrecomputaciónEn algoritmos , el precálculo es el acto de realizar un cálculo inicial antes del tiempo de ejecución para generar una tabla de búsqueda que un alg...Static variableStatic variableIn computer programming, a static variable is a variable that has been allocated "statically", meaning that its lifetime (or "extent") is the entir...