使用者: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.