计算机仿真
計算機倣真
계산궤방진
COMPUTER SIMULATION
2015年
3期
304-309
,共6页
可逆排序算法%检查点%反向计算%最低代价
可逆排序算法%檢查點%反嚮計算%最低代價
가역배서산법%검사점%반향계산%최저대개
Reversible Sorting Algorithm%Checkpointing%Reverse Computation%Minimal cost
使软件系统基于当前状态恢复先前某一状态的方法通常有两种:检查点和反向计算.为比较这两种方法的实现代价,以如何实现最低代价的可逆排序为例,将增量检查点技术应用于简单选择排序算法,实现了一种通过增量保存程序运行时系统状态的变化信息以恢复系统先前某一状态的排序算法,并通过反向计算技术实现了一种无需系统状态历史信息仅通过系统当前状态和程序自身逻辑便恢复先前状态的可逆排序算法.通过大量测试用例验证了上述两类算法的正确性,并得出在大规模且数据交换频繁的场景下反向计算排序算法远优于检查点排序算法的结论.
使軟件繫統基于噹前狀態恢複先前某一狀態的方法通常有兩種:檢查點和反嚮計算.為比較這兩種方法的實現代價,以如何實現最低代價的可逆排序為例,將增量檢查點技術應用于簡單選擇排序算法,實現瞭一種通過增量保存程序運行時繫統狀態的變化信息以恢複繫統先前某一狀態的排序算法,併通過反嚮計算技術實現瞭一種無需繫統狀態歷史信息僅通過繫統噹前狀態和程序自身邏輯便恢複先前狀態的可逆排序算法.通過大量測試用例驗證瞭上述兩類算法的正確性,併得齣在大規模且數據交換頻繁的場景下反嚮計算排序算法遠優于檢查點排序算法的結論.
사연건계통기우당전상태회복선전모일상태적방법통상유량충:검사점화반향계산.위비교저량충방법적실현대개,이여하실현최저대개적가역배서위례,장증량검사점기술응용우간단선택배서산법,실현료일충통과증량보존정서운행시계통상태적변화신식이회복계통선전모일상태적배서산법,병통과반향계산기술실현료일충무수계통상태역사신식부통과계통당전상태화정서자신라집편회복선전상태적가역배서산법.통과대량측시용례험증료상술량류산법적정학성,병득출재대규모차수거교환빈번적장경하반향계산배서산법원우우검사점배서산법적결론.
