Programming in the Large with Design Patterns (2012)
Chapter 7. Strategy
In the context of the Strategy pattern, the term “strategy” is a synonym for algorithm or behavior.
Introduction
Computer programs depend on algorithms. There are fundamental algorithms for routine activities like sorting and searching as well as application-specific algorithms for things like rating an insurance policy or calculating customer discounts.
Many times when programming you have a choice as to which algorithm to use to solve a problem. For example, there are more than 10 different mainstream algorithms for sorting a list of elements.
Algorithm selection is often a design time decision but there are times when it is necessary or desirable to postpone algorithm selection until runtime. Runtime selection is preferable when the choice of algorithm depends on factors not available at design time. Such factors include: nature of input, source of input, user preferences and current conditions. The following scenarios illustrate how these runtime factors can influence algorithm selection:
o In some situations detailed knowledge of input data can be used to select a more efficient algorithm at runtime. For example, insertion sort is likely to be faster than quicksort sort for a small number of input values. However, bucket sort outperforms both when variance among input values is low.
o Different validation algorithms might be used depending on whether the input data is coming from a trusted or untrusted source.
o User preference may directly affect algorithm choice. For example, selecting the economy mode on a hybrid car might activate a special algorithm for controlling throttle response and gear selection.
o A video game might switch from doing pixel-perfect collision detection to simply comparing the bounding box of images if performance (e.g. frames per second) drops below a certain threshold.
Components that postpone algorithm selection until runtime are good candidates for the Strategy design pattern. The Strategy design pattern shows how to design a class with interchangeable algorithms or behaviors.
Figure 58 The Strategy design pattern shows how to design a class with interchangeable algorithms
Intent
The Strategy design pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. Strategy lets the algorithm vary independently from clients that use it (Gamma 1995).
In practice, the opportunity to use the Strategy design pattern might show up as a class with mutually exclusive algorithms or behaviors that are selectable at runtime. For example, the following code fragment uses a compound if statement to select one of three algorithms:
class Context {
void operation() {
if ( . . .) {
// algorithm 1
. . .
}
else if ( . . .) {
// algorithm 2
. . .
}
else {
// algorithm 3
. . .
}
}
}
Strategy encapsulates each algorithm in a separate class and replaces the conditional logic in the context with delegation to an encapsulated algorithm.
Separating the algorithms from the context allows the two to vary independently. New algorithms can be added or existing ones modified without altering the context. Conversely, the context can be modified without affecting the algorithms.
Solution
Figure 59 shows the structure diagram for the Strategy design pattern.
Figure 59 Structure diagram for Strategy design pattern
There is a concrete strategy class for each interchangeable algorithm or behavior. Note, in the context of the Strategy pattern, the term “strategy” is a synonym for algorithm or behavior.
Strategy defines an interface common to all concrete strategy classes. All concrete strategy classes must implement the same interface.
Context is a class with a configurable algorithm or behavior. It keeps a reference to a Strategy object, which is the abstract interface for a concrete strategy.
Clients usually choose which algorithm is used by the context:
void clientCode() {
Strategy s = new ConcreteStrategyC();
Context c = new Context(s);
}
The context delegates to the configured algorithm:
class Context {
private Strategy strategy;
// Constructor
public Context(Strategy s) {
strategy = s;
}
public void contextInterface() {
. . .
strategy.algorithmInterface();
. . .
}
}
Sample Code
In statistics, a sample is a subset of a population. Oftentimes it is impractical to study every member of a population so a sample is selected for study. If it is a representative sample, the information gathered can be used to draw conclusions about the population as a whole.
There are several methods or algorithms for selecting a representative sample. The sample code in this section defines two such algorithms: RandomSample and SystematicSample. RandomSample picks n elements from the population at random. SystematicSample sorts the population and picks n elements at regular intervals from the sorted list.
Figure 60 UML class diagram for sample code
The population in this example is an array of zip codes. SamplingHelper is the context. The class Client creates and configures SamplingHelper with an algorithm and then asks SamplingHelper to select a subset. The selection process is done according to the configured algorithm.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
public class Client {
public static void main(String args[]) {
// Population
int[] zipCodes = new int[] {66209,64113,10162,90210,
61701,55901,48823,62901,50014};
// Instantiate an algorithm and use it to select a sample
// from the population
SamplingStrategy strategy = new RandomSampling();
SamplingHelper helper = new SamplingHelper(zipCodes,strategy);
int[] sample = helper.selectSubset(3);
// Output the sample
for(int i=0; i<sample.length; i++)
System.out.println(sample[i]);
System.out.println();
// Create another sample using a different algorithm
strategy = new SystematicSampling();
helper = new SamplingHelper(zipCodes,strategy);
sample = helper.selectSubset(4);
for(int i=0; i<sample.length; i++)
System.out.println(sample[i]);
}
}
// Context
class SamplingHelper {
private int[] population;
private SamplingStrategy strategy;
public SamplingHelper(int[] population, SamplingStrategy strategy) {
this.population = population;
this.strategy = strategy;
}
public int[] selectSubset(int sampleSize) {
return strategy.sample(population, sampleSize);
}
}
interface SamplingStrategy {
int[] sample(int[] population, int sampleSize);
}
// Simple random sampling. Each element has an
// equal probability of being selected.
class RandomSampling implements SamplingStrategy {
public int[] sample(int[] population, int sampleSize) {
int[] subset = new int[sampleSize];
Random generator = new Random();
// Using an ArrayList makes it easy to sample
// without replacement
ArrayList<Integer> tempArray = new ArrayList<Integer>();
for(int i=0; i<population.length; i++)
tempArray.add(population[i]);
for(int i=0; i<sampleSize; i++)
subset[i] = tempArray.remove(
generator.nextInt( tempArray.size() ));
return subset;
}
}
// Systematic sampling algorithm.
// Sort elements and then select elements at
// regular intervals
class SystematicSampling implements SamplingStrategy {
public int[] sample(int[] population, int sampleSize) {
int[] subset = new int[sampleSize];
Random generator = new Random();
// Make a copy of the population array.
// We don't want to cause function side effects.
int[] sortedPopulation = new int[population.length];
System.arraycopy(population, 0,
sortedPopulation, 0, population.length);
Arrays.sort(sortedPopulation);
int step = sortedPopulation.length / sampleSize;
int startingPoint = generator.nextInt(step+1);
// select elements at regular interval ‘step’
for(int i=0; i<sampleSize; i++)
subset[i] = sortedPopulation[startingPoint + (i*step)];
return subset;
}
}
Discussion
One issue to consider when implementing the Strategy design pattern is how to handle data interchange between the context and strategy objects. One option is to have Context pass data via parameters when calling operations on strategy objects. This is the approached used in the example above:
// pass parameters population and sampleSize
strategy.sample(population, sampleSize);
Another option is to pass a reference to the context and have strategy objects use call back methods on the context to fetch needed data.
// pass a reference to the context
strategy.sample(this);
The first option is appropriate when all strategy objects share the same interface and there is small number of parameters. The second option is more appropriate when strategy objects have different data needs and/or extensive data needs. The one drawback of the second option is increased coupling. With the first option the context knows about strategy objects but strategy objects don’t know about the context. With the second option there is a two-way dependency between context and strategy objects. The second option also requires data retrieval methods on the context. Adding additional data access methods to context goes against the principle of information hiding.
One of the drawbacks of the Strategy design pattern is clients must be aware of different strategy algorithms and understand the tradeoffs among the different algorithms in order to select the best one for a given situation. This increases coupling between clients and the details of implementation. One way to mitigate this drawback is to have the context configure a default strategy object or respond with default behavior when the client has configured no strategy object. Clients that don’t know or don’t care about strategy objects can use the default. Clients that do care about strategy objects can override the default behavior and install their own choice of strategy.
Related Patterns
Strategy has the same static structure as State. The Related Patterns section of the State design pattern describes what is unique about each pattern.