C++
Ausdrucksvorlagen
Suche…
Grundlegende Ausdrucksvorlagen für elementweise algebraische Ausdrücke
Einführung und Motivation
Ausdrucksvorlagen (im Folgenden als ETs bezeichnet) sind eine leistungsfähige Vorlagenmeta-Programmiertechnik, mit der die Berechnung von manchmal recht teuren Ausdrücken beschleunigt wird. Es wird häufig in verschiedenen Bereichen verwendet, beispielsweise bei der Implementierung von linearen Algebra-Bibliotheken.
Betrachten Sie für dieses Beispiel den Kontext der linearen algebraischen Berechnungen. Insbesondere Berechnungen, die nur elementweise Operationen umfassen . Diese Art von Berechnungen sind die grundlegendsten Anwendungen von ETs und sie sind eine gute Einführung in die interne Arbeitsweise von ETs .
Schauen wir uns ein motivierendes Beispiel an. Betrachten Sie die Berechnung des Ausdrucks:
Vector vec_1, vec_2, vec_3;
// Initializing vec_1, vec_2 and vec_3.
Vector result = vec_1 + vec_2*vec_3;
Der Einfachheit halber gehe ich davon aus, dass die Klassen Vector und operation + (vector plus: elementweise plus Operation) und operation * (hier bedeutet vector inneres Produkt: auch elementweise Operation) beide korrekt implementiert sind, wie z wie sie mathematisch sein sollten.
Bei einer herkömmlichen Implementierung ohne Verwendung von ETs (oder anderen ähnlichen Techniken) finden mindestens fünf Konstruktionen von Vector Instanzen statt, um das result :
- Drei Instanzen, die
vec_1,vec_2undvec_3. - Eine temporäre
VectorInstanz_tmp, die das Ergebnis von_tmp = vec_2*vec_3;. - Bei richtiger Verwendung der Rückgabewertoptimierung schließlich wird die Erstellung des
resultinresult = vec_1 + _tmp;.
Die Implementierung mit ETs kann die Erstellung von temporärem Vector _tmp in 2 verhindern, sodass nur vier Konstruktionen von Vector Instanzen übrig Vector _tmp . Interessanter ist der folgende Ausdruck, der komplexer ist:
Vector result = vec_1 + (vec_2*vec3 + vec_1)*(vec_2 + vec_3*vec_1);
Insgesamt gibt es vier Konstruktionen von Vector Instanzen: vec_1, vec_2, vec_3 und result . Mit anderen Worten, in diesem Beispiel, bei dem nur elementweise Operationen beteiligt sind , ist gewährleistet, dass aus Zwischenberechnungen keine temporären Objekte erstellt werden .
Wie funktionieren ETs?
Grundsätzlich bestehen ETs für algebraische Berechnungen aus zwei Bausteinen:
- Reine algebraische Ausdrücke ( PAE ): Sie sind Proxies / Abstraktionen algebraischer Ausdrücke. Eine reine Algebraik führt keine tatsächlichen Berechnungen durch, sondern ist lediglich eine Abstraktion / Modellierung des Berechnungs-Workflows. Eine PAE kann ein Modell entweder der Eingabe oder der Ausgabe von algebraischen Ausdrücken sein . Instanzen von PAEs werden oft als billig betrachtet.
- Faule Auswertungen : Dies sind Implementierungen realer Berechnungen. Im folgenden Beispiel werden wir sehen, dass für Ausdrücke, die nur elementweise Operationen enthalten, Lazy-Auswertungen tatsächliche Berechnungen innerhalb der indizierten Zugriffsoperation für das Endergebnis ausführen können, wodurch ein Bewertungsschema nach Bedarf erstellt wird: Eine Berechnung wird nicht durchgeführt Nur wenn auf das Endergebnis zugegriffen wird.
Also, wie implementieren wir in diesem Beispiel genau ETs ? Lass uns jetzt durchgehen.
Beachten Sie immer den folgenden Code-Ausschnitt:
Vector vec_1, vec_2, vec_3;
// Initializing vec_1, vec_2 and vec_3.
Vector result = vec_1 + vec_2*vec_3;
Der zu berechnende Ausdruck kann weiter in zwei Unterausdrücke zerlegt werden:
- Ein Vektor plus Ausdruck (als plus_expr bezeichnet )
- Ein Vektor-Produktausdruck (bezeichnet als innerprod_expr ).
Was machen die ETs ?
Statt jeden Unterausdruck sofort zu berechnen, modellieren die ETs zunächst den gesamten Ausdruck anhand einer grafischen Struktur. Jeder Knoten in der Grafik repräsentiert eine PAE . Die Kantenverbindung der Knoten repräsentiert den tatsächlichen Rechenfluss. Für den obigen Ausdruck erhalten wir die folgende Grafik:
result = plus_expr( vec_1, innerprod_expr(vec_2, vec_3) ) / \ / \ / \ / innerprod_expr( vec_2, vec_3 ) / / \ / / \ / / \ vec_1 vec_2 vec_3
Die abschließende Berechnung wird durch einen Blick in die Diagrammhierarchie implementiert: Da es sich hier nur um elementweise Operationen handelt, kann die Berechnung jedes indizierten Werts im
resultunabhängig voneinander erfolgen : Die abschließende Auswertung desresultkann träge auf ein Element verschoben werden. weise Bewertung jedesresult. Mit anderen Worten, da die Berechnung eines Elements vonresult,elem_res, unter Verwendung entsprechender Elemente invec_1(elem_1),vec_2(elem_2) undvec_3(elem_3)elem_3werden kann:elem_res = elem_1 + elem_2*elem_3;
Es ist daher nicht erforderlich, einen temporären Vector zu erstellen, um das Ergebnis des Zwischenprodukts zu speichern: Die gesamte Berechnung für ein Element kann vollständig ausgeführt und innerhalb der indizierten Zugriffsoperation codiert werden .
Hier sind die Beispielcodes in Aktion.
Datei vec.hh: Wrapper für std :: vector, um Protokoll anzuzeigen, wenn eine Konstruktion aufgerufen wird.
#ifndef EXPR_VEC
# define EXPR_VEC
# include <vector>
# include <cassert>
# include <utility>
# include <iostream>
# include <algorithm>
# include <functional>
///
/// This is a wrapper for std::vector. It's only purpose is to print out a log when a
/// vector constructions in called.
/// It wraps the indexed access operator [] and the size() method, which are
/// important for later ETs implementation.
///
// std::vector wrapper.
template<typename ScalarType> class Vector
{
public:
explicit Vector() { std::cout << "ctor called.\n"; };
explicit Vector(int size): _vec(size) { std::cout << "ctor called.\n"; };
explicit Vector(const std::vector<ScalarType> &vec): _vec(vec)
{ std::cout << "ctor called.\n"; };
Vector(const Vector<ScalarType> & vec): _vec{vec()}
{ std::cout << "copy ctor called.\n"; };
Vector(Vector<ScalarType> && vec): _vec(std::move(vec()))
{ std::cout << "move ctor called.\n"; };
Vector<ScalarType> & operator=(const Vector<ScalarType> &) = default;
Vector<ScalarType> & operator=(Vector<ScalarType> &&) = default;
decltype(auto) operator[](int indx) { return _vec[indx]; }
decltype(auto) operator[](int indx) const { return _vec[indx]; }
decltype(auto) operator()() & { return (_vec); };
decltype(auto) operator()() const & { return (_vec); };
Vector<ScalarType> && operator()() && { return std::move(*this); }
int size() const { return _vec.size(); }
private:
std::vector<ScalarType> _vec;
};
///
/// These are conventional overloads of operator + (the vector plus operation)
/// and operator * (the vector inner product operation) without using the expression
/// templates. They are later used for bench-marking purpose.
///
// + (vector plus) operator.
template<typename ScalarType>
auto operator+(const Vector<ScalarType> &lhs, const Vector<ScalarType> &rhs)
{
assert(lhs().size() == rhs().size() &&
"error: ops plus -> lhs and rhs size mismatch.");
std::vector<ScalarType> _vec;
_vec.resize(lhs().size());
std::transform(std::cbegin(lhs()), std::cend(lhs()),
std::cbegin(rhs()), std::begin(_vec),
std::plus<>());
return Vector<ScalarType>(std::move(_vec));
}
// * (vector inner product) operator.
template<typename ScalarType>
auto operator*(const Vector<ScalarType> &lhs, const Vector<ScalarType> &rhs)
{
assert(lhs().size() == rhs().size() &&
"error: ops multiplies -> lhs and rhs size mismatch.");
std::vector<ScalarType> _vec;
_vec.resize(lhs().size());
std::transform(std::cbegin(lhs()), std::cend(lhs()),
std::cbegin(rhs()), std::begin(_vec),
std::multiplies<>());
return Vector<ScalarType>(std::move(_vec));
}
#endif //!EXPR_VEC
Datei expr.hh: Implementierung von Ausdrucksvorlagen für elementweise Operationen (vector plus und vector inner product)
Lassen Sie uns es in Abschnitte aufteilen.
- Abschnitt 1 implementiert eine Basisklasse für alle Ausdrücke. Es verwendet das Curiously Recurring Template Pattern ( CRTP ).
- Abschnitt 2 implementiert die erste PAE : ein Terminal , das nur ein Wrapper (const-Referenz) einer Eingabedatenstruktur ist, die einen realen Eingabewert für die Berechnung enthält.
- Abschnitt 3 implementiert die zweite PAE : binary_operation , eine Klassenvorlage, die später für vector_plus und vector_innerprod verwendet wird. Sie wird durch die Art der Bedienung , die linke PAE und die rechte PAE parametrisiert. Die tatsächliche Berechnung wird im Operator für indizierten Zugriff codiert.
- Abschnitt 4 definiert die Operationen vector_plus und vector_innerprod als elementweise Operationen . Außerdem werden die Operatoren + und * für PAEs überladen, sodass diese beiden Operationen auch PAE zurückgeben .
#ifndef EXPR_EXPR
# define EXPR_EXPR
/// Fwd declaration.
template<typename> class Vector;
namespace expr
{
/// -----------------------------------------
///
/// Section 1.
///
/// The first section is a base class template for all kinds of expression. It
/// employs the Curiously Recurring Template Pattern, which enables its instantiation
/// to any kind of expression structure inheriting from it.
///
/// -----------------------------------------
/// Base class for all expressions.
template<typename Expr> class expr_base
{
public:
const Expr& self() const { return static_cast<const Expr&>(*this); }
Expr& self() { return static_cast<Expr&>(*this); }
protected:
explicit expr_base() {};
int size() const { return self().size_impl(); }
auto operator[](int indx) const { return self().at_impl(indx); }
auto operator()() const { return self()(); };
};
/// -----------------------------------------
///
/// The following section 2 & 3 are abstractions of pure algebraic expressions (PAE).
/// Any PAE can be converted to a real object instance using operator(): it is in
/// this conversion process, where the real computations are done.
///
/// Section 2. Terminal
///
/// A terminal is an abstraction wrapping a const reference to the Vector data
/// structure. It inherits from expr_base, therefore providing a unified interface
/// wrapping a Vector into a PAE.
///
/// It provides the size() method, indexed access through at_impl() and a conversion
/// to referenced object through () operator.
///
/// It might no be necessary for user defined data structures to have a terminal
/// wrapper, since user defined structure can inherit expr_base, therefore eliminates
/// the need to provide such terminal wrapper.
///
/// -----------------------------------------
/// Generic wrapper for underlying data structure.
template<typename DataType> class terminal: expr_base<terminal<DataType>>
{
public:
using base_type = expr_base<terminal<DataType>>;
using base_type::size;
using base_type::operator[];
friend base_type;
explicit terminal(const DataType &val): _val(val) {}
int size_impl() const { return _val.size(); };
auto at_impl(int indx) const { return _val[indx]; };
decltype(auto) operator()() const { return (_val); }
private:
const DataType &_val;
};
/// -----------------------------------------
///
/// Section 3. Binary operation expression.
///
/// This is a PAE abstraction of any binary expression. Similarly it inherits from
/// expr_base.
///
/// It provides the size() method, indexed access through at_impl() and a conversion
/// to referenced object through () operator. Each call to the at_impl() method is
/// a element wise computation.
///
/// -----------------------------------------
/// Generic wrapper for binary operations (that are element-wise).
template<typename Ops, typename lExpr, typename rExpr>
class binary_ops: public expr_base<binary_ops<Ops,lExpr,rExpr>>
{
public:
using base_type = expr_base<binary_ops<Ops,lExpr,rExpr>>;
using base_type::size;
using base_type::operator[];
friend base_type;
explicit binary_ops(const Ops &ops, const lExpr &lxpr, const rExpr &rxpr)
: _ops(ops), _lxpr(lxpr), _rxpr(rxpr) {};
int size_impl() const { return _lxpr.size(); };
/// This does the element-wise computation for index indx.
auto at_impl(int indx) const { return _ops(_lxpr[indx], _rxpr[indx]); };
/// Conversion from arbitrary expr to concrete data type. It evaluates
/// element-wise computations for all indices.
template<typename DataType> operator DataType()
{
DataType _vec(size());
for(int _ind = 0; _ind < _vec.size(); ++_ind)
_vec[_ind] = (*this)[_ind];
return _vec;
}
private: /// Ops and expr are assumed cheap to copy.
Ops _ops;
lExpr _lxpr;
rExpr _rxpr;
};
/// -----------------------------------------
/// Section 4.
///
/// The following two structs defines algebraic operations on PAEs: here only vector
/// plus and vector inner product are implemented.
///
/// First, some element-wise operations are defined : in other words, vec_plus and
/// vec_prod acts on elements in Vectors, but not whole Vectors.
///
/// Then, operator + & * are overloaded on PAEs, such that: + & * operations on PAEs
/// also return PAEs.
///
/// -----------------------------------------
/// Element-wise plus operation.
struct vec_plus_t
{
constexpr explicit vec_plus_t() = default;
template<typename LType, typename RType>
auto operator()(const LType &lhs, const RType &rhs) const
{ return lhs+rhs; }
};
/// Element-wise inner product operation.
struct vec_prod_t
{
constexpr explicit vec_prod_t() = default;
template<typename LType, typename RType>
auto operator()(const LType &lhs, const RType &rhs) const
{ return lhs*rhs; }
};
/// Constant plus and inner product operator objects.
constexpr vec_plus_t vec_plus{};
constexpr vec_prod_t vec_prod{};
/// Plus operator overload on expressions: return binary expression.
template<typename lExpr, typename rExpr>
auto operator+(const lExpr &lhs, const rExpr &rhs)
{ return binary_ops<vec_plus_t,lExpr,rExpr>(vec_plus,lhs,rhs); }
/// Inner prod operator overload on expressions: return binary expression.
template<typename lExpr, typename rExpr>
auto operator*(const lExpr &lhs, const rExpr &rhs)
{ return binary_ops<vec_prod_t,lExpr,rExpr>(vec_prod,lhs,rhs); }
} //!expr
#endif //!EXPR_EXPR
Datei main.cc: Test-SRC-Datei
# include <chrono>
# include <iomanip>
# include <iostream>
# include "vec.hh"
# include "expr.hh"
# include "boost/core/demangle.hpp"
int main()
{
using dtype = float;
constexpr int size = 5e7;
std::vector<dtype> _vec1(size);
std::vector<dtype> _vec2(size);
std::vector<dtype> _vec3(size);
// ... Initialize vectors' contents.
Vector<dtype> vec1(std::move(_vec1));
Vector<dtype> vec2(std::move(_vec2));
Vector<dtype> vec3(std::move(_vec3));
unsigned long start_ms_no_ets =
std::chrono::duration_cast<std::chrono::milliseconds>
(std::chrono::system_clock::now().time_since_epoch()).count();
std::cout << "\nNo-ETs evaluation starts.\n";
Vector<dtype> result_no_ets = vec1 + (vec2*vec3);
unsigned long stop_ms_no_ets =
std::chrono::duration_cast<std::chrono::milliseconds>
(std::chrono::system_clock::now().time_since_epoch()).count();
std::cout << std::setprecision(6) << std::fixed
<< "No-ETs. Time eclapses: " << (stop_ms_no_ets-start_ms_no_ets)/1000.0
<< " s.\n" << std::endl;
unsigned long start_ms_ets =
std::chrono::duration_cast<std::chrono::milliseconds>
(std::chrono::system_clock::now().time_since_epoch()).count();
std::cout << "Evaluation using ETs starts.\n";
expr::terminal<Vector<dtype>> vec4(vec1);
expr::terminal<Vector<dtype>> vec5(vec2);
expr::terminal<Vector<dtype>> vec6(vec3);
Vector<dtype> result_ets = (vec4 + vec5*vec6);
unsigned long stop_ms_ets =
std::chrono::duration_cast<std::chrono::milliseconds>
(std::chrono::system_clock::now().time_since_epoch()).count();
std::cout << std::setprecision(6) << std::fixed
<< "With ETs. Time eclapses: " << (stop_ms_ets-start_ms_ets)/1000.0
<< " s.\n" << std::endl;
auto ets_ret_type = (vec4 + vec5*vec6);
std::cout << "\nETs result's type:\n";
std::cout << boost::core::demangle( typeid(decltype(ets_ret_type)).name() ) << '\n';
return 0;
}
Beim Kompilieren mit -O3 -std=c++14 Verwendung von GCC 5.3 ist eine mögliche Ausgabe möglich:
ctor called.
ctor called.
ctor called.
No-ETs evaluation starts.
ctor called.
ctor called.
No-ETs. Time eclapses: 0.571000 s.
Evaluation using ETs starts.
ctor called.
With ETs. Time eclapses: 0.164000 s.
ETs result's type:
expr::binary_ops<expr::vec_plus_t, expr::terminal<Vector<float> >, expr::binary_ops<expr::vec_prod_t, expr::terminal<Vector<float> >, expr::terminal<Vector<float> > > >
Die Beobachtungen sind:
- Die Verwendung von ETs erzielt in diesem Fall eine ziemlich deutliche Leistungssteigerung (> 3x).
- Die Erstellung eines temporären Vector-Objekts wird eliminiert. Wie im Fall der ET wird ctor nur einmal aufgerufen.
- Boost :: demangle wurde verwendet, um die Art der Rückgabe von ETs vor der Konvertierung zu visualisieren: Es konstruierte genau den gleichen Ausdruck wie oben gezeigt.
Nachteile und Vorbehalte
Ein offensichtlicher Nachteil von ETs ist die Lernkurve, die Komplexität der Implementierung und der Schwierigkeitsgrad der Codewartung . In dem obigen Beispiel, in dem nur elementweise Operationen betrachtet werden, enthält die Implementierung bereits eine enorme Anzahl von Boilerplates, geschweige denn in der realen Welt, wo komplexere algebraische Ausdrücke in jeder Berechnung vorkommen und die Unabhängigkeit von Elementen nicht mehr zutrifft (zum Beispiel Matrixmultiplikation) ) wird der Schwierigkeitsgrad exponentiell sein.
Ein weiterer Nachteil bei der Verwendung von ETs ist, dass sie mit dem Schlüsselwort
autogut funktionieren. Wie oben erwähnt, handelt es sich bei PAEs im Wesentlichen um Proxies: Proxies spielen im Grunde nicht gut mitauto. Betrachten Sie das folgende Beispiel:auto result = ...; // Some expensive expression: // auto returns the expr graph, // NOT the computed value. for(auto i = 0; i < 100; ++i) ScalrType value = result* ... // Some other expensive computations using result.
Hier wird das Ergebnis in jeder Iteration der for-Schleife erneut ausgewertet , da anstelle des berechneten Werts der Ausdrucksgraph an die for-Schleife übergeben wird.
Bestehende Bibliotheken, die ETs implementieren
- boost :: proto ist eine leistungsstarke Bibliothek, in der Sie Ihre eigenen Regeln und Grammatiken für Ihre eigenen Ausdrücke definieren und mit ETs ausführen können.
- Eigen ist eine Bibliothek für lineare Algebra, die verschiedene algebraische Berechnungen effizient mit ETs implementiert.
Ein einfaches Beispiel, das Ausdrucksvorlagen veranschaulicht
Eine Ausdrucksvorlage ist eine Kompilierungszeitoptimierungstechnik, die hauptsächlich im wissenschaftlichen Rechnen verwendet wird. Ihr Hauptzweck besteht darin, unnötige temporäre Werte zu vermeiden und die Schleifenberechnungen mit einem einzigen Durchgang zu optimieren (normalerweise, wenn Operationen mit numerischen Aggregaten ausgeführt werden). Anfangs wurden Ausdrucksvorlagen entwickelt, um die Ineffizienz der naiven Überladung von Operatoren bei der Implementierung numerischer Array oder Matrix Typen zu umgehen. Eine äquivalente Terminologie für Ausdrucksvorlagen wurde von Bjarne Stroustrup eingeführt, der sie in der neuesten Version seines Buches "Die C ++ - Programmiersprache" als "fusionierte Operationen" bezeichnet.
Bevor Sie tatsächlich in Ausdrucksvorlagen eintauchen, sollten Sie verstehen, warum Sie diese überhaupt benötigen. Um dies zu veranschaulichen, betrachten Sie die unten angegebene sehr einfache Matrix-Klasse:
template <typename T, std::size_t COL, std::size_t ROW>
class Matrix {
public:
using value_type = T;
Matrix() : values(COL * ROW) {}
static size_t cols() { return COL; }
static size_t rows() { return ROW; }
const T& operator()(size_t x, size_t y) const { return values[y * COL + x]; }
T& operator()(size_t x, size_t y) { return values[y * COL + x]; }
private:
std::vector<T> values;
};
template <typename T, std::size_t COL, std::size_t ROW>
Matrix<T, COL, ROW>
operator+(const Matrix<T, COL, ROW>& lhs, const Matrix<T, COL, ROW>& rhs)
{
Matrix<T, COL, ROW> result;
for (size_t y = 0; y != lhs.rows(); ++y) {
for (size_t x = 0; x != lhs.cols(); ++x) {
result(x, y) = lhs(x, y) + rhs(x, y);
}
}
return result;
}
In Anbetracht der vorherigen Klassendefinition können Sie jetzt Matrix-Ausdrücke schreiben, beispielsweise:
const std::size_t cols = 2000;
const std::size_t rows = 1000;
Matrix<double, cols, rows> a, b, c;
// initialize a, b & c
for (std::size_t y = 0; y != rows; ++y) {
for (std::size_t x = 0; x != cols; ++x) {
a(x, y) = 1.0;
b(x, y) = 2.0;
c(x, y) = 3.0;
}
}
Matrix<double, cols, rows> d = a + b + c; // d(x, y) = 6
Wenn Sie den operator+() überladen können, erhalten Sie eine Notation, die die natürliche mathematische Notation für Matrizen nachahmt.
Leider ist die vorherige Implementierung im Vergleich zu einer entsprechenden "handgefertigten" Version auch sehr ineffizient.
Um zu verstehen, warum, müssen Sie berücksichtigen, was passiert, wenn Sie einen Ausdruck wie Matrix d = a + b + c schreiben. Dies erweitert sich tatsächlich auf ((a + b) + c) oder operator+(operator+(a, b), c) . Mit anderen Worten, die Schleife innerhalb von operator+() wird zweimal ausgeführt, während sie in einem einzigen Durchgang problemlos ausgeführt werden konnte. Dies führt auch dazu, dass zwei temporäre Systeme erstellt werden, was die Leistung weiter verschlechtert. Im Wesentlichen haben Sie durch Hinzufügen der Flexibilität, eine Notation in der Nähe des mathematischen Gegenstücks zu verwenden, die Matrix Klasse auch sehr ineffizient gemacht.
Beispielsweise können Sie ohne Überladen eines Operators eine wesentlich effizientere Matrixsummierung mit einem einzigen Durchlauf implementieren:
template<typename T, std::size_t COL, std::size_t ROW>
Matrix<T, COL, ROW> add3(const Matrix<T, COL, ROW>& a,
const Matrix<T, COL, ROW>& b,
const Matrix<T, COL, ROW>& c)
{
Matrix<T, COL, ROW> result;
for (size_t y = 0; y != ROW; ++y) {
for (size_t x = 0; x != COL; ++x) {
result(x, y) = a(x, y) + b(x, y) + c(x, y);
}
}
return result;
}
Das vorige Beispiel hat jedoch seine eigenen Nachteile, da es eine viel mehr verschachtelte Schnittstelle für die Matrix-Klasse erstellt (Sie müssten Methoden wie Matrix::add2() , Matrix::AddMultiply() usw.) in Betracht ziehen.
Lassen Sie uns stattdessen einen Schritt zurückgehen und sehen, wie wir die Überlastung der Bediener anpassen können, um eine effizientere Leistung zu erzielen
Das Problem rührt von der Tatsache her, dass der Ausdruck Matrix d = a + b + c zu "eifrig" ausgewertet wird, bevor Sie die Möglichkeit hatten, den gesamten Ausdrucksbaum zu erstellen. Mit anderen Worten, Sie möchten a + b + c in einem Durchgang auswerten, und nur dann müssen Sie den resultierenden Ausdruck d zuweisen.
Dies ist die Kernidee von Ausdrucksvorlagen: Statt operator+() sofort das Ergebnis des Hinzufügens von zwei Matrixinstanzen auszuwerten, gibt es eine "Ausdrucksvorlage" für die zukünftige Auswertung zurück, sobald der gesamte Ausdrucksbaum erstellt wurde.
Hier ist zum Beispiel eine mögliche Implementierung für eine Ausdrucksvorlage, die der Summation von 2 Typen entspricht:
template <typename LHS, typename RHS>
class MatrixSum
{
public:
using value_type = typename LHS::value_type;
MatrixSum(const LHS& lhs, const RHS& rhs) : rhs(rhs), lhs(lhs) {}
value_type operator() (int x, int y) const {
return lhs(x, y) + rhs(x, y);
}
private:
const LHS& lhs;
const RHS& rhs;
};
Und hier ist die aktualisierte Version von operator+()
template <typename LHS, typename RHS>
MatrixSum<LHS, RHS> operator+(const LHS& lhs, const LHS& rhs) {
return MatrixSum<LHS, RHS>(lhs, rhs);
}
Wie Sie sehen, gibt operator+() keine "eifrige Bewertung" des Ergebnisses des Hinzufügens von 2 Matrix-Instanzen (was eine andere Matrix-Instanz wäre) zurück, sondern eine Ausdrucksvorlage, die die Additionsoperation darstellt. Der wichtigste Punkt, den Sie beachten sollten, ist, dass der Ausdruck noch nicht bewertet wurde. Es enthält lediglich Verweise auf seine Operanden.
Tatsächlich MatrixSum<> Sie nichts daran, die MatrixSum<> Ausdrucksvorlage wie folgt zu instanziieren:
MatrixSum<Matrix<double>, Matrix<double> > SumAB(a, b);
Sie können den Ausdruck d = a + b jedoch zu einem späteren Zeitpunkt, wenn Sie das Ergebnis der Summation tatsächlich benötigen, folgendermaßen bewerten:
for (std::size_t y = 0; y != a.rows(); ++y) {
for (std::size_t x = 0; x != a.cols(); ++x) {
d(x, y) = SumAB(x, y);
}
}
Wie Sie sehen, besteht ein weiterer Vorteil der Verwendung einer Ausdrucksvorlage darin, dass Sie im Wesentlichen die Summe von a und b auswerten und sie in einem einzigen Durchgang d zuordnen können.
Außerdem hindert Sie nichts daran, mehrere Ausdrucksvorlagen zu kombinieren. Beispiel: a + b + c führt zur folgenden Ausdrucksvorlage:
MatrixSum<MatrixSum<Matrix<double>, Matrix<double> >, Matrix<double> > SumABC(SumAB, c);
Und auch hier können Sie das Endergebnis mit einem einzigen Durchlauf auswerten:
for (std::size_t y = 0; y != a.rows(); ++y) {
for (std::size_t x = 0; x != a.cols(); ++x) {
d(x, y) = SumABC(x, y);
}
}
Der letzte Teil des Puzzles besteht schließlich darin, Ihre Ausdrucksvorlage tatsächlich in die Matrix Klasse Matrix . Dies wird im Wesentlichen durch die Bereitstellung einer Implementierung für Matrix::operator=() , die die Ausdrucksvorlage als Argument nimmt und sie in einem Durchgang auswertet, wie Sie es zuvor "manuell" getan haben:
template <typename T, std::size_t COL, std::size_t ROW>
class Matrix {
public:
using value_type = T;
Matrix() : values(COL * ROW) {}
static size_t cols() { return COL; }
static size_t rows() { return ROW; }
const T& operator()(size_t x, size_t y) const { return values[y * COL + x]; }
T& operator()(size_t x, size_t y) { return values[y * COL + x]; }
template <typename E>
Matrix<T, COL, ROW>& operator=(const E& expression) {
for (std::size_t y = 0; y != rows(); ++y) {
for (std::size_t x = 0; x != cols(); ++x) {
values[y * COL + x] = expression(x, y);
}
}
return *this;
}
private:
std::vector<T> values;
};