Transform-e-Accumulo

Question

Qualcuno ha scritto un algoritmo STL compatibile C++ che combina std::transform e std::accumulate in un algoritmo singolo passaggio supportare sia la variante unario e binario e forse anche (n-ary!), Detto std::transformed_accumulate? Lo voglio perché ho trovato questo pattern altamente riutilizzabile ad esempio nell'algebra lineare, ad esempio nei calcoli della norma (l1-). La norma l1 calcola la somma dei valori assoluti degli elementi.

Answer 1

Uhm ... La mia scommessa è che puoi farlo incorporando la tua trasformazione nel predicato binario, trasformando l'elemento e accumulandolo dopo la trasformazione.

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

Questo funtore sarebbe equivalente a:

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

Naturalmente questo potrebbe essere fatto generico, basta passare il funtore trasformazione ad un funtore di base generico:

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

e si potrebbe generalizza anche sul tipo nel contenitore ... o crea anche un trasform_accumulatore più generico che prende sia un accumulatore che un trasformatore e li applica in ordine. Attuazione effettiva lasciata come esercizio per il lettore.

Answer 2

Anche se potrebbe non corrispondere esattamente all'intento originale, std::inner_product è in pratica la versione binaria. Si passa un valore iniziale, due gamme, e due funtori, e li applica come:

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

Così, per la L1 si farebbe qualcosa su questo ordine generale:

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

Solo che non funziona abbastanza - al momento, sta cercando di passare a std::abs dove hai davvero bisogno di una funzione binaria che combini i due input, ma non sono sicuro di come i due input dovrebbero essere combinati.

std::partial_sum è abbastanza vicino alla versione unaria, eccetto che insieme all'accumulo di un risultato, esso (tenta di) di scrivere ogni risultato intermedio, non solo il risultato finale. Per ottenere solo il risultato finale, che ci si deve scrivere (e passare un'istanza di) una sorta di do-nothing iteratore che appena in possesso di un unico valore:

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

Con questo, il vostro normalizzazione L1 apparirebbe qualcosa in questo modo:

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

Se si desidera utilizzare un certo parallelismo, ho fatto una versione veloce usando 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; 
} 

E 'veloce, ma c'è sicuramente spazio per l'ottimizzazione, soprattutto intorno for (auto i = 0U; i < size; ++i) Penso. (Ma non riuscivo a capire come creare una versione solo iteratore con OpenMP, qualsiasi aiuto sarebbe apprezzato!).

Su un test rapido con array di 1000000 elementi e il calcolo ripetuto 1000 volte per avere un valore medio, ho fatto alcuni confronti.

Versione 1:

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

punteggio quando compilato con:

• g++: 30 secondi
• g++ -O3: 2,6 secondi

versione 2:

Questa versione è la più ottimizzata per questo calcolo, penso. (Dà il miglior risultato).

#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 secondi (che è il migliore)

versione 3

Questa versione utilizza la funzione di modello MapReduce_n ho mostrato in precedenza:

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 secondi, quindi c'è un leggero sovraccarico per non utilizzare direttamente la riduzione OMP direttamente. Tuttavia, non consente agli operatori personalizzati, quindi a un certo punto (purtroppo) devi scambiare velocità per genericità.

Answer 4

Io sono nessuno sorpreso ha detto come fare questo con Boost.Range:

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

dove v è una (vale a dire, qualsiasi contenitore STL) Singe Pass Range. Il sovraccarico degli addominali deve essere specificato, altrimenti sarebbe elegante come Haskell.