Tabla de búsqueda - Lookup table

En ciencias de la computación , una tabla de búsqueda es una matriz que reemplaza el cálculo en tiempo de ejecución con una operación de indexación de matriz más simple. El ahorro en el tiempo de procesamiento puede ser significativo, porque recuperar un valor de la memoria es a menudo más rápido que realizar un cálculo "costoso" o una operación de entrada / salida . Las tablas pueden calcularse previamente y almacenarse en un almacenamiento de programa estático , calcularse (o "recuperarse previamente" ) como parte de la fase de inicialización de un programa ( memorizació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 al compararlos 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 compensaciones a etiquetas) para procesar la entrada coincidente. Los FPGA también hacen un uso extensivo de tablas de búsqueda reconfigurables implementadas en hardware para proporcionar funcionalidad de hardware programable.

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 usaban tablas de búsqueda de valores para acelerar los cálculos manuales de funciones complejas, como en trigonometría , logaritmos y funciones de densidad estadística.

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 el 493 d.C., Victorius de Aquitania escribió una tabla de multiplicar de 98 columnas que daba (en números romanos ) 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 cientos a uno. cien, luego descendiendo de decenas hasta diez, luego de uno a uno, y luego las fracciones hasta 1/144 "A los niños de la escuela moderna a menudo se les enseña a memorizar" tablas de multiplicar "para evitar cálculos de los números más utilizados (hasta 9 x 9 o 12 x 12).

Al principio de la historia de las computadoras, las operaciones de entrada / salida eran particularmente lentas, incluso en comparación con las velocidades de procesador de la época. Tenía sentido reducir las costosas operaciones de lectura mediante una forma de almacenamiento en caché 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 ocurren 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 hojas de cálculo de computadora , y la versión inicial de VisiCalc (1979) incluía una LOOKUP función entre sus 20 funciones originales. Esto ha sido seguido por las hojas de cálculo posteriores, como Microsoft Excel , y se complementa con especializada VLOOKUP y HLOOKUP funciones para simplificar las operaciones de búsqueda en una tabla vertical u horizontal. En Microsoft Excel, la XLOOKUP función se implementó a partir del 28 de agosto de 2019.

Ejemplos de

Búsqueda simple en una matriz, una matriz asociativa o una lista vinculada (lista sin clasificar)

Esto se conoce como búsqueda lineal o búsqueda de fuerza bruta , en la que se verifica la igualdad de cada elemento a su vez y el valor asociado, si lo hay, se utiliza como resultado de la búsqueda. Este suele ser el método de búsqueda más lento, a menos que los valores que aparecen con frecuencia aparezcan al principio de la lista. Para una matriz unidimensional o una lista vinculada , la búsqueda suele ser para determinar si hay una coincidencia con un valor de datos de "entrada".

Búsqueda binaria en una matriz o una matriz asociativa (lista ordenada)

Un ejemplo de un " algoritmo de divide y vencerás ", la búsqueda binaria implica que cada elemento se encuentre determinando en qué mitad de la tabla se puede encontrar una coincidencia y repitiendo hasta el éxito o el fracaso. Esto solo es posible si la lista está ordenada, pero ofrece un buen rendimiento incluso con listas largas.

Función hash trivial

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

Contando bits en una serie de bytes

Un problema discreto que es costoso de resolver en muchas computadoras es el de contar el número de bits que se establecen en 1 en un número (binario), a veces llamado 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".

Un ejemplo simple de código C , diseñado para contar los 1 bits en un int , podría verse así: 

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

Este algoritmo aparentemente simple puede tomar potencialmente cientos de ciclos incluso en una arquitectura moderna, porque crea muchas ramificaciones en el bucle, y la ramificación es lenta. Esto se puede mejorar mediante el desenrollado de bucles y algunas otras optimizaciones del compilador. Sin embargo, existe una solución algorítmica simple y mucho más rápida: usar una búsqueda de tabla de función hash trivial .

