Noch mehr Spass mit reduce

Jetzt nochmal zurück zu unseren Strings. In unserem obigen Beispiel hätte ich, ehrlich gesagt, lieber "This is a sentence" anstelle von "Thisisasentence" gesehen. Eigentlich muss man ja nur ein Leerzeichen zwischen 2 Worten einfügen ... das macht der vordefinierte operator+(std::string const&, std::string const&) jedoch nicht. Aber jetzt können wir uns ja unseren eigenen Operator definieren! (Noch eine Übungsaufgabe).

Wir können unser reduce auch für Aufgaben einsetzen, an die man evtl. nicht unmittelbar denkt, z.B. das Auftreten von Elementen mit bestimmten Eigenschaften zählen (std::count_if). Wir hatten weiter oben ja schon gesagt, dass init durchaus ein anderer Typ als der Wertetyp der Sequenz sein kann. Der Operator sollte also genau genommen als erstes Argument einen Wert mit dem Typ von init (oder konvertierbar) akzeptieren, und als zweites Argument einen Wert vom Sequenz-Wertetyp (oder konvertierbar). Damit können wir sehr einfach die Funktionalität von std::count_if mit unserem reduce erreichen:

template<typename Pred, typename T>
struct count {
  Pred p;
  count(Pred p) : p(p) {}
  int operator()(int cnt, T t) const { return cnt + (p(t) ? 1 : 0); }
};

struct is_positive { bool operator()(float x) const { return x > 0.0; } };

int cnt_positive = reduce(a, a+N, value<int>(0), count<is_positive,float>());

Relativ lästig ist es, dass diese Operatoren und Prädikate separat definiert werden müssen, grade wenn sie eher ad hoc sind. Bibliotheken wie boost.bind machen es etwas einfacher, vorhandenes anzupassen. In C++11 liefern lambdas eine allgemeine Lösung:

int cnt_positive = reduce(a, a+N, value<int>(0), 
	                  [](int cnt, float x) { return cnt + (x > 0 ? 1 : 0); })

Damit sollte auch klar sein, wie man an Fälle wie den folgenden herangeht:

struct employee {
  string  name;
  float   salary;
};

vector<employee> staff;
// ... fill staff ...
float total_salaries = reduce(staff.begin(), staff.end(), ???);

Auch das wird mit Cpp11 durchaus einfacher ...

Spassbremsen

Allerdings ist es schon sinnvoll, sich Gedanken über die Grenzen des Anwendungsbereichs von reduce zu machen. So hat das Beispiel mit string den Nachteil, dass bei jeder Addition wieder Speicher allokiert wird, weil der Ergebnisstring in res wieder ein Stückchen größer wird. Effizienter wäre es, den benötigten Speicher vorab zu reservieren. Aber dazu müssten wir noch erhebliche Arbeit leisten und möglicherweise das Interface ändern.

Der linear wachsende Speicherbedarf ist ein entscheidender struktureller Unterschied zur Addition von Zahlen, bei denen das Ergebnis diesselbe Größe hat wie die einzelnen Input-Daten (auch in den Fällen, in denen ein Ergebnistyp mit größerem Wertebereich gewählt wird, ist die Größe ja fest). Deswegen macht es wohl Sinn, eine eigene Abstraktion, etwa concat einzuführen, die hierauf explizit Rücksicht nimmt.
Übungsaufgabe: Wie würde man concat generisch implementieren?

Bei der ursprünglichen, auf Addition beschränkten Implementierung von sum war die (scheinbare, siehe Probleme mit der Initialisierung) Anwendbarkeit auf string ja auch nur der zufälligen Tatsache geschuldet, dass beim Sprachentwurf der operator+ bei string für die String-Verkettung gewählt wurde — in anderen Sprachen werden andere Operatoren benutzt. Experten wie Alexander Stepanov halten die Wahl von operator+ hier sogar für einen Fehler, weil Verkettung eben nicht kommutativ ist, wie man es bei diesem Operator erwarten würde. Das macht bei unserem sum zwar keinen Unterschied, aber ich kann mir durchaus Fälle vorstellen, in denen die Reihenfolge geändert wird, z.B. bei der parallelen Implementierung. Dies sollte dann zwar klar spezifiziert werden, aber eine solche unkonventionelle nicht-Kommutativität bleibt eine Fehlerquelle.

Unsere reduce-Implementierung ist auch dort nicht optimal, wo man des Ergebnis erhalten kann, ohne die gesamte Sequenz zu durchlaufen, z.B. bei der Reduktion einer Sequenz boolscher Werte mit logical_and oder logical_or. Also genügt reduce auch nicht voll unserer strengen Definition.
Übungsaufgabe: Kann man das reparieren?

Über den C++ Tellerrand

Was wir hier reduce genannt haben, ist unter verschiedenen Namen bekannt. In der C++-Standardbibliothek heißt diese Funktion accumulate (und sie hat durch das zusätzliche init-Argument das oben beschriebene Problem des genauen Typs bei Literalen).

In der funktionalen Programmierung nennt man diese higher-order function typischerweise fold bzw. genauer foldl (weil von links geklammert wird: a+b+c = (a+b)+c). Das Gegenstück foldr würde man erhalten, wenn die Sequenz umgekehrt durchlaufen wird, oder, wie in der funktionalen Programmierung üblich, eine rekursive Implementierung gewählt würde:

template<typename Iterator, typename T, typename Op>
T reduce_rec(Iterator begin, Iterator end, value<T> init, Op op)
{ return (begin == end? init : op(*begin, reduce_rec(begin+1, end, init, op))); }

Hier würde übrigens init erst ganz am Schluss benutzt.

• <<<Vorherige Seite
• Nächste Seite >>>