phobos
phobos copied to clipboard
[std.algorithm.searching] Add extrema to compute min and max
Performs < 3n/2
comparisons, unlike the naive < 2n
.
Implemented for an input range.
TODO add alias map = a => a
parameter, once design is confirmed OK.
Thanks for your pull request and interest in making D better, @ntrel! We are looking forward to reviewing it, and you should be hearing from a maintainer soon. Please verify that your PR follows this checklist:
- My PR is fully covered with tests (you can see the coverage diff by visiting the details link of the codecov check)
- My PR is as minimal as possible (smaller, focused PRs are easier to review than big ones)
- I have provided a detailed rationale explaining my changes
- New or modified functions have Ddoc comments (with
Params:
andReturns:
)
Please see CONTRIBUTING.md for more information.
If you have addressed all reviews or aren't sure how to proceed, don't hesitate to ping us with a simple comment.
Bugzilla references
Your PR doesn't reference any Bugzilla issue.
If your PR contains non-trivial changes, please reference a Bugzilla issue or create a manual changelog.
Testing this PR locally
If you don't have a local development environment setup, you can use Digger to test this PR:
dub run digger -- build "master + phobos#8727"
@atilaneves This is a new public function
unlike the naive < 2n.
Unlike the naive version done where?
Unlike the naive version done where?
https://dlang.org/phobos/std_algorithm_iteration.html#fold
// Compute minimum and maximum at the same time writeln(arr.fold!(min, max)); // tuple(1, 5)
Unlike the naive version done where?
https://dlang.org/phobos/std_algorithm_iteration.html#fold
// Compute minimum and maximum at the same time writeln(arr.fold!(min, max)); // tuple(1, 5)
Do you mean min
and max
? I don't understand what fold
has to do with this.
@atilaneves min
and max
take pairs of elements, not ranges. The versions that take ranges are called minElement
and maxElement
.
@ntrel @atilaneves how do we move further with this?
I still don't know what this is a replacement for.
When a user wants to compute the min and max value of a range with Phobos, currently they need to call minElement
and maxElement
separately, resulting in 2n
comparisons. By using the new extrema
function, they're only doing 1.5n
comparisons. It's somewhat similar to the sincos function being more efficient than separate sin
and cos
calls.