Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

You can beat the binary search

lemire.me

Post reply on HN
Print view View original

121–130 of 175 posts

Re: You can beat the binary search

#121

Post by crazygringo »

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

Sure, but the whole point is that you often don't know anything further about the data.

That's why b-trees are the standard in databases. The data could be anything, and its characteristics could massively change at any time, as you suddenly import a whole bunch of new rows at once.

And while you can certainly design algorithms around e.g. gradient descent to try to accelerate lookup, b-trees are already incredibly fast, and have lots of other benefits like predictable worse-case performance and I/O requirements, supporting range scans, ordered traversal, prefix conditions, etc.

So yes, you can certainly design lookup algorithms that are more efficient for particular data distributions, but they will also often lack other important properties. And b-trees are already so fast, improvements are often negligible -- like even if another algorithm produces a closer initial guess, it may be slower to locate the final item, or it may be faster on average but have horrible worst-case performance that makes it unusable.

Even with a paper dictionary, I've always used pretty much a binary search beyond the first initial guess, which only saves you a couple of hops. And actually, once I get to the right handful of pages I'm probably more linear than I should be, and I'd probably be faster if I tried to do a rigorous binary search, but I have to balance that with how long it takes to flip pages.

Re: You can beat the binary search

#122

Post by _jackdk_ »

ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

Fritz Henglein has done some interesting work on fast sorting/grouping. I think Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1] is the main paper. Ed Kmett took those ideas and refined them into the discrimination[2] library for Haskell, and gave a very interesting tech talk about it[3].

