Hispanopedia Wiki
Articulo de referencia

computación incremental

La computación incremental , también conocida como cálculo incremental , es una función de software que, cada vez que cambia un dato , intenta ahorrar tiempo recalculando solo a...

Hispanopedia WikiContenido en espanolLectura gratuita

La computación incremental , también conocida como cálculo incremental , es una función de software que, cada vez que cambia un dato , intenta ahorrar tiempo recalculando solo aquellos resultados que dependen de los datos modificados. [ 1 ] [ 2 ] [ 3 ] Cuando la computación incremental tiene éxito, puede ser significativamente más rápida que calcular nuevos resultados de forma ingenua. Por ejemplo, un paquete de software de hoja de cálculo podría usar la computación incremental en sus funciones de recálculo para actualizar solo aquellas celdas que contienen fórmulas que dependen (directa o indirectamente) de las celdas modificadas.

Una herramienta de computación incremental automatizada es una herramienta especializada de análisis de programas para la optimización.

Incremental computing provides a means of computing a new input/output pair (I2,O2), based on an old input output pair (I1,O1). The key technique is represented by a function ΔP, which relates changes in the input to changes to the output.
La computación incremental obtiene un nuevo par entrada/salida a partir de una o más relaciones anteriores. Para ello, ΔP debe relacionar un cambio en la entrada con un cambio en la salida. El usuario del resultado puede estar interesado en la salida completa actualizada, en la salida delta o en ambas.

Estático versus dinámico

Las técnicas de computación incremental se pueden clasificar a grandes rasgos en dos tipos de enfoques:

Los enfoques estáticos intentan derivar un programa incremental a partir de un programa convencional P utilizando, por ejemplo, diseño y refactorización manuales o transformaciones automáticas del programa. Estas transformaciones se producen antes de que se proporcionen entradas o cambios en las mismas.

Los enfoques dinámicos registran información sobre la ejecución del programa P con una entrada específica (I1) y utilizan esta información cuando la entrada cambia (a I2) para actualizar la salida (de O1 a O2). La figura muestra la relación entre el programa P, la función de cálculo de cambio ΔP, que constituye el núcleo del programa incremental, y un par de entradas y salidas, I1, O1 e I2, O2.

Enfoques especializados frente a enfoques de propósito general

Algunos enfoques de computación incremental son especializados, mientras que otros son de propósito general. Los enfoques especializados requieren que el programador especifique explícitamente los algoritmos y las estructuras de datos que se utilizarán para preservar los subcálculos sin cambios. Los enfoques de propósito general, por otro lado, utilizan técnicas de lenguaje, compilador o algorítmicas para dotar de comportamiento incremental a programas que, de otro modo, no lo serían. [ 4 ]

Métodos estáticos

Derivados del programa

Dado un cálculodo=F(incógnita1,incógnita2,…incógnitanorte){\displaystyle C=f(x_{1},x_{2},\dots x_{n})}y un posible cambioincógnitaj:=Δincógnitaj{\displaystyle x_{j}:=\Delta _{x_{j}}}, podemos insertar código antes de que ocurra el cambio (la prederivada) y después del cambio (la postderivada) para actualizar el valor dedo{\displaystyle C}más rápido que volver a ejecutarF{\displaystyle f}Paige ha escrito una lista de reglas para la diferenciación formal de programas en SUBSETL. [ 5 ]

Ver mantenimiento

En sistemas de bases de datos como DBToaster, las vistas se definen con álgebra relacional. El mantenimiento incremental de vistas analiza estáticamente el álgebra relacional para crear reglas de actualización que mantienen rápidamente la vista ante pequeñas actualizaciones, como la inserción de una fila. [ 6 ]

Métodos dinámicos

El cálculo incremental se logra mediante la creación de un grafo de dependencias que incluye todos los elementos de datos que requieren recalculación y sus respectivas dependencias. Los elementos que deben actualizarse cuando un elemento cambia se determinan mediante el cierre transitivo de la relación de dependencia del grafo. En otras palabras, si existe una ruta desde el elemento modificado a otro, este último puede actualizarse (dependiendo de si el cambio finalmente lo alcanza). El grafo de dependencias puede requerir actualizaciones a medida que cambian las dependencias o cuando se agregan o eliminan elementos del sistema. Su uso es interno y, por lo general, no es necesario mostrarlo al usuario.

Se puede evitar capturar dependencias en todos los valores posibles identificando un subconjunto de valores importantes (por ejemplo, resultados de agregación) en los que se puedan rastrear las dependencias y recalculando incrementalmente otras variables dependientes, equilibrando así la cantidad de información de dependencia que se debe rastrear con la cantidad de recálculo que se debe realizar ante un cambio en la entrada. [ 7 ]

