This chapter is from the book
This chapter is from the book
This chapter is from the book
2.5 Actions
Algorithms often use a transformation f in a statement like
x = f(x);
Changing the state of an object by applying a transformation to it defines an action on the object. There is a duality between transformations and the corresponding actions: An action is definable in terms of a transformation, and vice versa:
void a(T& x) { x = f(x); } // action from transformation
and
T f(T x) { a(x); return x; } // transformation from action
Despite this duality, independent implementations are sometimes more efficient, in which case both action and transformation need to be provided. For example, if a transformation is defined on a large object and modifies only part of its overall state, the action could be considerably faster.
Exercise 2.6.
Rewrite all the algorithms in this chapter in terms of actions.
Project 2.1.
Another way to detect a cycle is to repeatedly test a single advancing element for equality with a stored element while replacing the stored element at ever-increasing intervals. This and other ideas are described in Sedgewick, et al. [1979], Brent [1980], and Levy [1982]. Implement other algorithms for orbit analysis, compare their performance for different applications, and develop a set of recommendations for selecting the appropriate algorithm.