Simplemente construya una tabla estática, bits_set , con 256 entradas que den el número de un conjunto de bits en cada valor de byte posible (por ejemplo, 0x00 = 0, 0x01 = 1, 0x02 = 1, etc.). Luego use esta tabla para encontrar el número de unidades en cada byte del entero usando una búsqueda de función hash trivial en cada byte por turno, y súmelos. Esto no requiere ramificaciones y solo cuatro accesos a la memoria indexada, considerablemente más rápido que el código anterior. 

/* Pseudocode of the lookup table 'uint32_t bits_set[256]' */
/*                    0b00, 0b01, 0b10, 0b11, 0b100, 0b101, ... */
int bits_set[256] = {    0,    1,    1,    2,     1,     2, // 200+ more entries

/* (this code assumes that 'int' is an unsigned 32-bits wide integer) */
int count_ones(unsigned int x)
{
    return bits_set[ x       & 255]
        + bits_set[(x >>  8) & 255]
        + bits_set[(x >> 16) & 255]
        + bits_set[(x >> 24) & 255];
}

La fuente anterior se puede mejorar fácilmente (evitando el AND y el cambio) "refundiendo" "x" como una matriz de caracteres sin firmar de 4 bytes y, preferiblemente, codificada en línea como una sola declaración en lugar de ser una función. Tenga en cuenta que incluso este algoritmo simple puede ser demasiado lento ahora, porque el código original podría ejecutarse más rápido desde el caché de los procesadores modernos, y las tablas de búsqueda (grandes) no encajan bien en los cachés y pueden causar un acceso más lento a la memoria (además, en el ejemplo anterior, requiere calcular direcciones dentro de una tabla para realizar las cuatro búsquedas necesarias).

Tablas de búsqueda en el procesamiento de imágenes

Muestra de archivo de tabla de búsqueda de 16 bits rojo (A), verde (B), azul (C). (No se muestran las líneas 14 a 65524)

En aplicaciones de análisis de datos, como el procesamiento de imágenes , se utiliza una tabla de búsqueda (LUT) para transformar los datos de entrada en un formato de salida más deseable. Por ejemplo, una imagen en escala de grises del planeta Saturno se transformará en una imagen en color para enfatizar las diferencias en sus anillos.

Un ejemplo clásico de reducción de cálculos en tiempo de ejecución mediante tablas de búsqueda es obtener el resultado de un cálculo de trigonometría , como el seno de un valor. El cálculo de funciones trigonométricas puede ralentizar sustancialmente una aplicación informática. La misma aplicación puede finalizar mucho antes cuando precalcula por primera vez el seno de varios valores, por ejemplo, para cada número entero de grados (la tabla se puede definir como variables estáticas en tiempo de compilación, lo que reduce 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 seno más cercano de una dirección de memoria, y también puede interpolar al seno del valor deseado, en lugar de calcular mediante una fórmula matemática. Por tanto, los coprocesadores matemáticos utilizan tablas de búsqueda 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 seno y coseno) pueden implementarse mediante una matriz simple. Las funciones que involucran dos o más variables requieren técnicas de indexación de matrices multidimensionales. Por tanto, el último caso puede emplear una matriz bidimensional de potencia [x] [y] para reemplazar una función para calcular x y para un rango limitado de valores xey. Las funciones que tienen más de un resultado se pueden implementar con tablas de búsqueda que son matrices de estructuras.

Como se mencionó, existen soluciones intermedias que usan tablas en combinación con una pequeña cantidad de cálculo, a menudo usando interpolación . El cálculo previo combinado con la interpolación puede producir una mayor precisión para los valores que se encuentran entre dos valores calculados previamente. Esta técnica requiere un poco más de tiempo para realizarse, pero puede mejorar en gran medida la precisión en aplicaciones que requieren mayor precisión. Dependiendo de los valores que se calculen previamente, el cálculo previo con interpolación también se puede utilizar para reducir el tamaño de la tabla de búsqueda mientras se mantiene la precisión.

En el procesamiento de imágenes , las tablas de búsqueda a menudo se denominan LUT s (o 3DLUT) y dan un valor de salida para cada uno de un rango de valores de índice. Un LUT común, llamado mapa de colores o paleta , se usa para determinar los colores y los valores de intensidad con los que se mostrará una imagen en particular. En tomografía computarizada , "ventana" se refiere a un concepto relacionado para determinar cómo mostrar la intensidad de la radiación medida.

Aunque a menudo es efectivo, el empleo de una tabla de búsqueda puede resultar en una penalización severa si el cálculo que reemplaza la LUT es relativamente simple. El tiempo de recuperación de la 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 relación con lo que se requeriría mediante el cálculo de fórmulas directas. La posibilidad de contaminar la caché también puede convertirse en un problema. Es casi seguro que los accesos a tablas para tablas grandes provoquen una pérdida de caché . Este fenómeno se está convirtiendo cada vez más en un problema a medida que los procesadores superan 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 de tablas pueden ser incluso más costosas debido a la verificación de límites obligatoria que implica una comparación adicional y una rama para cada búsqueda.

Hay dos limitaciones fundamentales sobre cuándo es posible construir una tabla de búsqueda para una operación requerida. Una es la cantidad de memoria disponible: no se puede construir una tabla de búsqueda más grande que el espacio disponible para la tabla, aunque es posible construir tablas de búsqueda basadas en disco a expensas del tiempo de búsqueda. El otro es el tiempo necesario para calcular los valores de la tabla en primera instancia; aunque esto generalmente debe hacerse solo una vez, si lleva un tiempo prohibitivamente largo, puede hacer que el uso de una tabla de búsqueda sea una solución inapropiada. Sin embargo, como se indicó anteriormente, las tablas se pueden definir estáticamente en muchos casos.

Computación de 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 su lugar, 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:

(para x cerca de 0)

Sin embargo, esto puede ser costoso de calcular, especialmente en procesadores lentos, y hay muchas aplicaciones, particularmente en gráficos por computadora tradicionales , que necesitan calcular muchos miles de valores sinusoidales por segundo. Una solución común es calcular inicialmente el seno de muchos valores distribuidos uniformemente y luego, para encontrar el seno de x , elegimos el seno del valor más cercano a x . Esto estará cerca del valor correcto porque el seno es una función continua con una tasa de cambio limitada. 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 en una parte de la función seno

Desafortunadamente, la tabla requiere bastante espacio: si se utilizan números de coma flotante de doble precisión IEEE, se necesitarían más de 16.000 bytes. Podemos usar menos muestras, pero luego nuestra precisión empeorará significativamente. Una buena solución es la interpolación lineal , que dibuja una línea entre los dos puntos de la tabla a cada lado del valor y ubica la respuesta en esa línea. Esto sigue siendo rápido de calcular y mucho más preciso para funciones fluidas como la función sinusoidal. A continuación, se muestra un ejemplo que utiliza la interpolación lineal: 

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)

