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

101–110 of 175 posts

Re: You can beat the binary search

#101

Post by xenadu02 »

wtallis wrote: post #93
kryptiskt wrote: post #92

Earlier quoted context omitted.

> It's not possible to learn anything about other elements when performing binary search, _except_ the only thing there is to learn: if the target is before or after the recently compared element. You have another piece of information, you don't only know if the element was before or after the compared element. You can also know the delta between what you looked at and what you're looking for. And you also have the d…

And you always start off knowing the total length of the array, and the width of the datatype. Actually deciding what to do with that information without incurring a bunch more cache misses in the process may be tricky.

Is the disconnect here that in many datasets there is some implicit distribution? For example if we are searching for english words we can assume that the number of words or sentences starting with "Q" or "Z" is very small while the ones starting with "T" are many. Or if the first three lookups in a binary search all start with "T" we are probably being asked to search just the "T" section of a dictionary.

Depending on the problem space such assumptions can prove right enough to be worth using despite sometimes being wrong. Of course if you've got the compute to throw at it (and the problem is large) take the Contact approach: why do one when you can do two in parallel for twice the price (cycles)?

Re: You can beat the binary search

#102

Post by Nevermark »

rixed wrote: post #84
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…

> 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 Also if you do not learn anything about the data while performing the binary search, no? Like, if you are constantly below the estimate, you could gess that the distribution is biases toward large values and adjust your guess based on thi…

For a list of sorted values with no other knowledge, the binary search is optimal. Provably, it is simple information theory on binary information.

You can do better if the list is stable by reusing information.

But gathering that information during searches is going to require great complexity to leverage, as searches are an irregular information gathering scheme.

So create RAM for speedup optimizations up front.

1) Create a table that maps the first 8 bits to upper and lower indexes in the list. Then binary search over the last 8 bits. That reduces the search time in half.

2) Go all the way, and create an array of 32,768 indexes, with all 1's for misses. Either way, search returns O(1).

Stable lists allow for sliding parametric trade offs between RAM-lookup vs. binary search. From full lookup, to full binary.

Re: You can beat the binary search

#103

Post by gobdovan »

thaumasiotes wrote: post #99
gobdovan wrote: post #85

Earlier quoted context omitted.

You're mixing two different objectives the paper presents. You can't beat binary search when the objective is to minimise the expected number of turns in a single player setting . However, in a two player setting, using the strategies presented in the paper, you will beat an adversary that uses binary search in more than 50% of the games played. Here's another visual demonstration: https://www.youtube.com/watch?v=zmv…

What do you think you're saying that I didn't already say? > in a two player setting, using the strategies presented in the paper, you will beat an adversary that uses binary search in more than 50% of the games played. This is technically true. But 50 percentage points of your "more than 50%" of games played are games where you exclusively use binary search. For the remainder, you're redistributing luck around betwe…

> But 50 percentage points of your "more than 50%" of games played are games where you exclusively use binary search

Although I think I get your point, saying 'You can't beat binary search in Guess Who' is misleading, considering you would probably describe yourself the optimal strategy as 'play binary search when ahead, when behind, don't'.

> Trying to get lucky means that you intentionally play badly in order to get more victories

That's quite an uncommon definition of good and bad.

Re: You can beat the binary search

#104

Post by [deleted] »

KalMann wrote: post #62
rao-v wrote: post #22

Earlier quoted context omitted.

This is simply not true - if you look at this article’s excellent benchmarking, linear search falls behind somewhere around 200-400 elements. In general I love this article, it took what I’ve often wondered about and did a perfect job exploring with useful ablation studies.

I don't really see how this implies the above commenter's statement is "simply not true".

[deleted]

Re: You can beat the binary search

#105

Post by krackers »

jstanley wrote: post #18
zamadatix wrote: post #14

Earlier quoted context omitted.

This ternary approach doesn't actually average 3/2 comparisons per level: - First third: 1 comparisons - Second third: 2 comparisons - Third third: 2 comparisons (1+2+2)/3 = 5/3 average comparisons. I think the gap starts here at assuming it's 50% of the time because it feels like "either you do 1 comparison or 2" but it's really 33% of the time because "there is 1/3 chance it's in the 1st comparison and 2/3 chance i…

