Lookup table

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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.

En informática, una tabla es una matriz que reemplaza cómputo de tiempo de ejecución de una operación de indización de matriz simple. El ahorro en términos de tiempo de procesamiento puede ser significante, ya que la recuperación de un valor de la memoria es a menudo más rápido que someterse a una operación de computación "inasequible" o de entrada / salida. [1] Las tablas pueden ser precalculadas y almacenadas en la memoria de programa estático, calculados (o "pre-buscado") como parte de la fase de inicialización de un programa ("memoization"), o incluso almacenada en el "hardware" en plataformas específicas de la aplicación. Tablas de consultas también se utilizan ampliamente para validar los valores de entrada, haciendo coincidir contra una lista de elementos válidos (o no válido) en una matriz y, en algunos lenguajes de programación, pueden incluir funciones de puntero (o compensar a las etiquetas) para procesar la entrada correspondientes.

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[editar]

Cálculo sinusoidal[editar]

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:

\sin(x) \approx x - \frac{x^3}{6} + \frac{x^5}{120} - \frac{x^7}{5040} (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[editar]

// 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[editar]