Какой самый эффективный способ извлечь минимальное, максимальное и среднее значение из вектора

Question

Учитывая vector<T> vec{...}, каков наилучший способ извлечь его минимум, максимум и медиану, предполагая, что T является одним из числовых типов? Я знаю о std::nth_element, а также std::minmax_element, но они, похоже, выполняют избыточную работу, если их вызывают один за другим.

Лучшая идея, которую я до сих пор придумал, - просто вызывать std :: nth_element 3 раза один за другим. Но для этого все же нужны 3N сравнения, верно? Есть ли способ повторно использовать частичную сортировку, выполненную в предыдущих итерациях?

Answer 1

Используйте std::nth_element для разбиения, которое дает медиану, затем std::min_element в левой половине и std::max_element в правой.

Если вам нужно, чтобы это было быстрее, накатайте свою собственную версию, основанную на std::nth_element.

Answer 2

Другой вариант - указать пользовательское сравнение для std::nth_element, которое фиксирует минимальное и максимальное значения.Скорее всего, в конечном итоге будет выполняться гораздо больше сравнений и ветвлений, поэтому на некоторых конкретных аппаратных средствах это может быть медленнее, возможно, в зависимости от того, какая часть ваших данных кэшируется и т. Д., И, как всегда, для сравнения, если у вас есть причина для этогоно для непустого vector a метод выглядит следующим образом:

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;
    });

Сколько бы это ни стоило, на моем (~ 10yo i5-660) HTPC с использованием GCC 7.4 с 1 миллионом случайныхint с от 0 до 1000, nth_element занимает примерно на 36% больше времени при сравнении мин / макс, чем без.