Russian Qt Forum
Ноябрь 23, 2024, 17:46 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: Шаблоны выражений  (Прочитано 4177 раз)
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« : Апрель 06, 2012, 11:34 »

Введение

В данной заметке речь пойдёт об одном из важных применений шаблонного метапрограммирования, а именно о т.н. шаблонах выражений. Шаблоны выражений позволяют кардинально оптимизировать некоторые виды вычислений и при этом сохранить естественную запись математических выражений.
Впервые такое применение шаблонам было найдено в 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
 
причём без создания и уничтожения дополнительных временных объектов.


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

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

  

  
    
« Последнее редактирование: Апрель 06, 2012, 14:21 от m_ax » Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #1 : Апрель 06, 2012, 17:10 »

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

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 = a*v1 + a2*(v2+a3*v3)-(v4+v5) + v6*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 назад, так что могу и наврать. Но прирост в производительности там хороший (в разы). А как с этим в Вашей реализации?

А в целом - хороший, конструктивный пост (побольше бы таких). Спасибо
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #2 : Апрель 06, 2012, 17:48 »

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

Код
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>

Цитировать
Мне приходилось писать такой спец код лет 10 назад, так что могу и наврать. Но прирост в производительности там хороший (в разы). А как с этим в Вашей реализации?
Про SSL ничего сказать не могу, поскольку не сталкивался.
В данном случае, на этапе компиляции происходит разворачивание изначального выражения в цикл. Поэтому разницы по скорости выполнения кода, для вручную написанного цикла и тем, что делает этот механизм, очевидно нет.
А вот разница между примитивным вариантом с созданием временных объектов - колосальна и пропорциональна сложности изначального выражения и размера векторов, участвующих в  этом выражении.
 
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.353 секунд. Запросов: 23.