Tabla de consulta

En informática, una tabla de consulta o tabla de correspondencia (traducción del término inglés "lookup table", abreviado como "LUT") es una estructura de datos, normalmente un vector o un vector asociativo, que se usa para sustituir una rutina de computación mediante una simple indexación de los vectores. Son muy útiles a la hora de ahorrar tiempo de procesamiento, porque sacar un valor de la memoria es mucho más rápido que hacer un gran cálculo.^[1]: 466

En informática, una tabla es una matriz que reemplaza un cálculo en tiempo de ejecución por una operación más simple de indización de matriz. El ahorro en términos de tiempo de procesamiento puede ser muy significativo, ya que la recuperación de un valor de la memoria es a menudo mucho más rápido^[2] que realizar una operación de computación "inasequible" o de entrada/salida.^[3] Las tablas pueden ser precalculadas y almacenadas en la memoria estática de un programa, calculadas (o "pre-caculadas") como parte de la fase de iniciación de un programa (memoización), o incluso almacenadas en el "hardware" en plataformas específicas de la aplicación. Las tablas de consulta también se utilizan ampliamente para validar los 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 compensar a las etiquetas) para procesar las entradas correspondientes.

Las matrices de puertas lógicas programable en campo (FPGA) también hacen un uso extensivo de tablas de consulta reconfigurables, con la capacidad de manejar "hardware" programable.

Un ejemplo práctico de la utilidad de una lookup table o tabla de consulta es su uso para obtener resultados de funciones sin necesidad de hacer el cálculo, utilizando como valor indexado el valor de entrada y como valor de la salida de la función el valor almacenado en la posición correspondiente al índice. Cuando se utiliza para el procesamiento de imágenes, acostumbra a llamarse LUT.

Historia

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

Antes de la llegada de las computadoras, se usaban tablas de búsqueda de valores para acelerar los cálculos manuales de funciones complejas, tales como funciones trigonométicas, logarítmicas o funciones de densidad estadística.^[4]

En la antigua India (499 d. C.), Aryabhata creó una de los 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 numeración romana) el producto de cada número de 2 a 50 veces y las filas eran "una lista de números que comienzan con mil, descendiendo de cien en cien, luego descendiendo de diez en diez, luego de uno en uno, y luego las fracciones hasta 1/144".^[5] A los niños de la escuela moderna a menudo se les enseña a memorizar la "tabla de multiplicar" para evitar cálculos de los números más comúnmente utilizados (hasta 9x9 o 12x12).

Al principio de la historia de las computadoras, las operaciones de entrada/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 memoria intermedia 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 se usaban 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, o nunca, cambian.

Las tablas de búsqueda fueron una de las primeras funcionalidades implementadas en las hojas de cálculo para ordenador, con la versión inicial de VisiCalc (1979) que incluía una función LOOKUP entre sus 20 funciones originales.^[6] A esto le siguieron las hojas de cálculo posteriores, como Microsoft Excel, y se complementaron con funciones especializadas VLOOKUP y HLOOKUP (en español BUSCARV y BUSCARH) para simplificar la búsqueda en una tabla vertical u horizontal. En Microsoft Excel, la función XLOOKUP (en español BUSCARX)^[7] se implementó a partir del 28 de agosto de 2019.

Limitaciones

Aunque el rendimiento de una LUT es un ${\displaystyle O(1)}$ garantizado para una operación de búsqueda, no hay dos entidades o valores que puedan tener la misma clave ${\displaystyle k}$. Cuando el tamaño del universo numérico ${\displaystyle \cup }$, donde se representan las claves, es grande, puede ser poco práctico o imposible almacenarlo en la memoria. Por lo tanto, en este caso, una tabla hash sería una alternativa preferible.^{[1]: 468 [8]}

Ejemplos

Cálculo sinusoidal

La mayoría de ordenadores, que solamente hacen operaciones aritméticas básicas, no pueden calcular directamente el seno de un valor. Normalmente usan un algoritmo o una fórmula compleja, como pueden ser las series de Taylor, a partir de las que calculan el seno de un valor dado con bastante precisión:^[9]: 5

${\displaystyle \sin(x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}}$ (para x hasta 0)

Por tratarse de un cálculo complejo, estos métodos ralentizan ostensiblemente los procesos y aplicaciones, especialmente si se trata de generar gráficos, que necesitan calcular miles de valores sinusoidales por segundo. En esos casos, es más rápido obtener el resultado manejando una tabla en la que se busca el seno de x cada vez que haga falta. Previamente habrá que haber calculado los valores del seno dentro del rango que interese, almacenándolos en esa tabla. Ejemplo de uso de una tabla de 2001 elementos con los valores del seno entre -π y π:

 real array sine_table[-1000..1000]
 for x from -1000 to 1000
     sine_table[x] := sine (pi * x / 1000)

 function lookup_sine(x)
     return sine_table[round(1000 * x / pi)]