La interpolación lineal proporciona una función interpolada que es continua, pero que, en general, no tendrá derivadas continuas . Para una interpolación más suave de la búsqueda de tablas que sea continua y tenga una primera derivada continua , se debe usar la spline de Hermite cúbica .

Otra solución que utiliza una cuarta parte del espacio, pero que tarda un poco más en calcularse, sería tener en cuenta las relaciones entre el seno y el coseno junto con sus reglas de simetría. En este caso, la tabla de búsqueda se calcula utilizando la función seno para el primer cuadrante (es decir, sin (0..pi / 2)). Cuando necesitamos un valor, asignamos una variable para que sea el ángulo envuelto en el primer cuadrante. Luego ajustamos el ángulo a los cuatro cuadrantes (no es necesario si los valores están siempre entre 0 y 2 * pi) y devolvemos el valor correcto (es decir, el primer cuadrante es un retorno directo, el segundo cuadrante se lee de pi / 2-x, tercero y cuarto son negativos del primero y segundo respectivamente). Para el coseno, solo tenemos que devolver el ángulo desplazado por pi / 2 (es decir, x + pi / 2). Para la tangente, dividimos el seno por el coseno (puede ser necesario el manejo de dividir por cero según la implementación): 

function init_sine()
    for x from 0 to (360/4)+1
        sine_table[x] = sin(2*pi * x / 360)

