Dual-Pivot Binary Search | Hacker News Reader

Dual-Pivot Binary Search

vkostyukov.ru

53 pointsvkostyukov29 comments

A few mistakes in this post IMO:

1. Note that a 3 way pivoting (partitioning or decision) is EXACTLY the same as doing two consecutive 2-way pivoting. Check both functions. They have the exact same # of comparisons and index calculations.

2. Note that Quicksort and Quickselect (QS) and Binarysearch (BS) are very very similar. Quicksort recurses on BOTH partitions whereas QS and BS only recurse on ONE. This is important! You don't care if your pivot in Quicksearch is a little of. You still have to do the work anyways. For QS/BS you do care a lot since the other part gets immediately discarded!

3. Where 2) implies: Quicksort is harder to get non-recursive implementation. You still have to maintain some sort of stack even for the iterative part. Whereas for QS and BS it is very very easy to do an iterative version.

Now notice how you actually worsened the runtime complexity with your new approach:

1. A standard BS discards exactly half the array. Thus, after two iterations you discarded 3/4.

2. Your new algorithm's one iteration is the same as the default BS two iterations but you only remove 2/3.

Conclusion: It makes little sense (other than having fun) to apply this to BS/QS. Though, I like the complexity analysis and the overall post.

Just thinking, won't change complexity, but it could make sense to try and always choose your pivot at the front of a cache-line when possible and then choose this added pivot at then end of the cache line. Probably would only be worth it if the elements in the array numbers or tightly packed structs, and not just pointers to some allocated object elsewhere.

I'm quite disappointed in people saying that I should have replaced recursion with iteration. That wasn't my goal - to tune a binary search algorithm. I've know the exact result of this research before writing post. I've already known that it gives you literally nothing in terms of performance. The only question I had is why is so? And I wanted to show how to combine math and complexity analysis in order to figure this out.

it's not about tuning something and getting gain (in business, in performance). It's about digging into the challenging problems and finding answers (and of course - having fun).

Think about why we split the input array into two equals parts? There is a nice question in Skiena's algorithms book: what would be with time complexity and algorithm itself if we split the array in two parts: 1/3 and 2/3. The best answer is for sure: "Dr. Skiena, are you simply stupid asking these questions? Just rewrite it with iterations instead and relax."

Uh, wouldn't that be called a ternary search?

Saying "double-pivot binary search" is kinda like saying "three-wheeled bicycle".

Both I and my wife have a tendency to call her tricycle a "bike" or "bicycle", and to ride on roads expressly marked as bicycle lanes.

Are you married to a toddler? Do adults ride tricycles?

Many physically disabled people ride tricycles. Don't know about the GP's wife but it's a good thing to keep in mind. Could prevent you from possibly making some painfully unfunny jokes.

She bought it because she likes it over a regular bicycle.

Just to add, there can also be commercial reasons for a tricycle. In my neighborhood growing up in Miami, there was an ice cream vendor and a knife grinder who went around on trikes. In the latter case, the chain was switched over to the grinding stone to provide power.

There are plenty of reasons a person might find a tricycle more appropriate for their use than a bicycle, personal preference of course being a perfectly reasonable one.

That being my wife's reason. She fell in love with recumbents in college, after trying one that a professor had, and bought a Hase Lepus Comfort recumbent tricycle a few years ago. She likes the stability, being close to the ground, sitting on a real seat instead of a saddle, and the cargo space for groceries or camping gear.

Probably poor joke aside, I'd never heard of adults riding tricycles, so thanks in any case for the informative answers.

