This post is part of a series that explores how flexible programming languages and frameworks can get. We all know that with any given task, there are several approaches available to achieve it. Let's look at this in action!
In this post, we will look at the different approaches in implementing an Algorithm Selector. For this article’s purposes, an Algorithm Selector is basically a method or class that determines which appropriate algorithm is best used for a certain input.
Let's say that I want to implement an Algorithm Selector for sorting algorithms. To select the correct algorithm you'll use, I'll base it on the length of the array:
- For smaller arrays, I decided to use Bubble Sort.
- For larger arrays, I want to use Quick Sort.
In this example, let's set the threshold to 100. Any array with more than 100 items will be considered a "large" array.
Of course, there's probably more than 3 ways to ways to do this in Java (or any OOP language for that matter), but, I carefully selected three unique ones that better matches the ff. categories: The Usual, The Okay, and The Complicated.
The Usual
private int[] sort(int[] arrToSort) {
if (arrToSort.length <= 100) {
return this.bubbleSort(arrToSort);
}
return this.quickSort(arrToSort);
}
public void execute() {
var fiftyArray = Helpers.generateArray(50);
var hundredFiftyArray = Helpers.generateArray(150);
this.sort(fiftyArray);
this.sort(hundredFiftyArray);
}
In the above implementation, I simply used an if statement to determine the correct algorithm to use. Pretty straightforward and it just works. Let's step it up a bit.
The Okay
private int[] sort(int[] arrToSort) {
var sortingAlgos = new ISortingAlgorithm[] {
new BubbleSort(),
new QuickSort()
};
var canSort = false;
var i = 0;
do {
canSort = sortingAlgos[i].canSort(arrToSort);
if (canSort) {
return sortingAlgos[i].sort(arrToSort);
}
i++;
} while (!canSort && i < sortingAlgos.length);
return arrToSort;
}
public void execute() {
var fiftyArray = Helpers.generateArray(50);
var hundredFiftyArray = Helpers.generateArray(150);
this.sort(fiftyArray);
this.sort(hundredFiftyArray);
}
Now we're onto something. I've modified the sort method to use a more flexible way of identifying the best algorithm to use. Instead of hardcoding using an if statement, all sorting algorithms are implemented in their own class. These algorithm classes implements the ISortingAlgorithm interface.
public interface ISortingAlgorithm {
int[] sort(int[] arrToSort);
boolean canSort(int[] arrToSort);
}
This interface exposes a canSort method so any class implementation bears the responsibility of checking the input and ultimately declaring "Hey, I'm the one for this array!". A bit cheesy but you get how it works. Additionally, the actual sorting logic (sort method) is implemented inside each algorithm class.
Here's how this looks like for the BubbleSort class:
public class BubbleSort implements ISortingAlgorithm {
@Override
public int[] sort(int[] arrToSort) {
System.out.println("Sorted " + arrToSort.length+ " items by bubble sort!");
return arrToSort;
}
@Override
public boolean canSort(int[] arrToSort) {
return arrToSort.length <= 100;
}
}
The sort method will then iterate over the array of algorithms. Then, the first one to return true when their canSort method is called will be the algorithm used to sort the input array.
That's quite a bit already, right? Well, let's look at something more exciting.
The Complicated
The problem with The Okay approach is that the sorting algorithms are tightly coupled with the executing class. All of them are explicitly instantiated inside the sort method. In terms of good OOP design, it's not recommended to have very tight coupling between classes.
So in this approach, we'll use the Chain of Responsibility design pattern. In this pattern, there's a set of receivers with which the input will pass through. In a few points, here's how this pattern works:
- Once a receiver receives the input, the receiver will evaluate the input.
- If the receiver determines that the input is compatible with it, the receiver will proceed with the actual processing.
- If the input is not compatible with the receiver, the current receiver will just pass the input to the next available receiver.
For this article, the "receivers" are the sorting algorithm classes. I've now modified them to extend the SortingAlgorithm class:
public abstract class SortingAlgorithm {
private SortingAlgorithm NextAlgo = null;
public SortingAlgorithm() {
}
public SortingAlgorithm(SortingAlgorithm NextAlgo) {
this.NextAlgo = NextAlgo;
}
protected abstract boolean canSort(int[] arrToSort);
protected abstract int[] sortInternal(int[] arrToSort);
public int[] sort(int[] arrToSort) {
if (this.canSort(arrToSort)) {
return this.sortInternal(arrToSort);
} else if (this.NextAlgo != null) {
return this.NextAlgo.sort(arrToSort);
} else {
return arrToSort;
}
}
}
As seen above, the SortingAlgorithm class optionally receives the NextAlgo. This is the next algorithm in the chain and it will be called upon if the current algorithm cannot process the input. For simplicity, if there's no available NextAlgo, the sort method will just return the unprocessed input.
Now, let's look at the actual execution using this approach:
var fiftyArray = Helpers.generateArray(50);
var hundredFiftyArray = Helpers.generateArray(150);
var quickSort = new QuickSort();
var bubbleSort = new BubbleSort(quickSort);
var sortChain = new SortingChain(bubbleSort);
sortChain.sort(fiftyArray);
sortChain.sort(hundredFiftyArray);
In the above execution code, the sorting algorithms are actually instantiated outside the algorithm selector class SortingChain. Now, if I need to add/remove sorting algorithms , I don't need to touch the SortingChain class.
If you want to step this up further, you can also use Dependency Injection to dynamically load the sorting algorithms. Additionally, there are other design patterns aside from Chain of Responsibility that can be used to achieve the same thing.
The End
For your reference, all the code for this post can be found here.
Anyway, there's most likely lots of approaches to implementing an Algorithm Selector. Feel free to share them by commenting on this post.
I hoped you enjoyed exploring these with me. I'll be posting more in this series (covering other programming languages too!) so make sure to keep an eye!