Interpolación lineal de un fragmento del seno

Desafortunadamente, la tabla requiere espacio: si se usan números en formato IEEE de coma flotante y doble precisión, pueden ser necesarios hasta unos 16.000 bytes. De entrada, basta con que el rango de entrada cubra de 0 a π, pero si se necesitara reducir mucho el número de muestras, la precisión empeoraría significativamente. Una buena solución es utilizar la interpolación lineal, que asume una recta uniendo cada dos puntos consecutivos de la tabla, representada sobre un plano, y calcula los valores intermedios asumiendo que se encuentran sobre esa recta. Esto es rápido de calcular, y con bastante precisión en una función continuamente diferenciable como lo es la función seno. Un ejemplo de interpolación lineal es el siguiente:^[9]: 6 For example:^{[10]: 545-548}

 function lookup_sine(x)
     x1 := floor (x*1000/pi)
     y1 := sine_table[x1]
     y2 := sine_table[x1+1]
     return y1 + (y2-y1)*(x*1000/pi-x1)

Ejemplo de tabla de consulta a partir de la interpolación lineal:

Ejemplo de la tabla del seno

// C 8-bit Sine Table
const unsigned char sinetable[256] = {
	128,131,134,137,140,143,146,149,152,156,159,162,165,168,171,174,
	176,179,182,185,188,191,193,196,199,201,204,206,209,211,213,216,
	218,220,222,224,226,228,230,232,234,236,237,239,240,242,243,245,
	246,247,248,249,250,251,252,252,253,254,254,255,255,255,255,255,
	255,255,255,255,255,255,254,254,253,252,252,251,250,249,248,247,
	246,245,243,242,240,239,237,236,234,232,230,228,226,224,222,220,
	218,216,213,211,209,206,204,201,199,196,193,191,188,185,182,179,
	176,174,171,168,165,162,159,156,152,149,146,143,140,137,134,131,
	128,124,121,118,115,112,109,106,103,99, 96, 93, 90, 87, 84, 81, 
	79, 76, 73, 70, 67, 64, 62, 59, 56, 54, 51, 49, 46, 44, 42, 39, 
	37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 18, 16, 15, 13, 12, 10, 
	9, 8, 7, 6, 5, 4, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 
	0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 3, 4, 5, 6, 7, 8, 
	9, 10, 12, 13, 15, 16, 18, 19, 21, 23, 25, 27, 29, 31, 33, 35, 
	37, 39, 42, 44, 46, 49, 51, 54, 56, 59, 62, 64, 67, 70, 73, 76, 
	79, 81, 84, 87, 90, 93, 96, 99, 103,106,109,112,115,118,121,124
};

Véase también

• Tabla de saltos
• Tablas precisas de Gal
• Memoización

Referencias

1. Kwok, W.; Haghighi, K.; Kang, E. (1995). «An efficient data structure for the advancing-front triangular mesh generation technique». Communications in Numerical Methods in Engineering (Wiley & Sons) 11 (5). doi:10.1002/cnm.1640110511.
2. McNamee, Paul (21 de agosto de 1998). «Automated Memoization in C++». Archivado desde el original el 16 de abril de 2019.
3. McNamee, Paul (21 de agosto de 1998). «Automated Memoization in C++». Archivado desde el original el 16 de abril de 2019.
4. Campbell-Kelly, Martin; Croarken, Mary; Robson, Eleanor, eds. (2003). The History of Mathematical Tables: From Sumer to Spreadsheets. Oxford University Press.
5. Maher, David. W. J. and John F. Makowski. "Literary Evidence for Roman Arithmetic With Fractions", 'Classical Philology' (2001) Vol. 96 No. 4 (2001) pp. 376–399. (See page p.383.)
6. Bill Jelen: "From 1979 – VisiCalc and LOOKUP"!, by MrExcel East, 31 March 2012
7. Función BUSCARX (Soporte Microsoft)
8. Cormen, Thomas H. (2009). Introduction to algorithms (3rd edición). Cambridge, Mass.: MIT Press. pp. 253-255. ISBN 9780262033848. Consultado el 26 de noviembre de 2015.
9. Sharif, Haidar (2014). «High-performance mathematical functions for single-core architectures». Journal of Circuits, Systems and Computers (World Scientific) 23 (4). doi:10.1142/S0218126614500510.
10. Randall Hyde (1 de marzo de 2010). The Art of Assembly Language, 2nd Edition. No Starch Press. ISBN 1593272073 – via University of Campinas Institute of Computing.

Enlaces externos

• Fast table lookup using input character as index for branch table
• Art of Assembly: Calculation via Table Lookups
• Color Presentation of Astronomical Images

• Datos: Q690265