La computación incremental , también conocida como cómputo incremental , es una característica del software que, siempre que cambia un dato , intenta ahorrar tiempo recalculando solo aquellas salidas 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 nuevas salidas de manera ingenua. Por ejemplo, un paquete de software de hojas de cálculo podría usar computación incremental en sus características de recálculo, para actualizar solo aquellas celdas que contienen fórmulas que dependen (directa o indirectamente) de las celdas modificadas.
Cuando la computación incremental se implementa mediante una herramienta que puede implementarla para una variedad de diferentes piezas de código de manera automática, esa herramienta es un ejemplo de una herramienta de análisis de programas para optimización .
Las técnicas de computación incremental se pueden dividir en dos tipos de enfoques:
Los enfoques estáticos intentan derivar un programa incremental a partir de un programa convencional P mediante, por ejemplo, diseño y refactorización manuales o transformaciones automáticas del programa. Estas transformaciones del programa se producen antes de que se proporcionen entradas o cambios de entrada.
Los enfoques dinámicos registran información sobre la ejecución del programa P en una entrada particular (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.
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 dar un comportamiento incremental a programas que de otro modo no serían incrementales. [4]
Dado un cálculo y un cambio potencial , podemos insertar código antes de que se produzca el cambio (la prederivada) y después del cambio (la postderivada) para actualizar el valor de más rápido que si se vuelve a ejecutar . Paige ha escrito una lista de reglas para la diferenciación formal de programas en SUBSETL. [5]
En sistemas de bases de datos como DBToaster, las vistas se definen con álgebra relacional. El mantenimiento incremental de la vista analiza estáticamente el álgebra relacional para crear reglas de actualización que mantienen rápidamente la vista en presencia de pequeñas actualizaciones, como la inserción de una fila. [6]
El cálculo incremental se puede lograr mediante la construcción de un gráfico de dependencia de todos los elementos de datos que pueden necesitar ser recalculados y sus dependencias. Los elementos que necesitan ser actualizados cuando un solo elemento cambia están dados por el cierre transitivo de la relación de dependencia del gráfico. En otras palabras, si hay una ruta desde el elemento modificado a otro elemento, este último puede ser actualizado (dependiendo de si el cambio finalmente alcanza al elemento). El gráfico de dependencia puede necesitar ser actualizado a medida que cambian las dependencias, o a medida que se agregan o eliminan elementos del sistema. Lo utiliza internamente la implementación y, por lo general, no necesita ser mostrado al usuario.
La captura de dependencias entre todos los valores posibles se puede evitar identificando un subconjunto de valores importantes (por ejemplo, resultados de agregación) entre los cuales se pueden rastrear las dependencias y recalculando de manera incremental otras variables dependientes, equilibrando así la cantidad de información de dependencia a rastrear con la cantidad de recálculo a realizar ante un cambio de entrada. [7]
La evaluación parcial puede considerarse un método para automatizar el caso más simple posible de computación incremental, en el que se intenta dividir los datos del programa en dos categorías: los que pueden variar en función de la entrada del programa y los que no pueden (y la unidad de cambio más pequeña es simplemente "todos los datos que pueden variar"). La evaluación parcial puede combinarse con otras técnicas de computación incremental.
En el caso de los ciclos en el gráfico de dependencia, una sola pasada por el gráfico 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]
