Move Fast

수치 알고리즘 (Numeric Algorithm)

• iota 주어진 컨테이너를 특정 값에서 순서대로 증가하는 원소들로 채움.

// since C++11 until C++20
template< class ForwardIt, class T >
void iota( ForwardIt first, ForwardIt last, T value );

// since C++20
template< class ForwardIt, class T >
constexpr void iota( ForwardIt first, ForwardIt last, T value );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
using namespace std;

int main() {
    list<int> l(10);
    iota(l.begin(), l.end(), -4);

    vector<list<int>::iterator> v(l.size());
    iota(v.begin(), v.end(), l.begin());

    shuffle(v.begin(), v.end(), mt19937{random_device{}()});

    cout << "Contents of the list: ";
    for(auto n: l) cout << n << ' ';
    cout << endl;

    cout << "Contents of the list, shuffled: ";
    for(auto i: v) cout << *i << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Contents of the list: -4 -3 -2 -1 0 1 2 3 4 5
Contents of the list, shuffled: -4 -2 1 5 3 4 -3 0 2 -1
 */

• accumulate 주어진 값부터 범위 내 원소들을 누적시킴.

  • 비교자 함수를 이용해서 덧셈뿐만 아니라 뺄셈이나 문자열 연산 등을 할 수 있음.

// until C++20
template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );

template< class InputIt, class T, class BinaryOperation >
T accumulate( InputIt first, InputIt last, T init, BinaryOperation op );

// since C++20
template< class InputIt, class T >
constexpr T accumulate( InputIt first, InputIt last, T init );

template< class InputIt, class T, class BinaryOperation >
constexpr T accumulate( InputIt first, InputIt last, T init, BinaryOperation op );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <functional>
using namespace std;

int main() {
    vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int sum = accumulate(v.begin(), v.end(), 0);
    int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());

    auto dash_fold = [](string a, int b) {
                         return move(a) + '-' + to_string(b);
                     };

    // Start with first element
    string s = accumulate(next(v.begin()), v.end(), to_string(v[0]), dash_fold);

    // Right fold using reverse iterators
    // Start with last element
    string rs = accumulate(next(v.rbegin()), v.rend(), to_string(v.back()), dash_fold);

    cout << "sum: " << sum << endl
         << "product: " << product << endl
         << "dash-separated string: " << s << endl
         << "dash-separated string (right-folded): " << rs << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
sum: 55
product: 3628800
dash-separated string: 1-2-3-4-5-6-7-8-9-10
dash-separated string (right-folded): 10-9-8-7-6-5-4-3-2-1
 */

• inner_product 주어진 값(초기값)에 두 범위의 내적을 더한 결과를 반환.

// until C++20
template< class InputIt1, class InputIt2, class T >
T inner_product( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init );

template<class InputIt1, class InputIt2, class T,
         class BinaryOperation1, class BinaryOperation2> 
T inner_product( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init,
                 BinaryOperation1 op1, BinaryOperation2 op2 );

// since C++20
template< class InputIt1, class InputIt2, class T >
constexpr T inner_product( InputIt1 first1, InputIt1 last1,
                           InputIt2 first2, T init );

template<class InputIt1, class InputIt2, class T,
         class BinaryOperation1, class BinaryOperation2> 
constexpr T inner_product( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init,
                           BinaryOperation1 op1, BinaryOperation2 op2 );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <numeric>
#include <functional>
using namespace std;

int main() {
    vector<int> a{0, 1, 2, 3, 4};
    vector<int> b{5, 4, 2, 3, 1};

    int r1 = inner_product(a.begin(), a.end(), b.begin(), 0);
    cout << "Inner product of a and b: " << r1 << endl;

    int r2 = inner_product(a.begin(), a.end(), b.begin(), 0, plus<>(), equal_to<>());
    cout << "Number of pairwise matches between a and b: " <<  r2 << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++14
$ ./a.out
Inner product of a and b: 21
Number of pairwise matches between a and b: 2
 */

• adjacent_difference 범위 내 인접한 두 원소의 차이를 계산. 세번째 인자의 마지막 원소는 차이의 합.

// until C++20
template< class InputIt, class OutputIt >
OutputIt adjacent_difference( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt adjacent_difference( InputIt first, InputIt last, 
                              OutputIt d_first, BinaryOperation op );

// since C++20
template< class InputIt, class OutputIt >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last, 
                                        OutputIt d_first );

template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last, 
                                        OutputIt d_first, BinaryOperation op );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
                                ForwardIt1 first, ForwardIt1 last,
                                ForwardIt2 d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryOperation >
