[HN Gopher] Eytzinger Binary Search
___________________________________________________________________
Eytzinger Binary Search
Author : mikecarlton
Score : 100 points
Date : 2023-04-28 09:00 UTC (1 days ago)
(HTM) web link (algorithmica.org)
(TXT) w3m dump (algorithmica.org)
| sereja wrote:
| Author here. There is a newer and significantly expanded version
| of the article: https://en.algorithmica.org/hpc/data-
| structures/binary-searc...
| WinLychee wrote:
| Thanks for organizing this information into one place! It's
| super interesting and really relevant to high performance
| software. A lot of this material is scattered between
| conference talks, obscure forums, and hacks in closed-source
| software.
| snakey wrote:
| Thank you for your incredible work! I have been reading
| Algorithms for Modern Hardware as part of my after-work study
| and I have found it invaluable--I reference it daily.
|
| I can't wait for Part II :)
| einpoklum wrote:
| So, in your implementation, you always reduce the search range
| to n - n/2 to avoid branches. Why can it not be always n/2 -
| seeing as you've just examined and ruled out your middle
| element? i.e. seeing as how n/2 >= (n-1)-(n-1)/2 ?
| sereja wrote:
| This is a tricky part. The middle element is still part of
| the search range if we go "left" (>=). After we compare
| against it, the search range length becomes either floor(n/2)
| or ceil(n/2), in the latter case including the middle element
| (we will never compare against it again, but it still needs
| to be the first element of the search range).
|
| To avoid additional checks and branching, we can just always
| make the next search range length ceil(n/2), effectively
| adding that middle element to the search range in case we go
| "right" (<).
| ahefner wrote:
| Thank you for your article. I had difficulty understanding the
| "Binary search implementation" section of the original article
| for various reasons, despite knowing what binary search is,
| being familiar with the 2k/2k+1 encoding (from binary heaps),
| and generally thinking I understood what you're trying to do. I
| wondered if was the only one struggling with this.
|
| Among the difficulties:
|
| "restore the index of the resulting element" - it's not clear
| what this means until after reading the remainder of the
| section (many times, in my case, due to other difficulties)
|
| "We compare it against 4, 2, and 5..." - An error? You compared
| 'x' against 4, 2, and 3, or b[1], b[2], and b[5], but never
| against 5 - this would be to the right of 4 and a binary search
| would not visit it.
|
| "..and so we just need to find the number of trailing ones in
| the binary notation and right-shift by exactly that amount." -
| You need to shift right that amount plus one. In your example
| for search(4), after the loop and prior to shifting k=11. In
| binary this is 1011, which has two trailing ones, but must be
| shifted right by 3 bits (not 2) to yield k=1 such that b[k] ==
| 4.
|
| "eytzinger: 4 2 5 1 6 3 7 8" - it took me surprisingly long to
| realize this was describing the permutation of values of a[] to
| indexes of b[] rather than listing the contents of b[] itself
| with the zero element elided (which coincidentally are the same
| for the first two elements, despite otherwise not making any
| sense). Perhaps brevity forces this sort of thing.
|
| The presence of 8 in the example's array appears to be an
| error. At index 8 it would be the left child of 1, which it
| can't be. Letting n=7 and a={1,2,3,4,5,6,7} agrees with your
| example, whereas including 8 and setting n=8 rearranges things
| and forces the root to be 5 rather than 4.
| toolslive wrote:
| very nice. small remark: iirc, there's a risk of overflow if you
| naively do `m = (l + r) /2`
| utopcell wrote:
| There exists a 2022 CPPcon presentation covering efficient binary
| searching, which includes Eytzinger layouts [1].
|
| [1]
| https://github.com/CppCon/CppCon2022/blob/main/Presentations...
| sereja wrote:
| Also available on YouTube:
| https://www.youtube.com/watch?v=1RIPMQQRBWk
| utopcell wrote:
| Eytzinger layouts are great, but they require more space if one
| is not allowed to touch the original sorted array. Then again, if
| you are allowed to use extra space, binary search can be
| implemented in worst-case constant time for integer arrays.
| einpoklum wrote:
| tl;dr:
|
| 1. Avoid branching by always reducing the search range from n to
| n-n/2 (never n/2).
|
| 2. Preprocess the input (a sorted array) to Eytzinger order:
| Middle element, then first and third quartile elements etc. Now,
| if your search checks an element at position k, it will next want
| to look at either position 2k or 2k+1.
|
| 3. Some minor tweaks like aligned storage and rounding up size to
| a power of 2.
| jqpabc123 wrote:
| A good alternative to binary search on modern hardware that
| should not be overlooked is indexed sequential search.
|
| https://www.geeksforgeeks.org/indexed-sequential-search/
| utopcell wrote:
| This looks like a less efficient version of skip lists.
| jqpabc123 wrote:
| Skip lists are more complex, require more pointer storage and
| are really intended for more dynamic data.
|
| I would label this more of a hybrid hash/lookup table --- but
| without any wasted storage space.
|
| The key observation here is that on modern hardware, a
| simple, linear, fully cache based search of 20-30 elements is
| often faster than a binary search. If a pre-computed index
| can easily and efficiently narrow the average linear search
| range down to this level, it is likely to be faster.
|
| But re-arranging into Eytzinger order is sorta equivalent to
| building an index so as always, apply your own judgment.
| kalimanzaro wrote:
| Relevant recent HN thread:
| https://news.ycombinator.com/item?id=35737862
|
| (Beautiful branchless binary search)
___________________________________________________________________
(page generated 2023-04-29 23:03 UTC)