Tabla de búsqueda
En informática , 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 que, para recuperar un valor con clave , una tabla hash almacenaría el valor en la ranura donde hay 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 Los ahorros en el tiempo de procesamiento pueden ser significativos, ya que recuperar un valor de la memoria suele ser más rápido que realizar un cálculo o una operación de entrada/salida "costosos" . [2] Las tablas pueden precalcularse y almacenarse en el almacenamiento de programas estáticos , calcularse (o "precargarse" ) como parte de la fase de inicialización de un programa ( memoización ), o incluso almacenarse en hardware en plataformas específicas de la aplicación. Las tablas de búsqueda también se usan 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 de etiquetas) para procesar la entrada coincidente. FPGAtambién hacer un uso extensivo de tablas de búsqueda reconfigurables e implementadas en hardware para proporcionar funcionalidad de hardware programable.
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. [3]
En la India antigua (499 dC), Aryabhata creó una de las primeras tablas de senos , que codificó en un sistema numérico basado en letras sánscritas. En el año 493 d.C., Victorio 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 comenzando con mil, descendiendo por 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 las escuelas modernas a menudo se les enseña a memorizar " tablas de multiplicar " para evitar los 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 los procesadores 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 (incrustadas en el programa) o matrices dinámicas precargadas para contener solo los elementos de datos más comunes. 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 cambian, si es que alguna vez lo hacen.
Las tablas de búsqueda fueron una de las primeras funcionalidades implementadas en las hojas de cálculo informáticas , con la versión inicial de VisiCalc (1979) que incluía una LOOKUPfunción entre sus 20 funciones originales. [5] Esto ha sido seguido por hojas de cálculo posteriores, como Microsoft Excel , y complementado con funciones especializadas VLOOKUPy HLOOKUPpara simplificar la búsqueda en una tabla vertical u horizontal. En Microsoft Excel, la XLOOKUPfunción se implementó a partir del 28 de agosto de 2019.