ForwardIt2 adjacent_difference( ExecutionPolicy&& policy,
                                ForwardIt1 first, ForwardIt1 last, 
                                ForwardIt2 d_first, BinaryOperation op );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <array>
#include <numeric>
#include <functional>
#include <iterator>
using namespace std;

int main() {
    // Default implementation - the difference b/w two adjacent items
    vector<int> v = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    adjacent_difference(v.begin(), v.end(), v.begin());

    for (auto n : v) cout << n << ' ';
    cout << endl;

    // Fibonacci
    array<int, 10> a {1};
    adjacent_difference(begin(a), prev(end(a)), next(begin(a)), plus<> {});
    copy(begin(a), end(a), ostream_iterator<int> {cout, " "});
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++14
$ ./a.out
2 2 2 2 2 2 2 2 2 2
1 1 2 3 5 8 13 21 34 55
 */

• partial_sum 범위의 부분합을 계산. ex) ret[3] = [0, 3] 범위의 모든 원소들의 합.

// until C++20
template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,
                      BinaryOperation op );

// since C++20
template< class InputIt, class OutputIt >
constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,
                                BinaryOperation op );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <numeric>
#include <iterator>
#include <functional>
using namespace std;

int main() {
    vector<int> v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; // or vector<int>v(10, 2);

    cout << "The first 10 even numbers are: ";
    partial_sum(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    partial_sum(v.begin(), v.end(), v.begin(), multiplies<int>());
    cout << "The first 10 powers of 2 are: ";
    for (auto n : v) cout << n << " ";
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20
The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024
 */

• reduce 주어진 값(초기값)에다가 범위 내 원소들의 합을 더한 결과를 반환.

  • accumulate과 유사하나, 실행 정책(Execution Policy)가 추가되어 병렬 수행이 가능하다는 점에서 차이가 있음.

  • 실행 정책은 C++17 부터 추가된 것으로, 첫번째 인자에 std::execution::par 또는 std::execution::par_unseq 를 주면 쓰레드로 병렬 수행함.

  • 두 정책의 차이는 par은 중간에 다른 쓰레드가 개입되지 않음을 보장하며 데드락이 걸릴 위험이 없음. 반대로 par_unseq는 중간에 CPU가 다른 쓰레드를 실행할 수 있음을 의미.

  • 디폴트는 std::execution::seq 이며, 순차 실행을 의미.

  • 자세한 설명은 여기 참고.

  • 단, intell 에서는 실행 정책을 제공하지 않음.

  • intell 에서는 Threading Building Block (TBB) 라고 병렬 처리를 위한 C++ 라이브러리를 별도로 제공하고 있음.

  • 2018년도부터 TBB 내에 별도의 병렬화된 STL 함수(Parallel STL)들도 제공하는 것으로 확인됨.

// since C++17 until C++20
template<class InputIt>
typename std::iterator_traits<InputIt>::value_type reduce(
    InputIt first, InputIt last);

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

// since C++20
template<class InputIt>
constexpr typename std::iterator_traits<InputIt>::value_type reduce(
    InputIt first, InputIt last);

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

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

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

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

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

// only C++17
template<class InputIt, class T, class BinaryOp>
T reduce(InputIt first, InputIt last, T init, BinaryOp binary_op);

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <numeric>
#include <chrono>
#include <execution>
using namespace std;

int main() {
    const vector<double> v(10'000'007, 0.5);

    {
        const auto t1 = chrono::high_resolution_clock::now();
        const double result = accumulate(v.cbegin(), v.cend(), 0.0);
        const auto t2 = chrono::high_resolution_clock::now();
        const chrono::duration<double, milli> ms = t2 - t1;
        cout << fixed << "accumulate result " << result;
        cout << " took " << ms.count() << " ms" << endl;
    }

    {
        const auto t1 = chrono::high_resolution_clock::now();
        const double result = reduce(execution::par, v.cbegin(), v.cend());
        const auto t2 = chrono::high_resolution_clock::now();
        const chrono::duration<double, milli> ms = t2 - t1;
        cout << "reduce result " << result << " took ";
        cout << ms.count() << " ms" << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
std::accumulate result 5000003.50000 took 12.7365 ms
std::reduce result 5000003.50000 took 5.06423 ms
 */

• exclusive_scan 각 원소는 자신을 제외하고 앞의 원소까지만 누적 연산. ex) ret[3] = [0, 2] 범위에서만 연산을 수행한 결과. (C++17)

  • 초기값이 있으면 그 값을 포함해서 연산함. 즉, ret[0] != 0 이고 ret[0] = 초기값.

• inclusive_scan 각 원소는 자신을 포함해서 누적 연산. ex) ret[3] = [0, 3] 범위에서만 연산을 수행한 결과. (C++17)

  • 초기값이 있으면 그 값을 포함해서 연산함. 즉, ret[0] = 첫번째 원소 + 초기값.

// since C++17 until C++20
template< class InputIt, class OutputIt, class T >
OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, T init );

template< class InputIt, class OutputIt, 
          class T, class BinaryOperation >
OutputIt exclusive_scan( InputIt first, InputIt last,
                         OutputIt d_first, T init, BinaryOperation binary_op );

// since C++20
template< class InputIt, class OutputIt, class T >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last,
                                   OutputIt d_first, T init );

