Precomputación

En algoritmos , la precomputación consiste en realizar un cálculo inicial antes de la ejecución para generar una tabla de consulta que el algoritmo pueda utilizar, evitando así cálculos repetidos en cada ejecución. 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 sencillo de precomputación es el uso de constantes matemáticas codificadas , como π y e , en lugar de calcular sus aproximaciones con la precisión necesaria durante la ejecución.

En bases de datos , el término materialización se utiliza para referirse al almacenamiento de los resultados de un preprocesamiento, ^{[ 1 ] [ 2 ]} como en una vista materializada . ^{[ 3 ] [ 4 ]}

Precalcular un conjunto de resultados intermedios al inicio de la ejecución de un algoritmo suele aumentar considerablemente su eficiencia . Esto resulta ventajoso cuando una o más entradas se encuentran dentro de un rango suficientemente pequeño como para que los resultados puedan almacenarse en un bloque de memoria de tamaño razonable. Dado que el acceso a la memoria tiene una complejidad temporal prácticamente constante (salvo por los retrasos de la caché ), cualquier algoritmo con un componente cuya eficiencia sea inferior a la constante en un rango de entrada reducido puede mejorarse precalculando valores. En algunos casos, se pueden obtener algoritmos de aproximación eficientes calculando un subconjunto discreto de valores e interpolando para obtener 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 consulta impresas para agilizar los cálculos manuales de funciones complejas, como las tablas trigonométricas , las tablas de logaritmos y las tablas de funciones de densidad estadística . ^{[ 5 ]} A los escolares a menudo se les enseña a memorizar las tablas de multiplicar para evitar los cálculos de los números más comunes (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 mostraba (en números romanos ) el producto de cada número desde 2 hasta 50 veces, y las filas eran "una lista de números que comenzaba con mil, descendiendo por centenas hasta cien, luego descendiendo por decenas hasta diez, luego por unidades hasta uno, y luego las fracciones hasta 1/144". ^{[ 6 ]}

Incluso las implementaciones informáticas modernas de funciones trigonométricas digitales suelen utilizar tablas de consulta precalculadas para proporcionar coeficientes para algoritmos de interpolación o para inicializar algoritmos de aproximación sucesivos .

Muchos ataques a los sistemas criptográficos implican preprocesamiento.

Algunos ejemplos de precomputación a gran escala como parte de algoritmos modernos y eficientes son:

• Mesas arcoíris
• hashes perfectos
• El ataque del cubo
• Árboles BSP precalculados para cálculos de visibilidad en gráficos 3D
• Precálculo de radiosidad para iluminación en gráficos 3D

Los compiladores utilizan ampliamente la precomputación para aumentar la velocidad de ejecución del código resultante: esta precomputación puede considerarse, en efecto, una forma de evaluación parcial del propio código del programa. Ejemplos de este tipo de precomputación incluyen el análisis del flujo de datos y los pasos de reducción de complejidad .

• Tabla matemática
• Eficiencia algorítmica
• Evaluación parcial
• Memorización