Transform-and-Accumulate

Question

jemand hat einen C++ STL-konformen Algorithmus geschrieben, die std::transform und std::accumulate in einen einzigen Durchlauf-Algorithmus kombiniert unterstützt sowohl die unären und binäre und vielleicht sogar (n-ary!) Variante, sagt std::transformed_accumulate? Ich möchte das, weil ich dieses Muster zum Beispiel in (l1-) Normberechnungen zum Beispiel in der linearen Algebra als sehr wiederverwendbar gefunden habe. Die l1-Norm berechnet die Summe der absoluten Werte der Elemente.

Answer 1

Uhm ... Meine Wette ist, dass Sie das tun können, indem Sie Ihre Transformation in das binäre Prädikat einbetten, das Element transformieren und nach der Transformation akkumulieren.

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

Das Funktors wäre gleichbedeutend mit:

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

Natürlich ist diese allgemeine gemacht werden konnte, nur die Transformation Funktors auf eine generische Basis Funktors passieren:

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

und man konnte Verallgemeinere auch den Typ im Container ... oder erstelle sogar einen generischen transform_accumulator, der sowohl einen Akkumulator als auch einen Transformations-Funktor verwendet und diese der Reihe nach anwendet. Tatsächliche Implementierung als Übung für den Leser.

Answer 2

Obwohl es nicht genau der ursprünglichen Absicht entspricht, ist std::inner_product im Grunde Ihre binäre Version. Sie geben es einen Anfangswert, zwei Bereiche, und zwei functors, und es gilt sie als:

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

für Ihre L1 Also, wenn Sie etwas auf dieser allgemeinen Ordnung tun würde:

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

Nur das funktioniert nicht ganz - im Moment versucht es, std::abs zu übergeben, wo Sie wirklich eine binäre Funktion brauchen, die die zwei Eingänge kombiniert, aber ich bin nicht sicher, wie die zwei Eingänge wirklich kombiniert werden sollen.

std::partial_sum ist ziemlich nah an Ihrer unären Version, außer dass zusammen mit dem Ansammeln eines Ergebnisses, es versucht (versucht) jedes Zwischenergebnis, nicht nur das Endergebnis. Um nur das Endergebnis zu bekommen, würden Sie schreiben müssen (und eine Instanz übergeben), um eine Art von do-nothing Iterator, der nur einen einzigen Wert hält:

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

Damit wäre Ihre L1 Normalisierung aussehen etwas dies wie:

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

Wenn Sie einige Parallelität verwenden möchten, habe ich eine schnelle Version OpenMP mit:

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

Es ist schnell, aber es gibt sicherlich Raum für Optimierung, vor allem um for (auto i = 0U; i < size; ++i) Ich denke. (Aber ich konnte mir nicht vorstellen, wie man eine Iterator-Only-Version mit OpenMP erstellt, jede Hilfe wäre willkommen!).

Bei einem schnellen Test mit 1000000 Elementen Array, und die Berechnung tausendmal wiederholt, um einen Mittelwert zu haben, machte ich einige Vergleiche.

Version 1:

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

Punktzahl, wenn sie mit kompiliert:

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

Version 2:

Diese Version ist am besten für diese Berechnung optimiert, denke ich. (Es gibt das beste Ergebnis).

#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 Sekunden (es ist das beste)

Version 3

Diese Version verwendet die Funktion Vorlage MapReduce_n ich früher gezeigt:

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 Sekunden, so gibt es einen geringen Aufwand für die direkte Verwendung der OMP nicht direkt reduzieren. Allerdings erlaubt es keine benutzerdefinierten Operatoren, so dass Sie an einem Punkt (leider) die Geschwindigkeit für die Generizität tauschen müssen.

Answer 4

Ich bin überrascht, niemand sagte, wie dies mit Boost.Range zu tun:

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

wo v eine Singe Pass Range (dh jeder STL-Container). Die Abs-Überladung muss angegeben werden, sonst wäre das so elegant wie Haskell.