Precomputación
En algoritmos , precomputation es el acto de realizar una inicial de cálculo antes de tiempo de ejecución para generar una tabla de búsqueda que puede ser utilizado por un algoritmo para evitar cálculo repetido cada vez que se ejecuta. La precomputación se utiliza 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 cálculo previo es el uso de constantes matemáticas codificadas de forma rígida , 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 una precomputación, [1] [2] como en una vista materializada . [3] [4]
Calcular previamente un conjunto de resultados intermedios al comienzo de la ejecución de un algoritmo a menudo puede aumentar sustancialmente la eficiencia algorítmica . Esto resulta ventajoso cuando una o más entradas están limitadas 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 (a excepción de 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 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 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). Incluso ya 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, descienden de centenas a cien, luego descienden 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 a menudo utilizan tablas de búsqueda precalculadas para proporcionar coeficientes para algoritmos de interpolación o para inicializar algoritmos de aproximación sucesivos .
Los compiladores utilizan la precomputación ampliamente como un medio para aumentar la velocidad de ejecución del código resultante: esta precomputación puede considerarse en efecto como una forma de evaluación parcial del código del programa en sí. Ejemplos de este tipo de cálculo previo incluyen el análisis del flujo de datos y los pasos de reducción de la fuerza .