Oh yeah!

If you sort of squint this idea does work in cases where the cost of comparison is dominated by the cost of going down a level. And that leads you to things like b-trees where fetching a page from disk is expensive but doing the comparisons within that page is basically free.

Re: You can beat the binary search

#106

Post by XCSme »

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 is closer to a[3] (diff of 1) than a[7] (diff of 7), so instead of going to the middle between mid and right, we could choose a new "mid" point that's closer to the desired value (maybe as a ratio of (d[right]-d[mid]).

so left=mid+1, right stays the same, but new mid is NOT half of left and right, it is (left+right)/2 + ratioOffset

Where ratioOffset makes the mid go closer to left or right, depending on d.

The idea is quite obvious, so I am pretty sure it already exists.

But what if we use SIMD, with it? So we know not only which block the number is in in, but also, which part of the block the number is likely in. Or is this what the article actually says?

Re: You can beat the binary search

#107

Post by charleslmunger »

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…

I've spent some brainpower on binary search and have not been able to beat this:

https://github.com/protocolbuffers/protobuf/blob/44025909eb7...

1. Check for dense list O(1) 2. Check upper bound 3. Constant trip count binary search

The constant trip count is great for the branch predictor, and the core loop is pretty tightly optimized for the target hardware, avoiding multiplies. Every attempt to get more clever made the loop worse and did not pay for itself. It's hard because it's an array-of-structs format with a size of 12, and mostly pretty small N.

Re: You can beat the binary search

#108

Post by VorpalWay »

leni536 wrote: post #96
VorpalWay wrote: post #87

Earlier quoted context omitted.

I would expect the standard library of various languages to provide an optimised implementation such as this. Then everyone downstream benefits, and benefits from future improvements when compiled for a newer version of the language / executed under a newer version of the runtime. You see this in rust, where they replaced the hash tables many years ago, the channel a couple of years ago, and most recently the sort im…

I wouldn't. This is very specialized to the type of the elements.

Some languages, such as C++, allow for specialisation via templates and compile time evabulation (constexpr). It would be possible to detect when the size of the data type matches one of the integer types, is a POD, is comparable via memcmp, etc to use SIMD optimised algorithms.

It is looking like C++ 26 will get compile time reflection, which would make things like this even more feasible.

Re: You can beat the binary search

#109

Post by travisjungroth »

molf wrote: post #88
rixed wrote: post #84

Earlier quoted context omitted.

> 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 Also if you do not learn anything about the data while performing the binary search, no? Like, if you are constantly below the estimate, you could gess that the distribution is biases toward large values and adjust your guess based on thi…

It's not possible to learn anything about other elements when performing binary search, _except_ the only thing there is to learn: if the target is before or after the recently compared element. If we would guess that there is a bias in the distribution based on recently seen elements, the guess is at least as likely to be wrong as it is to be right. And if we guess incorrectly, in the worst case, the algorithm degra…

> If we would guess that there is a bias in the distribution based on recently seen elements, the guess is at least as likely to be wrong as it is to be right.

This is true for abstract and random data. I don't think it's true for real world data.

For example, python's sort function "knows nothing" about the data you're passing in. But, it does look for some shortcuts and these end up saving time, on average.

Re: You can beat the binary search

#110

Post by aidenn0 »

Findecanor wrote: post #15
aidenn0 wrote: post #3

If you are storing 16-bit integers, wouldn't an 8kB bitmap be even faster?

The range is 1..4096, so 4096 bits = 512 byte bitmap would suffice. That is, if you're only ever going to test for membership in the set. If you need metadata then ... You could store that in a packed array and use a population count of the bit-vector before the lookup bit as index into it. For each word of bits, store the accumulated population count of the words before it to speed up lookup. Modern CPU's are memory…

The size is 1..4096, the range is implied to be the full 16-bit integer range.
Post reply on HN