diff options
| author | Kouhei Yanagita <[email protected]> | 2023-09-16 12:10:09 +0900 |
|---|---|---|
| committer | <[email protected]> | 2023-09-16 12:10:09 +0900 |
| commit | 7d08dbd015a16c27f2d9c77751e80fa6efba2d7a () | |
| tree | f40369e5c50acc88026c5221695443342fb5c49c /range.c | |
| 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.
| -rw-r--r-- | range.c | 2 |
1 files changed, 2 insertions, 0 deletions
@@ -758,6 +758,7 @@ range_bsearch(VALUE range) return bsearch_integer_range(beg, mid, 0); } diff = rb_funcall(diff, '*', 1, LONG2FIX(2)); } } else if (NIL_P(beg) && is_integer_p(end)) { @@ -770,6 +771,7 @@ range_bsearch(VALUE range) return bsearch_integer_range(mid, end, 0); } diff = rb_funcall(diff, '*', 1, LONG2FIX(2)); } } else { |