This depend entirely on being able to do the interpolation on your keys. He computes:
offset = (key - min) / (max - min)
but not all data can have arithmetic done on it like that. What if the data in your array are, for example, names?
It's pretty trivial to beat binary search if your data are integers, or other keys on which you can do arithmetic. You can make the uniform distribution assumption, check it as you go, degrade to binary search if the assumption seems flawed, and then proceed from there.
However, if you're given an array of unknown objects, a comparison function, and no way to do arithmetic on your objects, you can't beat binary search.
However, if you're given an array of unknown objects, a comparison function, and no way to do arithmetic on your objects, you can't beat binary search.
... if all you care about is operation count. If you're fetching pages from disk, a B+Tree will perform dramatically better than a binary search.
And if you're fetching pages from disk and have a large cache, a B+Tree can do far better than interpolation search, too. Interpolation search will thrash your cache, resulting in O(log log n) seeks, whereas a cache of size O(n/B) will allow a B+Tree to find data in O(1) seeks.
But now you're talking about different data structures - his assumption was that you had a simple sorted array. We both know that there's a lot that can be done, and when performance really matters you don't use a sorted array, you don't use binary search, and you do take into account things like access pattern, access speed, caches, etc.
But people don't, because they read simplistic articles like this and then believe they know everything. At least the author could hint that there's a lot more that can be done. As it is, it just leaves the naive reader with a sense that they've seen the light, and the experienced reader irritated.
The issue, of course, is that names aren't evenly distributed, so this algorithm could degrade pretty poorly... you'd probably be better off with a simple binary search.
My apologies - the example I gave was a poor one, but I thought the point was clear. Obviously it wasn't.
Suppose instead I give you records of an unknown type, and a function that compares them. Now interpolation search doesn't work and you have to do something either simpler, or more complex.
Quick, what is the fastest way
to search a sorted array?
See? He didn't say I can do arithmetic on the keys, he just said the array is sorted. He then goes and solves a different problem to the one he originally gave.
In short, the real answer is: It depends
Yes, if you can do arithmetic on the keys, and the keys are sorted in the obvious way according to your arithmetic, then interpolation search can be faster than binary search.
But not always, not in the worst case, and not if you have interesting issues about the cache, access speed, etc.
No, I didn't change the problem, I just raised issues with the overly simplistic analysis he gave.
I'm not saying his problem description was great, but it did become clear through the course of the article the additional constraints and assumptions that he was working under. He certainly never said "you're given an array of unknown objects, a comparison function, and no way to do arithmetic on your objects", and that first sentence you quoted doesn't contain enough information to translate directly into that interpretation (where did it say you get a comparison function, for instance?).
I wonder if we're simply in violent agreement - it certainly seems to me that you just aren't getting my point, and while much of what you say is true, it just doesn't seem relevant to me.
Yes, Interpolation Search has better average complexity in those circumstances when it works. However, for almost all cases of Binary Search that I use, Interpolation Search won't work, and isn't applicable. I was trying to make that point.
If your vector is sorted then it's reasonable to assume you have a comparison function between the objects in your vector. Binary Search then requires nothing more than this absolute minimum - just a comparison function. In this case Interpolation Search doesn't work at all.
As Colin pointed out above, it actually gets worse for our author. In cases where the volumes are sufficient to make much of a difference, you are almost certainly going to want to take caching and access speeds into account. Now you need to move out of the realm of Binary or Interpolation Search and into other data structures anyway.
Yes, Interpolation Search is cool and works in a small niche of cases. But mostly, it's irrelevant.
And that's my summary. Cool, but mostly either inapplicable or irrelevant.
I think you're overstating how often you're only going have a sorted vector of unknown type and an opaque comparison function, and understating how often you'll know your types and be able to make a reasonable guess at their distribution.
You're also ignoring how much simpler it is to roll a quick interpolation search than throw together a B+-Tree, to the point where it may make sense as something to try when you've got an hour to try to speed up some process just enough to get you through another week of growing load while you're rewriting your app to do it right.
I'm fascinated that so many of the commenters here seem to be focusing on the fact that the algorithm mentioned doesn't work in every case. My reaction was different -- I thought of a case where it would be less than ideal, and allowed it to inspire me to find an algorithm that worked better than naive binary search for that case, too.
In particular, I thought of the case of searching arrays of strings. If you are doing repeated searches against the same array, you can easily build a table breaking the array down into subarrays all sharing the same first character. (I'm assuming ASCII there!) Using that can quickly eliminate 5 or so comparisons that would be required with a naive binary search.
Okay, that's not brilliant, but might be useful in some circumstances. My bigger point is I thought this article was a very useful reminder that even a terrific general purpose algorithm like binary search can be beaten if you can apply specific domain knowledge to the search.
>In particular, I thought of the case of searching arrays of strings. If you are doing repeated searches against the same array, you can easily build a table breaking the array down into subarrays all sharing the same first character. (I'm assuming ASCII there!) Using that can quickly eliminate 5 or so comparisons that would be required with a naive binary search.
depending on the extent of your "fan-out" your memory budget might explode...
ASCII can be stored in a byte, so at most he is going to use
256*(index+length).
Assuming he doesn't have more than 2^64 byte of data, he will only need 24576 bytes to the index, and only 32768 if he needs a 64 bit, rather than a 32 bit length.
You might even not need the length argument as it is only the next array index subtracted from the current. In that case you need only 16384 bytes.
If you want two bit unicode, you have to use 49152, 65536 and 32768 bytes, respectively.
Caveat emptor: The article fails to mention that interpolation search's worst-case performance is O(n), considerably worse than binary search's O(log n).
And? Quicksort in general runs faster than Heapsort, yet the worst case performance of the first is O(n^2) while the later only O(n log n). If they implemented it, I'm sure they've found that there's a performance boost for large datasets.
Note that properly implemented quicksort has expected O(n log n) time independent of the data (dependent only on the random choices of pivots), whereas interpolation sort's performance is data dependent. That's a pretty important distinction.
I'll point out too that no quicksort implementation uses a truly random choice of pivot. Typically they use the median of three pivots to be pseudo-random.
Your second point may be valid, though not literally. I've implemented quicksort, and I used (pseudo) random pivots, damnit! :)
The article you point to doesn't seem to address the complexity of quicksort with random pivots. However, that is proven to be expected O(n log n) time for any data in Motwani's Randomized Algorithms book, and I don't think the correctness of that has ever been questioned.
> The article you point to doesn't seem to address the complexity of quicksort with random pivots.
That paper is about experimental algorithmics, and avoids discussions of things which aren't practical (such as using truly random pivots).
> However, that is proven to be expected O(n log n) time for any data in Motwani's Randomized Algorithms book, and I don't think the correctness of that has ever been questioned.
Right, but since there are no truly random quicksorts, its hardly a concern.
Please clarify: Why are random pivots not practical? And why do you say there are no truly random quicksorts? Because pseudorandom numbers aren't really random, or for some other reason?
The cost of true randomness is really high (in execution time)
> And why do you say there are no truly random quicksorts?
Because pseudo-random numbers aren't really random.
The only reason this is important is that the pseudo-randomness means that its possible the construct an adversarial input, which could drive the quicksort to take N^2 time.
Only naive implementations of quicksort take O(n^2) time. Most good implementations will switch to another sort (generally heapsort) after detecting adversarial conditions.
My point was that we should give good hackers the benefit of the doubt when they say quicksort, as they are likely to actually be talking about introsort. GNU C uses introsort to implement qsort, and if I were to implement quicksort for an important job, I certainly wouldn't overlook the fact that it can run to O(N^2).
I have thought about this years ago, simply because it is also kind of the way humans search in telephone books. (Advantage of being born in a time when telephone books where still in use). I think humans would also do repeated interpolation, as some letters would be "thicker" (more pages in the book) than others.
You can beat pretty much any algorithm if you make convenient extra assumptions. In this case they have suitable data for the implication search (good for them!), but the title promises too much.
You can't beat binary search without new assumptions.
It doesn't need to be an integer but you're right in that it requires an additional property of the key type that most sorting and searching algorithms do not need: being able to measure the distance between two keys. Most algorithms only need to be able to decide whether a key is less, equal or greater than another key.
This is implicit in having access to the (cumulative) key distribution. Still, the interpolation function can turn out to be pretty expensive, if your data isn't uniform 0-100.
Technically, any data on your computer is represented as an integer. Integer subtraction is simply not guaranteed to be meaningful as a distance operation for all encodings.
For most data types that you're likely to index by (numbers, strings in alphabetical order, dates, tuples of these things), it's quite possible to build a meaningful distance operation which can be used for this. If you're indexing by something for which its difficult to do this (graphs, versioned strings), you should probably rethink your data structure.
It doesn't need to be integer keys, but you need to be able to do the interpolation. Hence you need some kind of arithmetic on your keys, and not all data are like that.
I agree. It does not depend on key distribution. Nor on the type of the key. But we do need to be able to estimate this
(key - min) / (max - min)
where the variables are all keys and we want the expression to give a number between 0 and 1. We just need some way of estimating the 'distance' between keys for the subtraction to work. It does not need to be an exact distance, an average estimate better than random should beat the binary search.
The algorithm they give is effectively a linear interpolation. We could beat their algorithm by fitting a curve to the accumulated known points rather than a straight line to the nearest two points.
I think it should work on many other distributions. You'll probably need to do density estimation on you keys and partition your search space accordingly if the distribution is not known a priori.
compute (max - min) as an int (potentially overflowing), and then convert it to long, defeating the precautions obviously taken against this kind of event with the cast to long elsewhere?
(max - min) is int
((long) key - min) is long
long / int is long since a long is involved.
(size - 1) is int
int * long is long
I think the purpose if the long cast is that the last multiplication produces a long and it doesn't overflow. But then it is casted to an int anyway defeating the purpose.
That's what mathematics is for ... you just need the growth rate.
O(lg lg N) is a smaller growth rate than O(lg N).
Of course, for smaller datasets it doesn't matter.
In fact if you do sorting, for small datasets (that are mostly sorted) a bubble-sort is better than quick-sort, since it doesn't involve random disk accesses and it might even require fewer steps.
I would be curious if this method for searching would apply to sorting (e.g. sorting done in O(N lg lg N)) ... since I remember that sorting done with comparisons can't be better than O(N lg N) (the height of a binary search tree is lg N ... and I think the demonstration was based on that).
So to get back on-topic ... it really depends on the size of your data.
It's pretty trivial to beat binary search if your data are integers, or other keys on which you can do arithmetic. You can make the uniform distribution assumption, check it as you go, degrade to binary search if the assumption seems flawed, and then proceed from there.
However, if you're given an array of unknown objects, a comparison function, and no way to do arithmetic on your objects, you can't beat binary search.