Real-World Design Patterns: Strategy

Many software engineers believe that design patterns are overly complicated, mythical, and abstract things that bring no practical value to software development. It is sad. In order to prove that they are real, in this article (and in more to come), we’ll look at some examples of how real software products implement some of the GoF design patterns. Today we are going to visit Strategy, from hot spots point of view. (See previous post on Flyweight here).

Defined strategy

Wikipedia defines the strategy as follows:

In computer programming, the strategy template (also known as policy template) is a software design pattern that allows you to select the behavior of an algorithm at runtime. The strategy model

  • defines a family of algorithms,
  • encapsulates each algorithm, and
  • makes the algorithms interchangeable within this family.

A good starting example is usually sorting arrays/collections. Let’s say we need to sort an array of numbers, so we implement BubbleSort, because it’s relatively easy. Within days we realize that the input data is sometimes much larger than expected, so we implement QuickSort instead, to speed things up. Now QuickSort turns out to be ideal for large datasets, but for small arrays it involves a lot of overhead. What if we took the best of both approaches and chose the right sort strategy at runtime, based on the information we have about the dataset? Let’s look at the diagram below:

We simply extracted a common interface to both sorting algorithms. The interface (or abstract class, depending on the implementation) is called abstract strategywhile BubbleSorter and QuickSorter are the concrete strategies. The worker can choose the right sorting strategy once he encounters the data to be sorted; this policy can be passed to the client via the constructor or a method argument.

Array collections and classes

Now, it may come as no surprise, one of the most obvious strategy implementations in the JDK is introduced by the Comparable interface. And just like in the example above, it has to do with sorting. Just look at the following diagram; it shows how sorting is implemented in Java for lists and arrays:

kind

The similarities are easy to spot between the two diagrams. The comparator interface represents abstract strategyBooleanComparator, TestComparator and UserDefinedComparator are the concrete strategies, while strategy’s clients are represented by arrays and collections in this case. Of course, starting with Java 8, classes like UserDefinedComparator become increasingly rare, because Comparator is a functional interface, so the implementing class itself can be replaced with a simple lambda expression.

Let’s take a look at this. At first sight, a rather strange dependency of Collections.sort on Arrays.sort. The first method first converts the list to an array, using its toArray method. Next, the Arrays.sort method is called and, in a final step, the elements of the list are overwritten by the elements of the array, using a ListIterator. So there is no specific sorting method implemented for lists, Arrays.sort is reused.

Note that Collections.sort() cannot sort any type of collection, as many believe; it can only sort a list. Well, that makes sense if you think about it. If you need to sort a set, you must first use a sorted set. The same goes for maps – there is SortedMap which sorts entries based on their keys. For queues, a sorting method would contradict its primary use case – putting new items on one end, taking on the other – or taking on both ends in the case of Dequeues. The only collection for which it makes sense to have a sort method is List.

But back to the implementation of the strategy, Arrays.sort is another interesting thing. This method first checks whether the transmitted comparator is null or not. If so, the natural order of the elements will be used for sorting. Note that the natural order (implemented as an inner class in Arrays, with the name NaturalOrder) assumes that the elements of the array are comparable (i.e., they implement Comparable). If they don’t, for some reason, a really nasty ClassCastException will be thrown.

Then the sorting method is selected. In most cases, Tim Sort will be used, unless the old Merge Sort is explicitly requested. The latter isn’t a particularly good idea, as it will be removed in a future release, according to his comment. (To request a merge sort, the JVM must be started using the -Djava.util.Arrays.useLegacyMergeSort=true VM argument).

I was curious how the two sorting methods compare in terms of speed. I didn’t use any fancy measurement methods, just used bigger and bigger arrays with random integer values ​​and measured the time it took to sort. The execution times below only reflect the time taken by the sort method, they do not include the time taken to create the test data:

TimOut (ms) Legacy Sort (ms)
ten 16 0
100 0 0
1,000 0 0
10,000 15 47
100,000 78 140
1,000,000 1347 628
10,000,000 8048 7348

As you can see, TimSort is generally a bit faster (except for arrays with very few elements) until we reach a fairly large dataset; from then on, the old algorithm outperforms the new one.

Java 8 functional interfaces

It’s not hard to find more strategy design pattern examples in the JDK, and it’s even easier from version 8. Do a quick reference search for new functional interfaces (predicate, function, consumer, supplier, etc.) helps to understand that this model is used literally everywhere.

Just an example: ArrayList defines a forEach method, which takes a Consumer as a parameter. The ArrayList class has no knowledge of specific consumers, it only knows about the interface. The collection client is responsible for passing the desired implementation of this interface. Of course, these Consumers don’t usually manifest as a class, but are instead represented as lambda expressions.

HashMap and ConcurrentHashMap also rely heavily on Function and BiFunction functional interfaces for computing and merging inputs.

Abdul J. Gaspar