增量計算(英語:Incremental computing),又稱增量計算法,是一種軟體特性。當部分數據變化時,增量計算試圖僅重新計算那些依賴於變化的數據的輸出,以節省計算時間。[1][2][3] 相比於簡單地重新計算完整的輸出內容,增量計算能夠顯著地節省計算時間。 比如,電子表格的重計算功能可能會採用增量計算的方式,只有當單元格含有的公式直接或間接依賴於發生變化的其他單元格時,該單元格才會被更新。

當一個工具能夠自動地為各種不同的代碼實現增量計算時,該工具可被視為一種用於優化的程序分析工具。

增量計算提供一種計算方法,使得新的輸入/輸出對(I2,O2)能夠從舊的輸入/輸出對(I1,O1)中推演而出。其中的關鍵就在於ΔP函數,它能夠把輸出的變化量與輸入的變化量進行關聯。
增量計算從一個或多個輸入/輸入關係中派生出一對新的輸入/輸出。圖中的ΔP將輸入的變化量與輸出的變化量進行關聯,以實現上述目標。用戶可能關注完整的輸出內容,或部分更新的輸出結果,抑或是對上述兩者皆有所關注。

靜態實現和動態實現

編輯

增量計算在技術實現上可以大致分為兩種類型:

靜態方法 試圖從現有的程序P中派生出一個增量計算程序。例如可以採取進行程序的重新設計、程序重構的手段,或者使用工具自動生成增量計算程序。這種程序的轉換需要發生在輸入或是輸入的變化量出現之前。

動態方法 記錄運行中的程序P在接受某個特定輸入(l1)時的信息。當這P接受另一個輸入(l2)時,把這些信息用於計算並更新輸出結果(從O1變化到O2)。圖示中顯示了:程序P;構成增量計算程序的核心的變化量計算函數ΔP;以及兩組輸入和輸出(I1,O1和I2,O2)。

專用實現和通用實現

編輯

某一些實現增量計算的方法是只適用於特定程序的專用實現方法,但也有一些可以普遍適用於任何程序的通用方法。專用實現方法需要程式設計師特別指定用於保存未修改子計算的算法資料結構。通用實現方法則會使用程式語言特性、編譯器功能或者一些算法來給非增量計算程序賦予增量計算的行為。

現有系統

編輯

編譯器與程式語言支持

編輯

框架與程序庫

編輯

應用

編輯
  • 資料庫(視圖維護)
  • 軟體構建系統
  • 電子表格[6]
  • 軟體開發環境
  • 金融計算
  • 屬性文法分析
  • 圖計算和查詢
  • GUI (例如 React 和 DOM diffing)
  • 科學計算應用程式

另請參閱

編輯

參考文獻

編輯
  1. ^ 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 (英語). 
  2. ^ Umut A. Acar (2005). Self-Adjusting Computation頁面存檔備份,存於網際網路檔案館 (PDF)(Ph.D. thesis).
  3. ^ 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 (英語). 
  4. ^ Hammer, Matthew A.; Acar, Umut A.; Chen, Yan. CEAL: a C-based language for self-adjusting computation. Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation - PLDI '09 (Dublin, Ireland: ACM Press). 2009: 25. ISBN 9781605583921. doi:10.1145/1542476.1542480 (英語). 
  5. ^ Reps, Thomas; Teitelbaum, Tim. The synthesizer generator. Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments - SDE 1 (Not Known: ACM Press). 1984: 42–48. ISBN 9780897911313. doi:10.1145/800020.808247 (英語). 
  6. ^ Hammer, Matthew; Phang, Khoo; Hicks, Michael; Foster, Jeffrey (2014). ADAPTON: Composable, Demand-Driven Incremental Computation頁面存檔備份,存於網際網路檔案館 (PDF). PLDI.