La evaluación parcial puede considerarse un método para automatizar el caso más simple de computación incremental, en el que se intenta dividir los datos del programa en dos categorías: los que pueden variar según la entrada del programa y los que no (y la unidad mínima de cambio es simplemente "todos los datos que pueden variar"). La evaluación parcial puede combinarse con otras técnicas de computación incremental.

Con ciclos en el grafo de dependencias, un solo recorrido por el grafo puede no ser suficiente para alcanzar un punto fijo. En algunos casos, la reevaluación completa de un sistema es semánticamente equivalente a la evaluación incremental, y puede ser más eficiente en la práctica, si no en la teoría. [ 8 ]

Sistemas existentes

Compilador y soporte de lenguaje

  • Incrementalización automática (también llamada "Computación autoajustable" y "Programación funcional adaptativa"), [ 9 ] Delta ML , Haskell adaptativo
  • Generador de sintetizador Cornell [ 10 ]
  • IceDust : un lenguaje personalizado específico para cada dominio.

Marcos de trabajo y bibliotecas

  • Adapton[11] - with implementations in several languages
  • One-way Dataflow Constraints (Reactive Computation in C++)
  • Differential Dataflow
  • Jane Street Incremental
  • Incremental Datalog (LogicBlox)
  • Incremental Prolog (XSB)[12]
  • FSharp.Data.Adaptive
  • Domain-Specific Approaches:
    • Incremental Type Checking.

Applications

  • Databases (view maintenance)
  • Build systems
  • Spreadsheets[13]
  • Development Environments
  • Financial Computations
  • Attribute Grammar Evaluation
  • Graph Computations and Queries
  • GUIs (e.g., React and DOM diffing)
  • Scientific applications.

See also

References

  1. ↑Carlsson, Magnus (2002). "Monads for incremental computing". Proceedings of the seventh ACM SIGPLAN international conference on Functional programming. New York: ACM. pp. 26–35. doi:10.1145/581478.581482. ISBN 1-58113-487-8.
  2. ↑Umut A. Acar (2005). Self-Adjusting Computation(PDF) (Ph.D. thesis).
  3. ↑Camil Demetrescu; Irene Finocchi; Andrea Ribichini (2011). "Reactive Imperative Programming with Dataflow Constraints". Proceedings of the 26th ACM International Conference on Object-Oriented Programming Systems Languages and Applications (OOPSLA 2011). ACM. pp. 407–426. arXiv:1104.2293. doi:10.1145/2048066.2048100. ISBN 978-1-4503-0940-0.
  4. ↑Yan Chen; Joshua Dunfield; Matthew A. Hammer; Umut A. Acar. Implicit self-adjusting computation for purely functional programs. ICFP '11. pp. 129–141. Archived from the original on 2016-10-30. Retrieved 2018-03-12.
  5. ↑Paige, Robert (1981). Formal Differentiation: A Program Synthesis Technique. UMI Research Press. ISBN 978-0-8357-1213-2.
  6. ↑Ahmad, Yanif; Kennedy, Oliver; Koch, Christoph; Nikolic, Milos (2012-06-01). "DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views". Proc. VLDB Endow. 5 (10): 968–979. arXiv:1207.0137. doi:10.14778/2336664.2336670. ISSN 2150-8097.
  7. ↑Mugilan Mariappan; Keval Vora (2019). "GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs". In European Conference on Computer Systems (EuroSys'19). pp. 25:1–25:16. doi:10.1145/3302424.3303974.
  8. ↑Kimberley Burchett; Gregory H. Cooper; Shriram Krishnamurthi (2007). "Lowering: A static optimization technique for transparent functional reactivity". In ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation. pp. 71–80. CiteSeerX 10.1.1.90.5866. ISBN 978-1-59593-620-2.
  9. ↑Hammer, Matthew A.; Acar, Umut A.; Chen, Yan (2009). "CEAL". Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation - PLDI '09. p. 25. doi:10.1145/1542476.1542480. ISBN 9781605583921. S2CID 11058228.
  10. ↑Reps, Thomas; Teitelbaum, Tim (1984). "The synthesizer generator". Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments - SDE 1. pp. 42–48. doi:10.1145/800020.808247. ISBN 978-0897911313.
  11. ↑"Adapton: Programming Language Abstractions for Incremental Computation". adapton.org. Retrieved 2016-10-07.
  12. ↑Saha, Diptikalyan; Ramakrishnan, C. R. (2005). "Incremental Evaluation of Tabled Prolog: Beyond Pure Logic Programs". Practical Aspects of Declarative Languages. Lecture Notes in Computer Science. Vol. 3819. pp. 215–229. CiteSeerX 10.1.1.111.7484. doi:10.1007/11603023_15. ISBN 978-3-540-30947-5. ISSN 0302-9743.
  13. ↑Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: Composable, Demand-Driven Incremental Computation(PDF). PLDI.