CODEWITHSUNDEEP
c++algorithmmedian
user1709708
user1709708

Reputation: 1577

What's the most efficient way to extract min, max & median from a vector

Given a vector<T> vec{...} what's the best way to extract its minimum, maximum and median assuming T is one of the numeric types? I know of std::nth_element as well as std::minmax_element but they seem to do redundant work if called one after another.

The best idea I came up with so far is to just call std::nth_element 3 times one after another. But this still needs 3N comparisons, right? Is there any way to reuse the partial sorting done in previous iterations?

Upvotes: 13

Views: 1579

Answers (2)

Tony Delroy
Tony Delroy

Reputation: 106116

Another option is to specify a custom comparison for std::nth_element, which captures the min and max. It will likely end up doing a lot more comparisons and branches, so this might be slower on some specific hardware, possibly depending on how much of your data is cached etc., so - as always - benchmark if you've reason to care, but for a non-empty vector a the technique looks like this:

int min = a[0], max = a[0];
std::nth_element(a.begin(), a.begin() + n, a.end(),
    [&](int lhs, int rhs) {
        min = std::min(min, std::min(lhs, rhs));
        max = std::max(max, std::max(lhs, rhs));
        return lhs < rhs;
    });

For what little it's worth, on my (~10yo i5-660) HTPC using GCC 7.4 with 1 million random ints between 0 and 1000, nth_element takes about 36% longer with the min/max comparison than without.

Upvotes: 3

Bathsheba
Bathsheba

Reputation: 234715

Use std::nth_element to partition which yields the median, then std::min_element in the left half and std::max_element in the right one.

If you need it to be faster than that then roll your own version based on std::nth_element.

Upvotes: 12

Related Questions