There is already a different (more useful) algorithm called ternary search (http://en.wikipedia.org/wiki/Ternary_search).

It is trivial to write a binary sort using a single iterating loop instead of using recursion. This is not true for quicksort which needs to maintain a bit of state generally on the stack via recursion. Basically it is a false start to try to optimize binary search's recursion since it is so easy to remove completely.

Maybe I misunderstand something, but I thought the whole point of selecting two pivots in Quicksort was to reduce impact of particularly bad pivot selection.

In this case, I don't know.. Unlike in Quicksort, there is no huge cost after selecting the pivot depending on it's value.

I guess it could be useful if you could expect you're searching for items with a different random distributions than are the items in the list, e.g. you search for uniformly distributed elements in a list with non-uniform distribution (like a highly skewed one).

Having two pivots in Quicksort reduces the number of swaps (# of comparisons is the same).

I wrote a test program in C, using the same functions as OP wrote.

Compiled with maximum optimizations, the binarysearch() was 33% faster over the more complicated dualPivotBinarysearch(). I tested every element of the array, with array sizes from 100000 to 10000000 elements in steps of 100000.

An different iterative version of binary search was 6.5% faster than binarysearch() using the same test.

Why stop at two pivots? At what point does adding pivots reduce speed? Is there an easy to compute heuristic to determine how many pivots makes sense?

These would be my follow up questions.

These are very good questions. The thing is we actually stopped at two pivots. But you can try to obtain the recurrent relation for three pivots by you own using the steps provided in the post.

Unfortunate that the testing only covers the performance impact of the recursive calls used by the main implementation - a tuned binary search function would probably not recurse and simply maintain a tiny stack of indices. The increased number of comparisons would probably matter a lot more in that case.

> a tuned binary search function would probably not recurse and simply maintain a tiny stack of indices.

You don't even need a stack. Binary search is an iterative process:

    int binarysearch(int a[], int k, int lo, int hi) {
      while (lo < hi) {
        int p = lo + (hi - lo) / 2;

        if (k < a[p]) {
          hi = p;
        } else if (k == a[p]) {
          return p;
        } else if (k > a[p]) {
          lo = p + 1;
        }
      }

      return -1;
    }

Quite. I am puzzled by the article. As even the author points out, binary search is tail-recursive, and therefore trivially transformed to an iterative form. So why on earth profile a recursive implementation?

That was the big WTF for me too. Before you start microbenchmarking and talking about the machine instructions for a function call, get rid of the damn function call.

And if we're talking about the cost in cycles of the operations for jump versus compare, shouldn't we also then consider the cost of the calculation of the pivot points?

I haven't done assembly language in a couple of decades, but it seems to me that the cost of calculating the traditional pivot point will be rather cheaper than that for the dual pivots.

At least back in the day, a division by two was a trivial operation (arithmetic shift right by 1), whereas the division by three would require an actual calculation: not a big deal, but more expensive than the ASR.

If your range is not too big( < 32768 ) and the divisor is constant you can do it with a single multiplication and a shift.

More complicated method: http://www.hackersdelight.org/divcMore.pdf

But the compiler will( should, look at generated code ) optimize the constant division anyway.

---

Behold, division by three using only addition and shifting( works up to 32767 ):

  unsigned int div3upto32767( unsigned int n )
  {
     return ( ( n << 13 )+( n << 11 )+( n << 9 )+( n << 7 )+( n << 5 )+( n << 3 )+( n << 1 )+n ) >> 15 ;
  }

---

This one works up to 32767, and then produces a wrong result every ~32767 numbers or so. The result is of by one. When you get over a million, every number is of by a couple of digits.

  uint64_t div3almost( uint64_t n )
  {
     n -= ( n >> 15 ) ;
     return ( ( n << 13 )+( n << 11 )+( n << 9 )+( n << 7 )+( n << 5 )+( n << 3 )+( n << 1 )+n ) >> 15 ;
  }

I don't think the additions are worth it.

I think applying a newton-raphson approach instead of just choosing a fixed pivot could result in fewer comparisons.

On the other hand, a comparison is a dirty cheap operation, even using bit masks and shifts I doubt it will have a big performance impact, unless we're dealing with very very big arrays.

Idea is nice in principle, but as you increase number of pivots it boils down to hashtable.

In my humble opinion main difference between quicksort and binary search is that one sorts numbers quickly, second is efficient in chasing down pointers. Ideally you want to avoid chasing pointers down at all, thus hashtable.

I am curious about the run time analysis. O(log_3 n)

If you have two comparisons per call to your quicksort recursive function instead of just one comparison, are you reducing the complexity at all?

The benefit of this method is less recursive calls, therefore, less overhead of recursion.

You actually increase the complexity.

2 compares with dual-pivot reduces your search space by 2/3

2 compares with single pivot reduces your search space by 3/4

Furthermore binary search can be done iteratively unlike quicksort, so reducing recursion overhead is useless.

If you want to go below nlog(n) during generic sorting you need to choose high information gain algorithm, its easy. This is no way.

Reply on news.ycombinator.com