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

Analysis and Implementation of Reversible Sorting Algorithm

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

Generally there are two ways for recovery of system current state to a certain previous state, they are checkpointing and reverse computation. In order to compare implementation costs of the two ways, take how to implement reversible sorting algorithm with minimal costs for example, we implemented the simple selection sorting algorithm with incremental checkpointing which recovered system state with incrementally saved state information. Then, we implemented a reversible sorting algorithm via reverse computation which can recover system state with current state and its program logic. Finally, we verified the validity of these algorithms via a large number of test cases, and concluded that sorting algorithm based on reverse computation is much better than the one using checkpointing under the environment of large-scale data and with lots of data exchanges.