Lookup table
Una lookup table (del inglés "tabla de consulta") es, en informática, una estructura de datos, normalmente un vector o un vector asociativo, que se usa para sustituir una rutina de computación con una simple indexación de los vectores. 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 las entradas 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 procesamiento de imágenes, acostumbra a llamarse LUT.
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:
(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 buscar el resultado en una tabla donde buscamos 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 π:
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 la siguiente:
Ejemplo de tabla Look Up Table a partir de la interpolación lineal: