User:ICoud/增量计算
增量计算，是一种软件功能 。当一部分的数据产生了变化，就仅对该产生变化的部分进行计算和更新，以节省计算时间。[1][2][3] 相比于简单地重复计算完整的输出内容，增量计算能够显著地节省计算时间。 比如，电子表格会在实现重计算功能时使用增量计算，只重新计算并更新那些含有公式，且被直接或间接地改变了的单元格。
用于帮助开发者自动实现增量计算的工具，可以被看作是帮助程序优化的程序分析工具。
静态和动态
[编辑]增量计算在技术实现上可以大致分为两种类型：
静态方法 试图从现有的程序P中派生出一个增量计算程序。例如可以采取进行程序的重新设计、程序重构的手段，或者使用工具自动生成增量计算程序。这种程序的转换需要发生在输入或是输入的变化量出现之前。
动态方法 记录运行中的程序P在接受某个特定输入（l1）时的信息。当这P接受另一个输入（l2）时，把这些信息用于计算并更新输出结果（从O1变化到O2）。图示中显示了：程序P；构成增量计算程序的核心的变化量计算函数ΔP；以及两组输入和输出（I1，O1和I2，O2）。
专用实现和通用实现
[编辑]某一些实现增量计算的方法是只适用于特定程序的专用实现方法，但也有一些可以普遍适用于任何程序的通用方法。专用实现方法需要程序员特别指定用于保存未修改子计算的算法和数据结构。通用实现方法则会使用编程语言特性、编译器功能或者一些算法来给非增量计算程序赋予增量计算的行为。
应用程序
[编辑]- 数据库（视图维护）
- 软件构建系统
- 电子表格[4]
- 软件开发环境
- 金融计算
- 属性文法分析
- 图计算和查询
- GUI （例如 React 和 DOM diffing）
- 科学计算应用程序
另请参阅
[编辑]参考文献
[编辑]- ^ Carlsson, Magnus. Monads for incremental computing. Proceedings of the seventh ACM SIGPLAN international conference on Functional programming - ICFP '02 (Pittsburgh, PA, USA: ACM Press). 2002: 26–35. ISBN 9781581134872. doi:10.1145/581478.581482 （英语）.
- ^ Umut A. Acar (2005). Self-Adjusting Computation (PDF)(Ph.D. thesis).
- ^ Demetrescu, Camil; Finocchi, Irene; Ribichini, Andrea. Reactive imperative programming with dataflow constraints. Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications - OOPSLA '11 (Portland, Oregon, USA: ACM Press). 2011: 407. ISBN 9781450309400. doi:10.1145/2048066.2048100 （英语）.
- ^ Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: Composable, Demand-Driven Incremental Computation (PDF). PLDI.