[1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220

[2]: https://hackage.haskell.org/package/discrimination

[3]: https://www.youtube.com/watch?v=cB8DapKQz-I

Re: You can beat the binary search

#123

Post by skybrian »

crazygringo wrote: post #121
ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

Sure, but the whole point is that you often don't know anything further about the data. That's why b-trees are the standard in databases. The data could be anything, and its characteristics could massively change at any time, as you suddenly import a whole bunch of new rows at once. And while you can certainly design algorithms around e.g. gradient descent to try to accelerate lookup, b-trees are already incredibly f…

Databases often use table statistics to try to do better at generating query plans. I wonder if they use them to make indexes faster as well?

Re: You can beat the binary search

#124

Post by thaumasiotes »

compiler-guy wrote: post #56
jstanley wrote: post #5

As a teenager I spent a weekend thinking that if binary search was good, because it cuts the search space in half at every step, then wouldn't a ternary search be better? Because we'd cut it into thirds at every step. So instead of just comparing the middle value, we'd compare the one at the 1/3 point, and if that turns out to be too low then we compare the value at the 2/3 point. Unfortunately although we cut the se…

This idea is closely related to the famous "Stooge Sort", which is basically quicksort with the pivot at 1/3 rather than 1/2. Naively, one might think it is faster than Quicksort, but of course it isn't. For years--maybe still?--analyzing its running time was a staple of the first or second problem set in a college-level "Introduction to Algorithms" course. https://en.wikipedia.org/wiki/Stooge_sort

> the famous "Stooge Sort", which is basically quicksort with the pivot at 1/3 rather than 1/2. Naively, one might think it is faster than Quicksort, but of course it isn't.

The pivot in quicksort isn't located anywhere fixed. You can do quicksort by always choosing the pivot to be the first element in the (sub)list before you do the swapping. If it happens that the pivot you choose always belongs 1/3 of the way through the sorted sublist... that won't even affect the asymptotic running time; it will still be O(n log n).

Stoogesort is nothing like that. It's worse than quadratic.

In quicksort, though, once you've done your thing with the pivot, you break the list into two non-overlapping sublists. If it happened that the pivot broke the list into 1/3 and 2/3, you'd then recur with one sublist of length n and one of length 2n.

Stoogesort has a different recursion pattern: you recur on the first 2/3, then you recur on the second 2/3, then you recur on the first 2/3 again.

The processing step isn't similar to quicksort either - in quicksort, you get a sublist, choose an arbitrary pivot, and then process the list such that every element of the list is correctly positioned relative to the pivot, which takes O(n) time. In stoogesort, you process the list by swapping the beginning with the end if those two elements are out of order, which takes O(1) time.

Re: You can beat the binary search

#125

Post by giovannibonetti »

tantalor wrote: post #79
ssivark wrote: post #67

Daniel Lemire's points about low-level hardware optimization notwithstanding, it's worth pointing out that binary search (or low-level implementation variants) is the best only if you know nothing about the data beyond the fact that it is sorted / monotonic. If you have priors about the data distribution, then it's possible to design algorithms which use that extra information to perform MUCH better. eg: a human sear…

> use that extra information to perform MUCH better Do you mean using a better estimator for the median value? Or something else?

Say, if you know the function is a polynomial of degree N, with N+1 datapoints you can find it – e.g. with Lagrange's polynomial, although the finite precision of computer numbers might make that more complex.

Re: You can beat the binary search

#126

Post by 10000truths »

skybrian wrote: post #123
crazygringo wrote: post #121

Earlier quoted context omitted.

Sure, but the whole point is that you often don't know anything further about the data. That's why b-trees are the standard in databases. The data could be anything, and its characteristics could massively change at any time, as you suddenly import a whole bunch of new rows at once. And while you can certainly design algorithms around e.g. gradient descent to try to accelerate lookup, b-trees are already incredibly f…

Databases often use table statistics to try to do better at generating query plans. I wonder if they use them to make indexes faster as well?

The cost plan is a crude approximation of the actual query cost. Sometimes, the query planner makes a terrible guess. Your resident DBA won't appreciate being sometimes paged at 3 AM on a Sunday. A good strategy is to freeze the query plan once you have sufficient sample size of data in the involved tables.

Re: You can beat the binary search

#127

Post by Rusky »

aidenn0 wrote: post #112
nly wrote: post #97

Earlier quoted context omitted.

Searching the upper cache lines in your binary search tree (sorted vector) for your target is unlikely to yield results. Instead you want to use the extra data in the line to shorten the search, which leads you to a B-Tree or B+tree. For 4 byte keys and 4 byte child pointers (or indexes in to an array) your inner nodes would have 7 keys, 8 child pointers and 1 next pointer, completely filling a 64 byte cache-line and…

Binary searching a sorted array is isomorphic to a sorted binary tree with implicit child pointers. It seems to me like there should be a sort order that stores the items as a fully-dense left-shifted binary tree from top-to-bottom (e.g. like the implicit heap in an in-place heap sort, but a binary search tree instead of a hea). Is there a name for this? Does it show any performance wins in practice?

There's Eytzinger order: https://algorithmica.org/en/eytzinger

Re: You can beat the binary search

#128

Post by mbowring »

XCSme wrote: post #106

Is it possible to do some sort of Binary* Search (Binary Star, as in A* star search algorithm, where we use heuristics). a: [1,3,5,7,8,9,10,15] x: 8 (query value) For this array, we would compare a[0], a[3], a[7] (left/mid/right) by subtracting 9. And we would get d=[-7, -1, 7] Now, normally, with binary search, because 8 > mid, we would go to (mid+right)/2, BUT we already have some extra information: we see that x i…

Yeah this is basically interpolation search

Re: You can beat the binary search

#129

Post by XCSme »

mbowring wrote: post #128
XCSme wrote: post #106

Is it possible to do some sort of Binary* Search (Binary Star, as in A* star search algorithm, where we use heuristics). a: [1,3,5,7,8,9,10,15] x: 8 (query value) For this array, we would compare a[0], a[3], a[7] (left/mid/right) by subtracting 9. And we would get d=[-7, -1, 7] Now, normally, with binary search, because 8 > mid, we would go to (mid+right)/2, BUT we already have some extra information: we see that x i…

Yeah this is basically interpolation search

Oh, that's what the article was referring to with "interpolation".

Weird that I didn't hear about it before, it's not that used in practice?

One reason I could see is that binary search is fast enough and easy to implement. Even on largest datasets it's still just a few tens of loop iterations.

Re: You can beat the binary search

#130

Post by ted_dunning »

Seems like you can use the core intuition here of SIMD comparison of multiple elements on more than just the terminal scale.

The outline would be:

a) use a gather to grab multiple elements from 16 evenly spaced locations

b) compare these in parallel using a SIMD instruction

c) focus in on the correct block

d) if the block is small revert to linear search, else repeat the gather/compare cycle

Even though the gather instruction is reading from non-contiguous memory and reading more than you normally would need to with a binary sort, enabling a multiway compare and collapsing 4 levels of binary search should be a win on large tables.

You also may not be able to do a full 16-way comparison for all data types. Searching for float64 will limit you to 8 way comparisons (with AVX-512) but int32, float32 will allow 16 way comparisons.

Post reply on HN