Lookup table

Una lookup table (del inglés "tabla de consulta") es, en informática, una estructura de datos, normalmente un arreglo o un arreglo asociativo, que se usa para substituir una rutina de computación con una simple indexación de los arreglos. Son muy útiles a la hora de ahorrar tiempo de procesamiento, porque sacar un valor de memoria es mucho más rápido que hacer una gran computación.

Un ejemplo práctico de la utilidad de una lookup table es su uso de obtener resultados de funciones sin necesidad de hacer el cálculo, utilizando como valor indexado el valor de entrada y como valor que toma la posición, el valor de la salida de la función. Cuando se utiliza para el processamiento de imágenes, acostumbra a llamarse LUT.

Ejemplos

Cálculo sinusoidal

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

(para x hasta 0)

Normalmente, esto puede llegar a ser un cálculo complejo, especialmente al ralentizar los procesadores, y otras aplicaciones, especialmente si son cálculos gráficos, que necesitan calcular miles de valores sinusoidales por segundo. Una solución que se usa inicialmente es calcular el seno de muchos valores que están distribuidos, y entonces encontrar del seno de x el valor que le corresponde. Esto será un valor correcto porque el seno es una función continúa con un rango que va cambiando. Por ejemplo:

 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 punto flotante y doble precisión, hasta unos 16.000 bytes pueden ser necesarios. Se pueden usar menos muestras, pero entonces la precisión empeoraría significativamente. Una buena solución es la Interpolación lineal, que dibuja una línea entre dos puntos de una tabla, donde a cada lado del valor correspondiente a una posición de esa línea. Esto es fácil de calcular, y con mayor precisión en una Función continuamente diferenciable como lo es la función seno. Un ejemplo de la interpolación lineal es la siguiente:

 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 Look Up Table 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
};

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