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.

La computación incremental proporciona un método para calcular un nuevo par de entrada/salida (I2,O2) a partir de un par de entrada/salida anterior (I1,O1). La técnica clave se representa mediante una función ΔP, que relaciona los cambios en la entrada con los cambios en la salida.
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 ] - con implementaciones en varios lenguajes
  • Restricciones de flujo de datos unidireccionales (Computación reactiva en C++)
  • Flujo de datos diferencial
  • Jane Street Incremental
  • Registro de datos incremental ( LogicBlox )
  • Prolog incremental (XSB) [ 12 ]
  • FSharp.Datos.Adaptativos
  • Enfoques específicos de cada dominio:
    • Verificación de tipos incremental.

Aplicaciones

  • Bases de datos (mantenimiento de vistas)
  • Construir sistemas
  • Hojas de cálculo [ 13 ]
  • Entornos de desarrollo
  • Cálculos financieros
  • Evaluación de la gramática de atributos
  • Cálculos y consultas de grafos
  • Interfaces gráficas de usuario (por ejemplo, React y comparación del DOM)
  • Aplicaciones científicas.

Véase también

Referencias

  1. ↑ Carlsson, Magnus (2002). «Mónadas para computación incremental». Actas de la séptima conferencia internacional ACM SIGPLAN sobre programación funcional . Nueva York: ACM . págs. 26–35 . doi : 10.1145/581478.581482 . ISBN  1-58113-487-8.
  2. ↑ Umut A. Acar (2005). Computación autoajustable (PDF) (tesis doctoral).
  3. ↑ Camil Demetrescu; Irene Finocchi; Andrea Ribichini (2011). «Programación imperativa reactiva con restricciones de flujo de datos» . Actas de la 26.ª Conferencia Internacional ACM sobre Sistemas, Lenguajes y Aplicaciones de Programación Orientada a Objetos (OOPSLA 2011) . ACM . págs. 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. Computación autoajustable implícita para programas puramente funcionales . ICFP '11. págs. 129–141 . Archivado del original el 30-10-2016 . Recuperado el 12-03-2018 . 
  5. ↑ Paige, Robert (1981). Diferenciación formal: una técnica de síntesis de programas . UMI Research Press. ISBN 978-0-8357-1213-2.
  6. ↑ Ahmad, Yanif; Kennedy, Oliver; Koch, Christoph; Nikolic, Milos (2012-06-01). "DBToaster: Procesamiento delta de orden superior para vistas dinámicas y frecuentemente actualizadas". 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: Procesamiento síncrono basado en dependencias de grafos en flujo". En Conferencia Europea sobre Sistemas Informáticos (EuroSys'19) . págs. 25:1–25:16. doi : 10.1145/3302424.3303974 . 
  8. ↑ Kimberley Burchett; Gregory H. Cooper; Shriram Krishnamurthi (2007). "Lowering: Una técnica de optimización estática para la reactividad funcional transparente". En 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". Actas de la conferencia ACM SIGPLAN de 2009 sobre diseño e implementación de lenguajes de programación - PLDI '09 . pág. 25. doi : 10.1145/1542476.1542480 . ISBN  9781605583921. S2CID 11058228 . 
  10. ↑ Reps, Thomas; Teitelbaum, Tim (1984). "El generador de sintetizadores". Actas del primer simposio de ingeniería de software ACM SIGSOFT/SIGPLAN sobre entornos prácticos de desarrollo de software - SDE 1. págs. 42–48 . doi : 10.1145/800020.808247 . ISBN  978-0897911313.
  11. ↑ "Adapton: Abstracciones de lenguajes de programación para computación incremental" . adapton.org . Consultado el 7 de octubre de 2016 .
  12. ↑ Saha, Diptikalyan; Ramakrishnan, CR (2005). "Evaluación incremental de Prolog tabulado: más allá de los programas de lógica pura". Aspectos prácticos de los lenguajes declarativos . Notas de clase en informática. Vol. 3819. págs. 215–229 . CiteSeerX 10.1.1.111.7484 . doi : 10.1007/11603023_15 . ISBN    978-3-540-30947-5ISSN 0302-9743​​ 
  13. ↑ Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: Composable, Demand-Driven Incremental Computation (PDF) . PLDI.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Incremental_computing&oldid=1360374352 "
Lecturas relacionadas
6 articulos
Característica del softwareCaracterística del softwareEn software , una característica es una característica identificable de un programa de computadora . [1]DatosEstos son algunos de los diferentes tipos de datos: Geográficos, Culturales, Científicos, Financieros, Estadísticos, Meteorológicos, Naturales, Tra...TiempoTiempoEl tiempo es la secuencia continua de existencia y eventos que ocurre en una sucesión aparentemente irreversible desde el pasado , a través del pre...Hoja de cálculoHoja de cálculoUna hoja de cálculo es una aplicación informática para el cálculo , organización, análisis y almacenamiento de datos en forma de tabla . [1] [2] [3...FórmulaFórmulaEn ciencia , una fórmula es una forma concisa de expresar información simbólicamente, como en una fórmula matemática o una fórmula química . El uso...Análisis del programaAnálisis del programaEn informática , el análisis de programas [1] es el proceso de analizar automáticamente el comportamiento de los programas informáticos en relación...