2.5 动作
在算法里,变换f经常被用在如下形式的语句中
x = f(x);
应用变换去改变对象的状态,就定义了相应对象上的一个动作(action).变换和动作之间有直接的对偶关系,可以基于变换来定义动作,反之亦然:void a(T& x) { x = f(x); } //从变换定义动作以及T f(T x) { a(x); return x; } //从动作定义变换
虽然存在这种对偶关系,但有时独立的实现效率更高,这种情况下就应该分别提供动作和变换.举例说,如果在很大的对象上定义变换,但是只修改整个状态中很小的一部分,采用动作定义就可能大大提高效率.
练习2.6 请用动作的方式重写本章的各个算法.
项目2.1检查环路的另一种方式是反复检查一个不断更新的元素是否与另一个保存着的元素相等,与此同时按一定间隔更新那个保存的元素.Sedgewicketal.[1982],Brent[1980]和Levy[1982]讨论了这种想法和其他想法.请为轨道分析写一些算法,针对不同应用比较它们的性能,并为选择适当的算法提出一组建议.
