Using a different algorithm depending on the size of the input

Question

I recently finished a course on advanced algorithms, and another on complexity & computability theory, and in the past few days my mind has been somewhat preoccupied by this question.

Why don't we just use a different algorithm based on the size of the input?

I'm asking this question because I've never seen this done in practice or heard of it, and I'm also simply curious about the answer. I also tried looking it up on StackExchange and Google with various queries but couldn't come up with anything remotely related to my question.

I'll take the example of sorting algorithms, as they're quite common and there are so many, with different properties and runtime complexities.

Say I have three algorithms, SortA, SortB and SortC. SortA is incredibly efficient on inputs of size <= 100 but becomes very slow on inputs that are any bigger; SortB is more efficient on inputs of length > 100 than SortA but falls off quickly after a size of 1000. Finally, SortC isn't very fast on inputs of size < 1000, but is faster than SortA and SortB on very large inputs.

Why shouldn't/couldn't I make a function like this (written in pseudo-C#-ish code for simplicity)? Or why isn't it done in practice?

int[] Sort(int[] numbers) { if (numbers.Length <= 100) { return SortA(numbers); } else if (numbers.Length <= 1000) { return SortB(numbers); } else { return SortC(numbers); } } 

I'm assuming some of the potential reasons are that

1. it's more code to write,
2. more potential bugs since there's more code,
3. it's not necessarily easy to find the exact breakpoints at which some algorithm becomes faster than another, or it might take a lot of time to do so (i.e. running performance tests on various input sizes for every algorithm),
4. the breakpoints could only be on small or medium-sized input, meaning there won't be a significant performance increase that is worth doing the additional implementation work,
5. it just isn't worth it in general, and is only used in applications where performance is crucial (similar to how some numerical algorithms use a different method to solve a problem based on the properties of a matrix, like symmetry, tridiagonality,...),
6. input size isn't the only factor on an algorithm's performance.

I'm familiar with Landau/Big O notation, so feel free to use it in your answers.

Answer 1

Why don't we just use a different algorithm based on the size of the input?

We do. Hybrid algorithms are used all the time.

Why shouldn't/couldn't I make a function like this (written in pseudo-C#-ish code for simplicity)? Or why isn't it done in practice?

That is quite literally how most real-world implementations of sorting algorithms look like.

E.g. quick sort has quite a high overhead, so every real-world quick sort implementation switches to insertion sort for the simple cases at the lower levels of the recursion tree. Instead of switching algorithms at the leaves of the recursion, you can also simply stop sorting altogether at some pre-defined partition size, and then run insertion sort once on the "almost-sorted" result of the "aborted quick sort". This may be more efficient, because instead of having many tiny insertion sorts, you have one longer one, so you don't constantly switch between quick sort and insertion sort in the instruction cache.

Merge sort is also often combined with insertion sort. For example, for cache efficiency, you might want to switch to an in-place insertion sort as soon as the partitions are small enough to fully fit into the cache.

One of the most-widely used sorting algorithms is Timsort, which was implemented for CPython in 2002 by Tim Peters, and has since been adopted by (among others) Oracle JRE (and many others, e.g. IBM J9) as Arrays.sort for reference types, Android, V8, Swift, and GNU Octave. It is a hybrid insertion sort and merge sort, It tries to find "runs" of already sorted elements and merges those; if it can't find any runs, it will create them by partially sorting the list with insertion sort.

Considering that it is used in some of the most widely-used implementations of some of the most widely-used languages, i.e. in Android and Swift (in other words, on pretty much every smartphone and tablet) and also in Java (in other words on pretty much every desktop and a large number of servers) and V8 (i.e. in Chrome and Node.js) and CPython, we can quite confidently say that there is probably not a single person on the planet who has not used it in some form. I don't know about you, but I wouldn't call that "not done in practice", in fact, it doesn't get any more practical than running on almost every computer in the world.

it's not necessarily easy to find the exact breakpoints at which some algorithm becomes faster than another, or it might take a lot of time to do so (i.e. running performance tests on various input sizes for every algorithm)

Introsort solves this by being, as the name implies, introspective. It starts off as a quick sort, but it watches itself while it executes, and when the recursion exceeds a certain depth, it switches to heap sort. Regardless of whether it switches to heap sort in between or stays at quick sort, for very small arrays, it then switches to insertion sort.

Introsort is used in several C and C++ standard library implementations, in .NET, and with Shellsort instead of insertion sort as the final algorithm in Go.

As we have seen above, Timsort has a really clever take on this problem: if the input data doesn't fit its assumptions, it simply makes it fit by partially sorting it first!

Answer 2

I'm coming at this from an engineering rather than an academic answer.

Two algorithms mean twice as much code to write, test, and maintain. It's also twice as much code which could potentially break. With current computers it's often better to write your software as clearly as possible and then optimize if it's required, otherwise you end up creating illegible code for no benefit (I it's possible to write legible efficient code but lets assume for the sake of argument there's a correlation and if both was an easy option then there would be no question to ask).

Next, let's assume that Algorithm A operates best on <1000 items and Algorithm B works best on anything over 1000. In reality how long is Algorithm A really going to take? A fraction of a second? If it's any more than that you could probably step through one at a time and be more efficient. So, if the less efficient algorithm takes less than a second would it really be that inefficient to use the less optimized one?

The largest cost in software is more often than not the development and the bugs. From a practical point of view often the simplest solution really is the best one - why create twice as much code to maintain to save a fraction of a second in operation which humans probably wouldn't notice anyway?

Obviously the question changes if you're processing <1000 items a million times a day but if that's the case just batch them per second!

Answer 3

The answers so far has concentrated on practical aspects. A more academic answer follows.

In Algorithm Analysis we look at what happens when size grows towards infinity. And that is all we do.

So, what happens in your example when size grows? The program will call SortC and ignore the other alternatives. So, all we have to do is analyse SortC and we are done.

To make easy for the students we will only give them the code for SortC. No need to confuse things with unimportant details.

An interesting wrinkle happens when the algorithm is recursive. The top level call and the first levels uses SortC, but the recursive calls can use the other parts. However, it turns out that this will only change the result by a constant factor. And as we know, constant factors are not important... to academics.

A good course in Algorithm Analysis will explain all this, but not all courses are good.

Answer 4

Why don't we just use a different algorithm based on the size of the input?

I'll look at this question from a very different perspective, which is human spaceflight safety. It has been near dogma since the start of human spaceflight that highly critical segments of spaceflight must have a backup flight system. The rationale is a what if game: What if the algorithms used in / the sensors used by the primary flight software are flawed?

The backup flight system typically uses a different and possibly reduced set of sensors and maybe even different effectors than those used by the primary flight system. (Sensors are devices that passively measure aspects of a vehicle's state while effectors are devices that actively change aspects of a vehicle's state.) The backup flight system is driven by backup flight software, which is written by a completely separate group of people than those who write the software for the primary flight system.

The primary argument in favor of a backup flight system is that the reduced scope and reduced sensor set makes the backup flight system and the resulting backup flight software less complex. That the backup flight system was developed by an independent team supposedly makes the system more reliable overall.

The primary arguments against a backup flight system are that the scope is not significantly reduced (those critical sections of flight are inherently complex), that the reduced sensor set does not reduce and may even increase software complexity, that the redundant sensors unnecessarily add weight, that the backup flight system inherently increases cost, and perhaps most importantly, that the people who write the backup flight software / create the backup sensors went to the same schools as did the people who write the primary flight software / create the primary sensors.

As far as I can tell, SpaceX does not ascribe to the concept of a backup flight system. There are others who agree with the SpaceX perspective. From this anti-BFS perspective, it would be far better to spend a fraction of the money needed to develop a backup flight system toward improving the primary (and only) flight system so as to develop better and more reliable behavior by this system.

While this might mean more primary sensors, more inspection into the primary flight system, and greater testing of the primary flight software, the claim is that the end result of ditching the concept of a backup flight system results in a better and cheaper system overall.

Answer 5

It depends on the situation.

Take this example, streaming video. When there is ample bandwidth and CPU available then higher quality video can be encoded. When there is less resources then less quality video can be encoded. Now, is this a change in algorithm, maybe, or maybe it's a change in parameters for a Encode() method.

It does represent a behavioral difference, altered by the environment the software runs in.

Let's assume it's a change in algorithm. It might be just an additional step after the encoding step, say a compression step, or it might actually use a different encoder a different video format, one where sound is encoded as MP3 and not FLAC.

In this case the additional code, the duplicate approach, might allow over 1 million more people to watch, generating a revenue stream of 8 million dollars with maintenance costs of 2 million.

With 6 million profit, now it's worth it.

Another example, and this is used in real time systems for redundancy, is each similar algorithm runs at the same time and produces different answers, then the best solution is derived for the current situation is then used. This is a good way to deal with fault tolerance. If 3 of the 4 algorithms are within 0.01% margin of error then there is consensus and the action should be taken. Think safety systems of nuclear power plants.

So the idea of using similar but different algorithms under different circumstances should absolutely be considered; if it makes sense, and by that we need to consider the side effects that have been mentioned; cost, maintenance, testing, and benefits.

Answer 6

Many times you’ll have a simple algorithm that is fast for small n, But not as n grows, and another algorithm that is more complex and faster for large n. And for small n, the simple algorithm may be faster.

When would you write a hybrid algorithm that picks a simple or a complex algorithm depending on size?

One case where you definitely do it is when the complex algorithm has problems with small n. Are you sure that your favourite Quicksort implementation works with n=0 or n=1? So you handle small sizes separately.

Otherwise you ask yourself: Does anyone care? If I sort 1,000 arrays of size 1, and the complex algorithm is needlessly slow, it still takes no measurable time. But there may be problems that you need to solve gazillions of times for small n, and it makes a difference. And if you build a framework or library, a million apps could use the faster code, so it adds up. So in a situation where someone is willing to pay money for handling small n faster, that’s where you implement a hybrid strategy.