Russian Qt Forum

Введение

В данной заметке речь пойдёт об одном из важных применений шаблонного метапрограммирования, а именно о т.н. шаблонах выражений. Шаблоны выражений позволяют кардинально оптимизировать некоторые виды вычислений и при этом сохранить естественную запись математических выражений.
Впервые такое применение шаблонам было найдено в 1994 г. Тоддом Вельдхузеном и Дэвидом Вандерворде. В последствии этот приём был положен в основу таких мат. библиотек как:
Blitz
Matrix Template Library
POOMA
boost ublas
и др.

Для большей ясности, зачем всё это нужно, рассмотрим типичные операции линейной алгебры, такие как сложение, вычитание векторов:

V = c1*V1 + c2*V2 + c3*V3 + c4*V4,

где V1, V2, V3, V4 - вектора, а c1, c2, c3 и c4 - числа.
В примитивной реализации этого выражения создаются временные объекты: вначале для c1*V1, c2*V2, c3*V4 и c4*V4. Затем будут созданы временные объекты (c1*V1 + c2*V2) и (c3*V3 + c4*V4) и в конце будет создан ещё один временный объект для последней суммы.
Если вектора имеют большой размер то затраты на создание и уничтожение временных объектов могут оказаться  неприемлемыми.  
Но с использованием шаблонов выражений можно писать подобные мат. конструкции без создания временных объектов.
Я покажу на примере класса vector, как это можно реализовать.

Реализация Шаблонов выражений на примере класса vector
И так, вначале приведу реализацию класса vector.

C++ (Qt)
template <class, size_t, class, class, class> class expr; // Предварительное объявление класса выражений
 
template <class T, size_t N>
class vector
{
public:
    typedef T value_type;
    typedef T* iterator;
    typedef const T* const_iterator;
    typedef T& reference;
    typedef const T& const_reference;
    typedef size_t size_type;
 
    vector() { m_elems = new T[size()]; }
 
    explicit vector(const T& value) {
        m_elems = new T[size()];
        std::fill(begin(), end(), value);
    }
 
    vector(const vector<T, N>& other) {
        m_elems = new T[size()];
        std::copy(other.begin(), other.end(), begin());
    }
 
    ~vector() { delete [] m_elems; }
 
    vector &operator=(const vector<T, N>& v) {
        if (this != &v) {
            std::copy(v.begin(), v.end(), begin());
        }
        return *this;
    }
 
    template <class L, class R, class F> // Оператор присваивания для шаблонного выражения 
    vector &operator=(const expr<T, N, L, R, F>& expr) {
        for (size_t i = 0; i < N; ++i)
            m_elems[i] = expr[i];
        return *this;
    }
 
    reference operator()(size_type i) throw(std::out_of_range) {
        if (i >= size())
            throw std::out_of_range("specmath::vector<T, N>: index out of range");
 
        return m_elems[i];
    }
 
    const_reference operator()(size_type i) const throw(std::out_of_range) {
        if (i >= size())
            throw std::out_of_range("specmath::vector<T, N>: index out of range");
 
        return m_elems[i];
    }
 
    reference operator[](size_type i) {
        return m_elems[i];
    }
 
    const_reference operator[](size_type i) const {
        return m_elems[i];
    }
 
    static size_type size() { return N; }
    iterator begin() { return m_elems; }
    iterator end() { return m_elems + N; }
    const_iterator begin() const { return m_elems; }
    const_iterator end() const { return m_elems + N; }
 
    vector &operator*=(const T &value) {
        std::transform(begin(), end(), begin(), std::bind2nd(std::multiplies<T>(), value));
        return *this;
    }
 
    vector &operator/=(const T &value) {
        std::transform(begin(), end(), begin(), std::bind2nd(std::divides<T>(), value));
        return *this;
    }
 
    vector &operator+=(const vector<T, N>& v) {
        std::transform(begin(), end(), v.begin(), begin(), std::plus<T>());
        return *this;
    }
 
    vector &operator-=(const vector<T, N>& v) {
        std::transform(begin(), end(), v.begin(), begin(), std::minus<T>());
        return *this;
    }
 
    template <class L, class R, class F>
    vector &operator+=(const expr<T, N, L, R, F>& expr) {
        for (size_t i = 0; i < N; ++i)
            m_elems[i] += expr[i];
        return *this;
    }
 