function lookup_sine(x)
    x = wrap x from 0 to 360
    y = mod (x, 90)
    if (x <  90) return  sine_table[   y]
    if (x < 180) return  sine_table[90-y]
    if (x < 270) return -sine_table[   y]
    return -sine_table[90-y]

function lookup_cosine(x)
    return lookup_sine(x + 90)

function lookup_tan(x)
    return lookup_sine(x) / lookup_cosine(x)

Cuando se usa la interpolación, el tamaño de la tabla de búsqueda se puede reducir usando un muestreo no uniforme , lo que significa que donde la función es casi recta, usamos pocos puntos de muestra, mientras que cuando cambia de valor rápidamente usamos más puntos de muestra para mantener la aproximación. cerca de la curva real. Para obtener más información, consulte interpolación .

Otros usos de las tablas de búsqueda

Cachés

Artículo principal: Caché (informática)

Los cachés de almacenamiento (incluidos los cachés de disco para archivos o los cachés de procesador para código o datos) también funcionan como una tabla de búsqueda. La tabla está construida con una memoria muy rápida en lugar de almacenarse en una memoria externa más lenta, y mantiene dos datos para un subrango de bits que componen una dirección de memoria externa (o disco) (en particular, los bits más bajos de cualquier dirección externa posible) :

  • una pieza (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 para leer o escribir, entonces la otra pieza contiene el valor almacenado en caché para esta dirección.
  • la otra pieza mantiene los datos asociados a esa dirección.

Se realiza una búsqueda única (rápida) para leer la etiqueta en la tabla de búsqueda en el índice especificado por los bits más bajos de la dirección de almacenamiento externo deseada y para determinar si la dirección de memoria es alcanzada por la caché. Cuando se encuentra un hit, no se necesita acceso a la memoria externa (excepto para las operaciones de escritura, donde el valor en caché puede necesitar ser actualizado asincrónicamente a la memoria más lenta después de algún tiempo, o si la posición en el caché debe ser reemplazada para almacenar en caché otra habla a).

LUT de hardware

En lógica digital , se puede implementar una tabla de búsqueda 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 la matriz. Estos valores pueden estar cableados, como en un ASIC cuyo propósito es específico para una función, o provistos por pestillos D que permiten valores configurables. ( ROM , EPROM , EEPROM o RAM ).

Un n LUT bits puede codificar cualquier n -input función booleana mediante el almacenamiento de la tabla de verdad de la función en la LUT. Esta es una forma eficiente de codificar funciones lógicas booleanas , y las LUT con 4-6 bits de entrada son, de hecho, el componente clave de las modernas matrices de puertas programables en campo (FPGA) que proporcionan capacidades lógicas de hardware reconfigurables.

Sistemas de adquisición y control de datos

En los sistemas de control y adquisición de datos , las tablas de búsqueda se utilizan comúnmente para realizar las siguientes operaciones en:

  • La aplicación de datos de calibración , para aplicar correcciones a las mediciones no calibradas o valores de consigna ; y
  • Llevar a cabo la conversión de unidades de medida ; y
  • Realización de cálculos genéricos definidos por el usuario.

En algunos sistemas, los polinomios también se pueden definir en lugar de tablas de búsqueda para estos cálculos.

Ver también

Referencias

enlaces externos