Geek asks and answers

Transform-and-accumulate

Somebody wrote an algorithm that is compatible with the C ++ STL, which brings together std::transformand std::accumulatein a single-pass algorithm that supports both the unitary and the binary and perhaps even (n-ary!) Option, for example std::transformed_accumulate? I want this because I found this pattern reusable, for example, for linear algebra, for example, in (l1-) calculations. L1-norm calculates the sum of the absolute values ​​of the elements.

+5
source share
4 answers

Umm ... My bet is that you can do this by nesting your transform in a binary predicate, transform the element and copy it after the conversion.

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

This functor will be equivalent to:

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

... transform_accumulator, , . .

+9

, 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 , , () , . , ( ) do-nothing, :

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;
}
+2

parallelism, 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

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, :

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-. , , - ( ) .
+1

, , Boost.Range:

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

where v is the Singe Pass Range (i.e. any STL container). Abs must be specified, otherwise it would be as elegant as Haskell.

+1
source

More articles:


All Articles