std::reduce

template< class InputIt >
typename std::iterator_traits<InputIt>::value_type
    reduce( InputIt first, InputIt last );

template< class ExecutionPolicy, class ForwardIt >
typename std::iterator_traits<ForwardIt>::value_type
    reduce( ExecutionPolicy&& policy,
            ForwardIt first, ForwardIt last );

template< class InputIt, class T >
T reduce( InputIt first, InputIt last, T init );

template< class ExecutionPolicy, class ForwardIt, class T >
T reduce( ExecutionPolicy&& policy,
          ForwardIt first, ForwardIt last, T init );

template< class InputIt, class T, class BinaryOp >
T reduce( InputIt first, InputIt last, T init, BinaryOp op );

template< class ExecutionPolicy,
          class ForwardIt, class T, class BinaryOp >
T reduce( ExecutionPolicy&& policy,
          ForwardIt first, ForwardIt last, T init, BinaryOp op );

주어진 binary_op 가 실제 이진 연산일 때:

• 결과는 binary_op 가 결합법칙을 따르지 않거나 교환법칙을 따르지 않으면 (예: 부동소수점 덧셈) 비결정적입니다.

• 다음 값 중 T로 변환할 수 없는 값이 있으면 프로그램의 형식이 잘못되었습니다:

• binary_op(init, *first)
• binary_op(*first, init)
• binary_op(init, init)
• binary_op(*first, *first)

• 다음 조건 중 하나라도 만족하면 동작은 정의되지 않습니다:

• T 가 MoveConstructible이 아닙니다.
• binary_op 가 [first, last)의 요소를 수정합니다.
• binary_op 가 [first, last]의 반복자나 하위 범위를 무효화합니다.

매개변수

반환값

요소 그룹의 일반화된 합 은 이진 연산 binary_op 에 대해 다음과 같이 정의됩니다:

• 그룹에 요소가 하나만 있는 경우, 합계는 해당 요소의 값입니다.
• 그렇지 않은 경우, 다음 작업을 순서대로 수행합니다:

1. 그룹에서 임의의 두 요소 elem1 과 elem2 를 취합니다.
2. binary_op ( elem1, elem2 ) 을 계산하고 결과를 그룹에 다시 넣습니다.
3. 그룹에 요소가 하나만 남을 때까지 1단계와 2단계를 반복합니다.

복잡도

주어진 \(\scriptsize N\) N 이 std:: distance ( first, last ) 인 경우:

예외

ExecutionPolicy 라는 템플릿 매개변수를 사용하는 오버로드는 다음과 같이 오류를 보고합니다:

• 알고리즘의 일부로 호출된 함수 실행 중 예외가 발생하고 ExecutionPolicy 가 표준 정책 중 하나인 경우, std::terminate 가 호출됩니다. 다른 ExecutionPolicy 의 경우 동작은 구현에 따라 정의됩니다.
• 알고리즘이 메모리 할당에 실패하는 경우, std::bad_alloc 이 throw됩니다.

참고 사항

std::reduce 는 범위의 요소들이 임의의 순서로 그룹화되고 재배열될 수 있다는 점을 제외하면 std::accumulate 와 유사하게 동작합니다.

예제

#if PARALLEL
#include <execution>
#define SEQ std::execution::seq,
#define PAR std::execution::par,
#else
#define SEQ
#define PAR
#endif
#include <chrono>
#include <iomanip>
#include <iostream>
#include <locale>
#include <numeric>
#include <utility>
#include <vector>
int main()
{
    std::cout.imbue(std::locale("en_US.UTF-8"));
    std::cout << std::fixed << std::setprecision(1);
    auto eval = [](auto fun)
    {
        const auto t1 = std::chrono::high_resolution_clock::now();
        const auto [name, result] = fun();
        const auto t2 = std::chrono::high_resolution_clock::now();
        const std::chrono::duration<double, std::milli> ms = t2 - t1;
        std::cout << std::setw(28) << std::left << name << "합계: "
                  << result << '\t' << "시간: " << ms.count() << " ms\n";
    };
    {
        const std::vector<double> v(100'000'007, 0.1);
        eval([&v]{ return std::pair{"std::accumulate (double)",
            std::accumulate(v.cbegin(), v.cend(), 0.0)}; });
        eval([&v]{ return std::pair{"std::reduce (seq, double)",
            std::reduce(SEQ v.cbegin(), v.cend())}; });
        eval([&v]{ return std::pair{"std::reduce (par, double)",
            std::reduce(PAR v.cbegin(), v.cend())}; });
    }
    {
        const std::vector<long> v(100'000'007, 1);
        eval([&v]{ return std::pair{"std::accumulate (long)",
            std::accumulate(v.cbegin(), v.cend(), 0l)}; });
        eval([&v]{ return std::pair{"std::reduce (seq, long)",
            std::reduce(SEQ v.cbegin(), v.cend())}; });
        eval([&v]{ return std::pair{"std::reduce (par, long)",
            std::reduce(PAR v.cbegin(), v.cend())}; });
    }
}

// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3; ./a.out
std::accumulate (double)    합계: 10,000,000.7	시간: 356.9 ms
std::reduce (seq, double)   합계: 10,000,000.7	시간: 140.1 ms
std::reduce (par, double)   합계: 10,000,000.7	시간: 140.1 ms
std::accumulate (long)      합계: 100,000,007	시간: 46.0 ms
std::reduce (seq, long)     합계: 100,000,007	시간: 67.3 ms
std::reduce (par, long)     합계: 100,000,007	시간: 63.3 ms
// POSIX: g++ -std=c++23 ./example.cpp -ltbb -O3 -DPARALLEL; ./a.out
std::accumulate (double)    합계: 10,000,000.7	시간: 353.4 ms
std::reduce (seq, double)   합계: 10,000,000.7	시간: 140.7 ms
std::reduce (par, double)   합계: 10,000,000.7	시간: 24.7 ms
std::accumulate (long)      합계: 100,000,007	시간: 42.4 ms
std::reduce (seq, long)     합계: 100,000,007	시간: 52.0 ms
std::reduce (par, long)     합계: 100,000,007	시간: 23.1 ms

같이 보기