diff options
| author | Kouhei Yanagita <yanagi@shakenbu.org> | 2023-09-16 12:10:09 +0900 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-09-16 12:10:09 +0900 |
| commit | 7d08dbd015a16c27f2d9c77751e80fa6efba2d7a (patch) | |
| tree | f40369e5c50acc88026c5221695443342fb5c49c /benchmark | |
| parent | 67dedf8cf634843488a477e53b9995b63e9aa291 (diff) | |
Optimize Range#bsearch for beginless/endless ranges
On Range#bsearch for endless ranges, we try positions at `begin + 2**i` (i = 0, 1, 2, ...)
to find a point that satisfies a given condition.
Subsequently, we perform binary searching with the interval `[begin, begin + 2**n]`.
However, the interval `[begin + 2**(n-1), begin + 2**n]` is sufficient for binary search
because `begin + 2**(n-1)` does not satisfy the condition.
The same applies to beginless ranges.
Diffstat (limited to 'benchmark')
| -rw-r--r-- | benchmark/range_bsearch.yml | 9 |
1 files changed, 9 insertions, 0 deletions
diff --git a/benchmark/range_bsearch.yml b/benchmark/range_bsearch.yml new file mode 100644 index 0000000000..9a7388ab04 --- /dev/null +++ b/benchmark/range_bsearch.yml @@ -0,0 +1,9 @@ +prelude: | + r = (1..) + +benchmark: + '10**1': r.bsearch { |x| x >= 10 } + '10**2': r.bsearch { |x| x >= 100 } + '10**3': r.bsearch { |x| x >= 1000 } + '10**4': r.bsearch { |x| x >= 10000 } + '10**5': r.bsearch { |x| x >= 100000 } |