template< class InputIt, class OutputIt, 
          class T, class BinaryOperation >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                                   T init, BinaryOperation binary_op );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
                           ForwardIt1 first, ForwardIt1 last,
                           ForwardIt2 d_first, T init);

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class T, class BinaryOperation >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
                           ForwardIt1 first, ForwardIt1 last,
                           ForwardIt2 d_first, T init, BinaryOperation binary_op );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <iterator>
#include <functional>
#include <numeric>
using namespace std;

int main() {
    vector data = {3, 1, 4, 1, 5, 9, 2, 6};

    cout << "exclusive sum: ";
    exclusive_scan(data.begin(), data.end(),
                   ostream_iterator<int>(cout, " "), 0);

    cout << endl << "inclusive sum: ";
    inclusive_scan(data.begin(), data.end(),
                   ostream_iterator<int>(cout, " "));

    cout << endl << endl << "exclusive product: ";
    exclusive_scan(data.begin(), data.end(),
                   ostream_iterator<int>(cout, " "), 1,
                   multiplies<>{});

    cout << endl << "inclusive product: ";
    inclusive_scan(data.begin(), data.end(),
                   ostream_iterator<int>(cout, " "),
                   multiplies<>{});
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
exclusive sum: 0 3 4 8 9 14 23 25
inclusive sum: 3 4 8 9 14 23 25 31

exclusive product: 1 3 3 12 12 60 540 1080
inclusive product: 3 3 12 12 60 540 1080 6480
 */

• transform_reduce 각 원소들을 변환시킨 후, 축약한 결과를 반환. (C++17 부터 지원)

  • 초기값이 있으면, 초기값을 더해서 최종 결과를 반환.

  • 주어진 범위가 두 개일 경우, inner_product 함수와 동일하게 동작함. 차이점은 transform_reduce 에서는 실행 정책을 인자로 줄 수 있음. reduce 함수와 마찬가지로 실행 정책이 intel CPU 에서는 지원하지 않음.

  • 주어진 범위가 하나일 경우, UnaryOp unary_op 에 넘긴 함수로 각 원소를 변환시킨 후, BinaryOp binary_op 에 넘긴 함수로 모든 원소들을 축약함.

// since C++17 until C++20
template<class InputIt1, class InputIt2, class T>
T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init);

template <class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2>
T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                   T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);

template<class InputIt, class T, class BinaryOp, class UnaryOp>
T transform_reduce(InputIt first, InputIt last,
                   T init, BinaryOp binop, UnaryOp unary_op);

// since C++20
template<class InputIt1, class InputIt2, class T>
constexpr T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init);

template <class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2>
constexpr T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                             T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);

template<class InputIt, class T, class BinaryOp, class UnaryOp>
constexpr T transform_reduce(InputIt first, InputIt last,
                             T init, BinaryOp binop, UnaryOp unary_op);

// since C++17
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T>
T transform_reduce(ExecutionPolicy&& policy,
                   ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init);

template<class ExecutionPolicy,
         class ForwardIt1, class ForwardIt2, class T, class BinaryOp1, class BinaryOp2>
T transform_reduce(ExecutionPolicy&& policy,
                   ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2,
                   T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);

