可逆排序算法的分析与实现

摘要：

使软件系统基于当前状态恢复先前某一状态的方法通常有两种:检查点和反向计算.为比较这两种方法的实现代价,以如何实现最低代价的可逆排序为例,将增量检查点技术应用于简单选择排序算法,实现了一种通过增量保存程序运行时系统状态的变化信息以恢复系统先前某一状态的排序算法,并通过反向计算技术实现了一种无需系统状态历史信息仅通过系统当前状态和程序自身逻辑便恢复先前状态的可逆排序算法.通过大量测试用例验证了上述两类算法的正确性,并得出在大规模且数据交换频繁的场景下反向计算排序算法远优于检查点排序算法的结论.

关键词：可逆排序算法、检查点、反向计算、最低代价

所属期刊栏目：32

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金60873069;江苏省高校自然科学研究项目14KJB520033;南通市应用研究计划BK2013043

在线出版日期：2015-06-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：304-309