8 ms·

Beating Binary Search

• panic 16y ago
  Interesting article, but without actual numbers it's hard to tell whether the change made any difference in performance.
  • bad_user 16y ago
    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.
• oinopion 16y ago
  It works well only on uniformly distributed keys. Not everyone has pleasure to work with such data.
  • seanos 16y ago
    Actually it will work with any distribution of keys, provided that you know what that distribution is.
    • alextp 16y ago
      As long as they are integer keys, that is.
      • pbiggar 16y ago
        I don't see why.
        • RiderOfGiraffes 16y ago
          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.
        • by 16y ago
          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.
      • DrJokepu 16y ago
        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.
        • by 16y ago
          We only need a ball-park estimate of the distance between keys not an exact measurement. Anything better than random should be an improvement.
        • sesqu 16y ago
          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.
  • pictional 16y ago
    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.
• Tichy 16y ago
  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. Bionics for the win...
• RiderOfGiraffes 16y ago
  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.
  • BrandonM 16y ago
    What if the data in your array are, for example, names? offset = (key[0] - min) / (max - min) doesn't seem very hard to me. Or you could even go by the first 2 digits: offset = (key[0] << sizeof(key[0]) + key[1] - min) / (max - min) 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.
    • RiderOfGiraffes 16y ago
      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.
      • jfager 16y ago
        But that's a different problem. Of course different problems may require different solutions.
        • RiderOfGiraffes 16y ago
          But that's a different problem. No, it's exactly the problem. Quoting: 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.
• bnoordhuis 16y ago
  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).
  • wheaties 16y ago
    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.
    • ramchip 16y ago
      > If they implemented it, I'm sure they've found that there's a performance boost for large datasets. Argh! Perhaps I take things too literally, but the logic in this statement is just painful.
    • pbiggar 16y ago
      Only naive implementations of quicksort take O(n^2) time. Most good implementations will switch to another sort (generally heapsort) after detecting adversarial conditions.
      • jemfinch 16y ago
        In which case they cease to be quicksort, and are instead called "introsort": http://en.wikipedia.org/wiki/Introsort http://en.wikipedia.org/wiki/Introsort
        • pbiggar 16y ago
          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).
    • 16y ago
• aplari 16y ago
  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.
• colomon 16y ago
  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.
  • tbrownaw 16y ago
    That sounds a bit like Burst Tries / burstsort.
    • huherto 16y ago
      You mean the Burst-colomon sort.
  • signa11 16y ago
    >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...
    • tomjen3 16y ago
      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. Remember he only wanted to index the first value.
• pascal_cuoq 16y ago
  I do not know this language (Java?), but doesn't the line int offset = (int) (((size - 1) * ((long) key - min)) / (max - min)); 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?
  • huherto 16y ago
    Let me try to break it down: (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.
    • feijai 16y ago
      > (max - min) is int Incorrect. These are signed values. If you subtract a large negative integer from a large positive integer, the result is larger than an integer.