precálculo
En los algoritmos , el cálculo previo es el acto de realizar un cálculo inicial antes del tiempo de ejecución para generar una tabla de búsqueda que un algoritmo puede usar para evitar el cálculo repetido cada vez que se ejecuta. El cálculo previo se usa a menudo en algoritmos que dependen de los resultados de cálculos costosos que no dependen de la entrada del algoritmo. Un ejemplo trivial de precálculo es el uso de constantes matemáticas codificadas , como π y e , en lugar de calcular sus aproximaciones con la precisión necesaria en tiempo de ejecución.
En las bases de datos , el término materialización se utiliza para referirse al almacenamiento de los resultados de un cálculo previo, [1] [2] como en una vista materializada . [3] [4]
Precalcular un conjunto de resultados intermedios al comienzo de la ejecución de un algoritmo a menudo puede aumentar sustancialmente la eficiencia algorítmica . Esto se vuelve ventajoso cuando una o más entradas están restringidas a un rango lo suficientemente pequeño como para que los resultados puedan almacenarse en un bloque de memoria de tamaño razonable. Debido a que el acceso a la memoria es esencialmente constante en la complejidad del tiempo (excepto por los retrasos en el almacenamiento en caché ), cualquier algoritmo con un componente que tenga una eficiencia peor que constante en un rango de entrada pequeño puede mejorarse mediante el cálculo previo de los valores. En algunos casos, se pueden obtener algoritmos de aproximación eficientes calculando un subconjunto discreto de valores e interpolando para valores de entrada intermedios, ya que la interpolación también es una operación lineal.
Antes de la llegada de las computadoras, las personas usaban tablas de búsqueda de valores impresas para acelerar los cálculos manuales de funciones complejas, como en tablas trigonométricas, tablas de logaritmos y tablas de funciones de densidad estadística [5] A los niños en edad escolar 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). Ya 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 de centenas a cien, luego descendiendo de decenas a diez, luego de unidades a uno, y luego las fracciones hacia abajo a 1/144" [6]
Incluso las implementaciones informáticas modernas de funciones trigonométricas digitales suelen utilizar tablas de búsqueda precalculadas para proporcionar coeficientes para algoritmos de interpolación o para inicializar algoritmos de aproximación sucesiva .
Los compiladores utilizan ampliamente el precálculo como un medio para aumentar la velocidad de ejecución del código resultante: este precálculo puede considerarse, en efecto, como una forma de evaluación parcial del propio código del programa. Los ejemplos de este tipo de precálculo incluyen análisis de flujo de datos y pasos de reducción de fuerza .
