Tabla de búsqueda
En ciencias de la computación , una tabla de búsqueda (LUT) 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 proceso se denomina "direccionamiento directo" y las LUT se diferencian de las tablas hash en una forma en que, para recuperar un valor con la clave , una tabla hash almacenaría el valor en la ranura donde se encuentra una función hash, es decir, se utiliza para calcular la ranura, mientras que en el caso de LUT, el valor se almacena en la ranura , por lo que es directamente direccionable. [1] : 466 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 . [2] 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 los 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 las etiquetas) para procesar la entrada coincidente. FPGA también hacen un uso extensivo de tablas de búsqueda reconfigurables implementadas en hardware para proporcionar funcionalidad de hardware programable.
Antes de la llegada de las computadoras, las tablas de búsqueda de valores se usaban para acelerar los cálculos manuales de funciones complejas, como trigonometría , logaritmos y funciones de densidad estadística. [3]
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 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 centenas a uno cien, luego descendiendo de decenas a diez, luego de uno a uno, y luego las fracciones hasta 1/144 " [4] 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 comúnmente usados ( 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 de búsqueda previa 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 de 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 LOOKUPfunción entre sus 20 funciones originales. [5] Esto ha sido seguido por las hojas de cálculo posteriores, como Microsoft Excel , y complementado por especializado VLOOKUPy HLOOKUPfunciones para simplificar las operaciones de búsqueda en una tabla vertical u horizontal. En Microsoft Excel, la XLOOKUPfunción se implementó a partir del 28 de agosto de 2019.
