Fields
| hardware | None |
| os | None |
Parameters
Fields
| Name | Value |
|---|
Parameters
| Name | Value |
|---|---|
| git_commit |
commit a0662176a9b40462aafbb17cd8eb8cf6a65e940e Author: Iuri Chaer <iuri.chaer@gmail.com> Date: Thu Jul 18 21:11:24 2024 +0100 [libc++] Speed up set_intersection() by fast-forwarding over ranges of non-matching elements with one-sided binary search. (#75230) One-sided binary search, aka meta binary search, has been in the public domain for decades, and has the general advantage of being constant time in the best case, with the downside of executing at most 2*log(N) comparisons vs classic binary search's exact log(N). There are two scenarios in which it really shines: the first one is when operating over non-random-access iterators, because the classic algorithm requires knowing the container's size upfront, which adds N iterator increments to the complexity. The second one is when traversing the container in order, trying to fast-forward to the next value: in that case the classic algorithm requires at least O(N*log(N)) comparisons and, for non-random-access iterators, O(N^2) iterator increments, whereas the one-sided version will yield O(N) operations on both counts, with a best-case of O(log(N)) comparisons which is very common in practice. |