4 ms·
I get that it's faster, but binary search is already so quick that it is almost free when you look at the big picture, even with large datasets. If standard lib
by w0mbat 3y ago
I get that it's faster, but binary search is already so quick that it is almost free when you look at the big picture, even with large datasets. If standard library implementors want to switch to this method behind the scenes then that's fine, but I'm not re-writing my apps.
- pvansandt 3y agoThis wouldn't go into a standard library since it's distribution dependent, but you might be interested to note a non-trivial (nor game changing) improvement to leveldb query time even with all the other work that it's doing besides search. Other examples would include things like pandas joins which use primitives like searching for lower bounds and partition points. I agree because for datasets that fit into memory, the scope for improvement is pretty limited. From a billion elements to 128 billion, that's only around 23% (37/30) more comparisons for binary search, and keeping that constant at the expense of more linear search isn't necessarily all that interesting for cheap comparisons. LogN grows so slowly that log-logN is frequently not that practically interesting.