Transform-and-Accumulate

Question

Кто-нибудь написал алгоритм, совместимый с C++ STL, который объединяет std::transform и std::accumulate в однопроходный алгоритм, поддерживающий как унарный, так и двоичный и, возможно, даже (n-арный!) Вариант, скажем std::transformed_accumulate? Я хочу это, потому что я нашел этот шаблон многократно используемым, например, для линейной алгебры, например, в (l1-) вычислениях. L1-norm вычисляет сумму абсолютных значений элементов.

Answer 1

... Я уверен, что вы можете сделать это, вложив ваше преобразование в бинарный предикат, преобразуйте элемент и скопируйте его после преобразования.

struct times2accumulator { 
    int operator()(int oldvalue, int newvalue) const { 
     return oldvalue + 2*newvalue; 
    } 
}; 
int r = std::accumulate(v.begin(), v.end(), 2, times2accumulator()); 

Этот функтор будет эквивалентно:

struct times2 { 
    int operator()(int x) { 
     return 2*x; 
    } 
}; 
std::vector<int> tmp; tmp.reserve(v.size()); 
std::transform(v.begin(), v.end(), std::back_inserter(tmp), times2); 
int r = std::accumulate(tmp.begin(), tmp.end(), 0); 

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

template <typename Transform> 
struct transform_accumulator_t { 
    Transform t; 
    transform_accumulator_t(Transform t) : t(t) {} 
    int operator()(int oldvalue, int newvalue) const { 
     return oldvalue + t(newvalue); 
    } 
}; 
// syntactic sugar: 
template <typename T> 
transform_accumulator_t<T> transform_accumulator(T t) { 
    return transform_accumulator_t<T>(t); 
} 
int r = std::accumulate(v.begin(), v.end(), 0, transform_accumulator(times2)); 

А вы могли бы также обобщайте тип в контейнере ... или даже создайте более общий преобразовательный_аккулятор, который берет как аккумулятор, так и функторы преобразования и применяет их по порядку. Фактическая реализация осталась в качестве упражнения для читателя.

Answer 2

Хотя это может не соответствовать оригинальному намерению, std::inner_product - это в основном ваша двоичная версия. Вы передаёте начальное значение, два диапазона, и два функторы, и применяет их как:

T acc = initial_value; 
while (begin1 != end1) { 
    acc = binary_op1(acc, binary_op2(begin1, begin2); 
    ++begin1; 
    ++begin2; 
return acc; 

Таким образом, для L1 вы могли бы сделать что-то на этом общем порядке:

norm = std::inner_product(input1.begin(), input1.end(), 
          input2.begin(), input2.end(), 
          std::plus<int>(), std::abs); 

только это не совсем работает - прямо сейчас, он пытается пройти std::abs, где вам действительно нужна двоичная функция, которая объединяет два входа, но я не уверен, как эти два входа действительно должны быть объединены.

std::partial_sum довольно близко к вашей унарной версии, за исключением того, что наряду с накоплением результата он (пытается) выписывает каждый промежуточный результат, а не только конечный результат. Для того, чтобы просто получить конечный результат, вы должны написать (и передать экземпляр) своего рода ничегонеделания итератор, который просто держит одно значение:

template<class T, class Dist=size_t, class Ptr = T*, class Ref = T&> 
class unique_it : public std::iterator<std::random_access_iterator_tag, T, Dist, Ptr, Ref> { 
    T &value; 
public: 
    unique_it(T &v) : value(v) {} 
    T &operator*() { return value; } 
    unique_it &operator++() { return *this; } 
    unique_it &operator+(size_t) { return *this; } 
    unique_it &operator++(int) { return *this; } 
}; 

template <class T> 
unique_it<T> make_res(T &v) { return unique_it<T>(v); } 

С этим, ваш L1 нормализация будет выглядеть как это:

int main(){ 
    double result=0.0; 
    double inputs[] = {1, -2, 3, -4, 5, -6}; 

    std::partial_sum(
     inputs, inputs+6, 
     make_res(result), 
     [](double acc, double v) {return acc + std::abs(v);}); 

    std::cout << result << "\t"; 
    return 0; 
} 

Answer 3

Если вы хотите использовать какой-то параллелизм, я сделал быструю версию с помощью OpenMP:

template <class T, 
      class InputIterator, 
      class MapFunction, 
      class ReductionFunction> 
T MapReduce_n(InputIterator in, 
       unsigned int size, 
       T baseval, 
       MapFunction mapper, 
       ReductionFunction reducer) 
{ 
    T val = baseval; 

    #pragma omp parallel 
    { 
     T map_val = baseval; 

     #pragma omp for nowait 
     for (auto i = 0U; i < size; ++i) 
     { 
      map_val = reducer(map_val, mapper(*(in + i))); 
     } 

     #pragma omp critical 
     val = reducer(val, map_val); 
    } 

    return val; 
} 

это быстро, но есть, конечно, комната для оптимизации, особенно вокруг for (auto i = 0U; i < size; ++i) думаю. (Но я не мог понять, как сделать версию с итератором только с OpenMP, любая помощь будет оценена!).

При быстром тестировании с массивом 1000000 элементов и вычислении, которое повторялось 1000 раз, чтобы иметь среднее значение, я сделал несколько сравнений.

Версия 1:

for (auto i = 0U; i < size; ++i) 
    val += std::pow(in[i][0], 2) + std::pow(in[i][1], 2); 

оценка при компиляции с:

• g++: 30 секунд
• g++ -O3: 2,6 секунды

Version 2:

Эта версия наиболее оптимизирована для этого вычисления, я думаю. (Это дает лучший результат).

#pragma omp parallel reduction(+ : val) 
{ 
    double map_val = 0.0; 

    #pragma omp for 
    for (int i=0; i < size; ++i) 
    { 
     map_val += std::pow(in[i][0], 2) + std::pow(in[i][1], 2); 
    } 

    val += map_val; 
} 

• g++ -O3: 0,2 секунды (это самый лучший один)

Версия 3

Эта версия использует шаблон функции MapReduce_n I показано ранее:

double val = MapReduce_n(in, size, 0.0, [] (fftw_complex val) 
    { 
     return std::pow(val[0], 2.0) + std::pow(val[1], 2.0); 
    }, std::plus<double>()); 

• g++ -O3: 0,4 секунды, поэтому есть небольшая накладная плата за то, что напрямую не используется непосредственно OMP-снимок. Тем не менее, он не позволяет настраивать операторов, поэтому в какой-то момент вам (к сожалению) приходится торговать скоростью для родовой.

Answer 4

Я удивлен, никто не сказал, как сделать это с Boost.Range:

accumulate(v | transformed((int(*)(int))&std::abs), 0); 

где v является Singe Pass Range (т.е. любой STL контейнер). Необходимо указать перегрузку абс, иначе это было бы столь же изящно, как Haskell.