    template <class L, class R, class F>
    vector &operator-=(const expr<T, N, L, R, F>& expr) {
        for (size_t i = 0; i < N; ++i)
            m_elems[i] -= expr[i];
        return *this;
    }
 
private:
    value_type *m_elems;
};
 
// ...
 
 

Здесь следует обратить внимание на пару тонких моментов.
Во-первых, вначале идёт предварительное объявление шаблонного класса expr, который фактически и будет являться шаблоном выражения. Его реализация будет описана ниже.
Во-вторых, появились дополнительные операторы:

C++ (Qt)
template <class L, class R, class F> // Оператор присваивания для шаблонного выражения 
    vector &operator=(const expr<T, N, L, R, F>& expr) {
        for (size_t i = 0; i < N; ++i)
            m_elems[i] = expr[i];
        return *this;
    }
 
template <class L, class R, class F>
    vector &operator+=(const expr<T, N, L, R, F>& expr) {
        for (size_t i = 0; i < N; ++i)
            m_elems[i] += expr[i];
        return *this;
    }
 
    template <class L, class R, class F>
    vector &operator-=(const expr<T, N, L, R, F>& expr) {
        for (size_t i = 0; i < N; ++i)
            m_elems[i] -= expr[i];
        return *this;
    }
 

 
которые принимают в качестве аргумента наше шаблонное выражение.

Теперь посмотрим на реализацию класса expr:

C++ (Qt)
template <class T, size_t N, class Left, class Right, class F>
class expr
{
public:
    expr(const Left& lhs, const Right& rhs)
        : left(lhs), right(rhs) {}
    T operator[](size_t index) const {
        return _f(left[index], right[index]);
    }
private:
    const Left& left;
    const Right& right;
    F _f;
};
 

Первые два параметра шаблона T и N - определяют тип элементов вектора и его длину. Далее идут параметры Left и Right - это левое и правое выражения, которые нужно объединить в одно выражение. Последний параметр F - задаёт бинарную функцию(std::plus<T>, std::minus<T>, std::multiplies<T> и т.д.) в зависимости от того, какая операция должна быть произведена над выражениями Left и Right.
Конструктор класса expr просто копирует ссылки на объекты Left и Right.
Далее объявляется оператор[] в котором с помощью объекта бинарной функции конструируется итоговое выражение.    

Чтоб было понятно, как это всё работает рассмотрим операцию сложения двух векторов. Для этого определим оператор+

C++ (Qt)
template <class T, size_t N>
const expr<T, N, vector<T, N>, vector<T, N>, std::plus<T> > operator+(const vector<T, N> &x, const vector<T, N> &y)
{
    return expr<T, N, vector<T, N>, vector<T, N>, std::plus<T> >(x, y);
}
 

 
Возвращаемое значение в данном случае представляет из себя не вектор, а шаблонное выражение. при этом временных объектов не создаётся. при создании expr в его конструктор передаются ссылки, которые он просто копирует.
Однако это ещё не всё..
Сейчас мы уже можем писать выражения типа:
V = V1+V2
и это будет работать. Но мы пока не можем написать выражения типа:
V = V1+V2+V3+...
Для этого нужно определить ещё такие операторы+, а именно:
1) вектор + выражение
2) выражение + вектор
3) выражение + выражение

Приведу лишь первый вариант (остальные пишутся аналогично)

C++ (Qt)
template <class T, size_t N, class L, class R, class F>
const expr<T, N, vector<T, N>, expr<T, N, L, R, F>, std::plus<T> > operator+(const vector<T, N> &x, const expr<T, N, L, R, F> &y)
{
    return expr<T, N, vector<T, N>, expr<T, N, L, R, F>, std::plus<T> >(x, y);
}
 

Теперь, после того, как мы реализовали все 4 оператора+ мы спокойно можем писать любые комбинации, наподобии следующих:
v = v1+(V2+V3)+V4+(V5+V6+V7)+V8, и т.д.

Теперь, если аналогично определить оператор- (минус) то мы почти будем у цели) Для этого оператора всё в точности аналогично, нужно лишь везде поменять std::plus<T> на std::minus<T>

