4 ms·
A good alternative to binary search on modern hardware that should not be overlooked is indexed sequential search. https://www.geeksforgeeks.org/indexed-sequen
by jqpabc123 4y ago
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/ https://www.geeksforgeeks.org/indexed-sequential-search/
- utopcell 4y agoThis looks like a less efficient version of skip lists.
- jqpabc123 4y agoSkip 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.
- vlovich123 4y agoI would recommend using a larger value (eg 10) to limit the amount of space overhead. RocksDB uses a similar data structure to search through SSTables although they call it something else (can’t find the link where they describe it).