←back to thread

386 points ingve | 1 comments | | HN request time: 0s | source
Show context
2102922286 ◴[] No.35738100[source]
A cool related algorithm is https://algorithmica.org/en/eytzinger

In addition to being branchless, it also has better cache properties than a standard binary search tree.

If you're doing a binary search in an array, you start in the middle, and then jump all the way to the midway point of one half, and so on. As a result, there's a lot of distance between each read that you do in the array. Thus, each read is putting extra strain on the cache (or the reads won't be cached).

The CPU cache performs much better if the values you want to read are close to each other. Enter the Eytzinger Binary Search. The idea is that, if you're always going to be accessing the root of the tree, and then one of its two children--you should just put those children physically close to the root, so they'll all be on the same cache line!

replies(8): >>35738287 #>>35738451 #>>35738561 #>>35739155 #>>35740049 #>>35740397 #>>35740690 #>>35744101 #
1. utopcell ◴[] No.35740690[source]
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, lower_bound operations (aka binary searching) can be implemented in worst-case constant time for integer arrays.