template<class ExecutionPolicy,class ForwardIt, class T, class BinaryOp, class UnaryOp>
T transform_reduce(ExecutionPolicy&& policy,
                   ForwardIt first, ForwardIt last,
                   T init, BinaryOp binary_op, UnaryOp unary_op);

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <numeric>
#include <functional>
#include <execution>
using namespace std;

int main() {
    vector<double> xvalues(10007, 1.0), yvalues(10007, 1.0);

    double result = transform_reduce(
        execution::par,
        xvalues.begin(), xvalues.end(),
        yvalues.begin(), 0.0
    );
    cout << result << endl;

    result = transform_reduce(
        execution::par,
        xvalues.begin(), xvalues.end(), 1.0,
        plus<>(), [](double x) { return x * 2.0; }
    );
    cout << result << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
10007
20015 <--- 1.0 + 2.0 * 10007
 */

• transform_exclusive_scan 각 원소들을 주어진 함수로 변환시킨 후, exclusive_scan을 적용. (C++17부터 지원)

• transform_inclusive_scan 각 원소들을 주어진 함수로 변환시킨 후, inclusive_scan을 적용. (C++17부터 지원)

// since C++17 until C++20
template< class InputIt, class OutputIt, class T, 
          class BinaryOperation, class UnaryOperation>
OutputIt transform_exclusive_scan( InputIt first, InputIt last,
                                   OutputIt d_first, T init,
                                   BinaryOperation binary_op,
                                   UnaryOperation unary_op);

template< class InputIt, class OutputIt,
          class BinaryOperation, class UnaryOperation >
OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                                   BinaryOperation binary_op,
                                   UnaryOperation unary_op );

template< class InputIt, class OutputIt,
          class BinaryOperation, class UnaryOperation, class T >
OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                                   BinaryOperation binary_op, UnaryOperation unary_op,
                                   T init );

// since C++20
template< class InputIt, class OutputIt, class T, 
          class BinaryOperation, class UnaryOperation>
constexpr OutputIt transform_exclusive_scan( InputIt first, InputIt last,
                                             OutputIt d_first,
                                             T init, BinaryOperation binary_op,
                                             UnaryOperation unary_op);

template< class InputIt, class OutputIt, class BinaryOperation, class UnaryOperation >
constexpr OutputIt transform_inclusive_scan( InputIt first, InputIt last,
                                             OutputIt d_first,
                                             BinaryOperation binary_op,
                                             UnaryOperation unary_op );

template< class InputIt, class OutputIt,
          class BinaryOperation, class UnaryOperation, class T >
constexpr OutputIt transform_inclusive_scan( InputIt first, InputIt last,
                                             OutputIt d_first,
                                             BinaryOperation binary_op,
                                             UnaryOperation unary_op,
                                             T init );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class T, class BinaryOperation, class UnaryOperation >
ForwardIt2 transform_exclusive_scan( ExecutionPolicy&& policy,
                                     ForwardIt1 first, ForwardIt1 last,
                                     ForwardIt2 d_first, T init,
                                     BinaryOperation binary_op,
                                     UnaryOperation unary_op );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryOperation, class UnaryOperation >
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy,
                                     ForwardIt1 first, ForwardIt1 last,
                                     ForwardIt2 d_first,
                                     BinaryOperation binary_op,
                                     UnaryOperation unary_op );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryOperation, class UnaryOperation, class T >
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy,
                                     ForwardIt1 first, ForwardIt1 last,
                                     ForwardIt2 d_first,
                                     BinaryOperation binary_op,
                                     UnaryOperation unary_op,
                                     T init );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <iterator>
#include <functional>
#include <numeric>
using namespace std;

int main() {
    vector data {3, 1, 4, 1, 5, 9, 2, 6};

    auto times_10 = [](int x) { return x * 10; };

    cout << "10 times exclusive sum: ";
    transform_exclusive_scan(data.begin(), data.end(),
                             ostream_iterator<int>(cout, " "), 0,
                             plus<int>{}, times_10);
    cout << endl;

    cout << "10 times inclusive sum: ";
    transform_inclusive_scan(data.begin(), data.end(),
                             ostream_iterator<int>(cout, " "),
                             plus<int>{}, times_10);
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
10 times exclusive sum: 0 30 40 80 90 140 230 250
10 times inclusive sum: 30 40 80 90 140 230 250 310
 */