Binary search with looking nearby values
I am trying to find, if someone implemented binary search in following way -
Let suppose we have array of some elements, placed in contiguous memory.
Then when you compare middle element, the next few elements should be already in the the CPU cache. Comparing should be already free?
Yet I can not find anyone who doing this.
If no one do that, what could be the reason?
Classic binary search can be thought of as defining a binary tree structure on the elements. For example, if your array has 15 elements numbered 1 through 15, you would start out by looking at the middle element "8", and from there go either left or right to element "4" or "12":
(from Brodal et al, "Cache oblivious search trees via binary trees of small height", SODA'02, PDF preprint link)
What you are proposing is essentially adding a few more elements into each node, so that the "8" element would also contain some adjacent elements e.g. "9", "10", "11". I don't think this has been studied extensively before, but there is another very related idea that has been studied, namely going from a binary tree (with two children on each node) to a B-ary tree ("B-tree", with B children on each node). This is where you have multiple elements in a node that split up the resulting data into many different ranges.
By comparing a search key to the B-1 different elements in a node, you can determine which of the B children to recurse into.
It's possible to rearrange the elements in an array so that this search structure can be realized without using pointers and multiple memory allocations, so that it becomes just as space-efficient as doing binary search in a regular sorted array, but with fewer "jumps" when doing the search. In a regular sorted array, binary search does roughly log_2(N) jumps, whereas search in a B-tree does only log_2(N) / log_2(B) = log_B(N) jumps, which is a factor log_2(B) fewer!
Sergey Slotin has written a blog post with a complete example of how to implement a static B-tree that is stored implicitly in an array: https://algorithmica.org/en/b-tree
- Convert the greatest binary number (by number of binary digits) to decimal
- Performance Advantages to Iterators?
- Fastest way to determine if record exists
- Why can't an "active" garbage collector work like Rust's borrow checker?
- Time Limit Exceed on a UVA problem using Python, is this code that inefficient?
- marshal dumps faster, cPickle loads faster
- Left side of LIKE expression must evaluate to a varchar (actual: varbinary). What's an alternative to converting from varbinary to varchar?
- Fastest way to strip trailing zeroes from an unsigned int
- Is there any benefit of using a dictionary comprehension if an equivalent dict(zip(a, b)) is possible?
- Efficient solution for the same-fringe problem for binary trees
- Find out which thread/process is consuming CPU
- Virtual Threads and Spring WebFlux
- Fastest way to search for a row in a large Google Sheet using/in Google Apps Script
- Numba njit making function call involving long expressions extremely slow
- JPA + spring boot - findBy <field> extremely slow when Database is huge ( 20M lines Table )
- Splash Screen Recreating After Calling AppCompatDelegate.setDefaultNightMode
- Improve performance of onEdit simple trigger
- Django is too slow when processing exception
- Which is the fastest way to tell if a Channel<T> is empty?
- How to get observable gauge value using DiagnosticsClient?
- Why did SQL Server suddenly decide to use such a terrible execution plan?
- "Preprocessing" a Python function, to avoid excess evaluation of conditional logic
- Most efficient way to concatenate strings in JavaScript?
- Vue3 v-for + component => triggers lots of renders
- C faster way to check if a directory exists
- How to improve the code to return the unpaired element
- Comparison of two approaches of exponentiating elements of a matrix
- How can I optimize the performance of a React application that's rendering a large list of items?
- Computationally efficient alternative to row-wise apply on a list with same-length vectors
- Maximizing Haskell loop performance with GHC