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]
Descripción general
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 (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 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.
Historia
Antes del advenimiento 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 se les suele enseñar 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, descendiendo por cientos a cien, luego descendiendo de decenas a diez, luego de uno a uno, y luego las fracciones hasta 1/144 " [6]
Ejemplos de
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 .
Muchos ataques a los criptosistemas implican precomputación.
Los ejemplos de precomputación a gran escala como parte de algoritmos eficientes modernos incluyen:
- Mesas arcoiris
- Hashes perfectos
- El ataque del cubo
- Precalculada árboles BSP para los cálculos de visibilidad en gráficos 3D
- Cálculo previo de radiosidad para iluminación en gráficos 3D
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 .
Ver también
Referencias
- ^ Jiawei Han; Micheline Kamber (9 de junio de 2011). Minería de datos: conceptos y técnicas: conceptos y técnicas . Elsevier. pag. 159. ISBN 978-0-12-381480-7.
- ^ Sven Groppe (29 de abril de 2011). Gestión de datos y procesamiento de consultas en bases de datos web semántica . Springer Science & Business Media. pag. 178. ISBN 978-3-642-19357-6.
- ^ Karen Morton; Kerry Osborne; Robyn Sands; Riyaj Shamsudeen; Jared Still (28 de octubre de 2013). Pro Oracle SQL . Presione. pag. 48. ISBN 978-1-4302-6220-6.
- ^ Marie-Aude Aufaure; Esteban Zimányi (16 de enero de 2012). Inteligencia empresarial: Primera escuela europea de verano, EBISS 2011, París, Francia, 3-8 de julio de 2011, Conferencias tutoriales . Springer Science & Business Media. pag. 43. ISBN 978-3-642-27357-5.
- ^ Campbell-Kelly, Martin; Croarken, Mary; Flood, Raymond; et al., eds. (2003). La historia de las tablas matemáticas de Sumer a hojas de cálculo . Prensa de la Universidad de Oxford. ISBN 978-0-19-850841-0.
- ^ Maher, David. WJ y John F. Makowski. "Evidencia literaria de la aritmética romana con fracciones", 'Filología clásica' (2001) Vol. 96 No. 4 (2001) págs. 376–399. (Consulte la página p. 383.)