C++ (Qt)
template <class T, size_t N>
const expr<T, N, vector<T, N>, vector<T, N>, std::minus<T> > operator-(const vector<T, N> &x, const vector<T, N> &y)
{
    return expr<T, N, vector<T, N>, vector<T, N>, std::minus<T> >(x, y);
}
 
template <class T, size_t N, class L, class R, class F>
const expr<T, N, vector<T, N>, expr<T, N, L, R, F>, std::minus<T> > operator-(const vector<T, N> &x, const expr<T, N, L, R, F> &y)
{
    return expr<T, N, vector<T, N>, expr<T, N, L, R, F>, std::minus<T> >(x, y);
}
 
//...
 
 

 

Теперь осталось реализовать лишь оператор умножения вектора на число и деление на число.
Предлагаю это проделать в качестве самостоятельного задания)

После полной реализации всех операторов мы получаем возможность писать абсолютно любые выражения с нашим вектором. И самое главное, что ещё на этапе компиляции выражение, например вида:

C++ (Qt)
v = a*v1 + a2*(v2+a3*v3)-(v4+v5) + v6*a4
 

 
будет развёрнуто в конструкцию вида:

C++ (Qt)
for (size_t i = 0; i < v.size(); ++i)
    v[i] = a*v1[i] + a2*(v2[i]+a3*v3[i])-(v4[i]+v5[i]) + v6[i]*a4
 

причём без создания и уничтожения дополнительных временных объектов.


Надеюсь, это было кому то полезным)

Исходники с примером приатачены.
 

  

  
    

Ну Вы знаете, достигнутый эффект выглядит слишком мал по сравнению с затраченными усилиями  :) Но в конце-концов почему бы мне не подучить template (которые я знаю плохо) если есть человек который мне охотно объясняет?

Правда пока получается не очень.  Пытаясь осмыслить напр такую соплю

C++ (Qt)
const expr<T, N, vector<T, N>, vector<T, N>, std::minus<T> > operator-(const vector<T, N> &x, const vector<T, N> &y)

я сразу же смертельно устаю :) Ну не все сразу, по крайней мере я уже знаю: в теории избавиться от промежуточных значений можно. Уже хорошо!

Два момента

1) Ну что с именами у Вас никак не ладится  :'( Ну как можно было запрягать имя vector? Назвали бы хоть array, что ли..

2) Есть "векторный процессор" (наск я помню называется SSL). это выглядит это так

C++ (Qt)
if (vectorProcessor) {
 ...               // здесь оперируем с векторами в терминах SSL
}
else                 
for (size_t i = 0; i < v.size(); ++i)   // бананiв нема, то ж скалярна сумма
    v[i] = a*v1[i] + a2*(v2[i]+a3*v3[i])-(v4[i]+v5[i]) + v6[i]*a4
 
 

Мне приходилось писать такой спец код лет 10 назад, так что могу и наврать. Но прирост в производительности там хороший (в разы). А как с этим в Вашей реализации?

А в целом - хороший, конструктивный пост (побольше бы таких). Спасибо

Ну я бы не сказал.. Вообще спорно сравнивать усилия от написания нескольких дополнительных строчек кода (один раз)  с усилиями приложенными в последующем, городить циклы. В последнем случае мы проигрываем в читаемости кода, повышаем риск ошибок, да и время это занимает больше (циклы писать).

C++ (Qt)
const expr<T, N, vector<T, N>, vector<T, N>, std::minus<T> > operator-(const vector<T, N> &x, const vector<T, N> &y)
 

       
Здесь всё не так сложно.. Дело привычки)
Этот оператор возвращает объект expr<T, N, Left, Right, F>
где:
T - тип элементов в векторе
N - размер вектора
Left = vector<T, N>
Right = vector<T, N>
F = std::minus<T>
что означает: нужно взять Left и Right и применить к ним операцию std::minus<T>

Про SSL ничего сказать не могу, поскольку не сталкивался.
В данном случае, на этапе компиляции происходит разворачивание изначального выражения в цикл. Поэтому разницы по скорости выполнения кода, для вручную написанного цикла и тем, что делает этот механизм, очевидно нет.
А вот разница между примитивным вариантом с созданием временных объектов - колосальна и пропорциональна сложности изначального выражения и размера векторов, участвующих в  этом выражении.