18장 표현식 템플릿 Ver 2.01

이 내용은 매우 어려우므로 정신적인 스트레스가 동반될 수 있습니다. 임산부나 노약자는 삼가해 주시기 바랍니다 경고 이 내용은 매우 어려우므로 정신적인 스트레스가 동반될 수 있습니다. 임산부나 노약자는 삼가해 주시기 바랍니다

용어 설명 더러운 코드 : 복잡하거나 직관적으로 보기 어려운 코드 어쩌라고 : 어떤 문제점의 대안이 또 다른 문제점을 야기 했을 때 감탄사

표현식 템플릿 int main() { SArray<double> x(1000), y(1000); //... x = 1.2*x + x*y; } 이런 종류의 연산을 빠르게 처리해 보자

표현식 템플릿 표현식 템플릿 숫자 배열 클래스를 지원하기 위해 고안된 템플릿 프로그래밍 기술 표현식 템플릿과 템플릿 메타프로그래밍이 유사함 재귀적 인스턴스화 템플릿 메타프로그래밍 - 작고 고정된 크기 배열 연산 표현식 템플릿 - 중간에서 큰 크기의 배열을 실시간으로 연산

진행 순서 단순 배열 클래스 구현하여 배열 연산 문제 제기 표현식 템플릿 구현 표현식 템플릿을 아는 랩퍼클래스와 연산자 구현 실재 표현식 템플릿 사용해서 동작 방법 추적

단순 배열 클래스 배열처럼 사용할 수 있는 클래스 만들어 봅시다 생성자 복사생성자 소멸자 할당연산자 크기반환 인덱스[] 연산자 배열처럼 사용할 수 있는 클래스 만들어 봅시다 생성자 복사생성자 소멸자 할당연산자 크기반환 인덱스[] 연산자 클래스이면 당연히 있어야 할 것 배열처럼 사용하기에 있어야 할 것

단순 배열 클래스 template<typename T> class SArray { public: explicit SArray (size_t s) //생성자 : storage(new T[s]), storage_size(s) init(); }

단순 배열 클래스 SArray (SArray<T>const& orig ) //복사생성자 :storage(new T[orig.size()]) ,storage_size(orig.size()) { copy(orig); }

단순 배열 클래스 ~SArray() //소멸자 { delete[] storage; }

단순 배열 클래스 //할당연산자 SArray<T>& operator= (SArray<T>const& orig) { if (&orig!=this) copy(orig); } return *this;

단순 배열 클래스 //크기반환 size_t size() const { return storage_size; }

단순 배열 클래스 //인덱스연산자 T operator[] (size_t idx) const { return storage[idx]; } T& operator[] (size_t idx)

단순 배열 클래스 protected: //생성자 보조함수 void init() { for (size_t idx = 0; idx<size(); ++idx) storage[idx] = T(); }

단순 배열 클래스 //복사 생성자와 할당 연산자 보조함수 void copy (SArray<T> const& orig) { assert(size()==orig.size()); for (size_t idx = 0; idx<size(); ++idx) storage[idx] = orig.storage[idx]; }

단순 배열 클래스 //멤버변수 private: T* storage; size_t storage_size; };

단순 배열 클래스 덧셈연산 template<typename T> SArray<T> operator+ (SArray<T> const& a, SArray<T> const& b) { SArray<T> result(a.size()); for (size_t k = 0; k<a.size(); ++k) { result[k] = a[k]+b[k]; } return result; 배열…

단순 배열 클래스 곱셈연산 template<typename T> SArray<T> operator* (SArray<T> const& a, SArray<T> const& b) { SArray<T> result(a.size()); for (size_t k = 0; k<a.size(); ++k) { result[k] = a[k]*b[k]; } return result; 배열…

단순 배열 클래스 스칼라와 곱셈연산 template<typename T> SArray<T> operator* (T const& s, SArray<T> const& a) { SArray<T> result(a.size()); for (size_t k = 0; k<a.size(); ++k) { result[k] = s*a[k]; } return result; 배열…

단순 배열 클래스 int main() { SArray<double> x(1000), y(1000); //... x = 1.2*x + x*y; }

단순 배열 클래스 비효율 연산자의 모든 응용(할당 제외)은 적어도 하나의 임시 배열을 생성 연산자의 모든 응용은 인자와 결과 배열에 대해 부가적으로 탐색

단순 배열 클래스 tmp1 = 1.2*x; //1000번의 연산 위한 루프 //tmp1 생성하고 소멸 tmp2 = x*y; //1000번의 연산 위한 루프 //tmp2 생성하고 소멸 tmp3 = tmp1+tmp2; //1000번의 연산 위한 루프 //tmp3 생성하고 소멸 x = tmp3; // 1000번 읽기 연산 // 1000번 쓰기 연산

임시배열을 줄여보자 +,* 연산 대신 +=, *= 연산으로 임시배열을 줄여보자

단순 배열 클래스 template<class T> SArray<T>& SArray<T>::operator+= (SArray<T> const& b) { for (size_t k = 0; k<size(); ++k) { (*this)[k] += b[k]; } return *this;

단순 배열 클래스 template<class T> SArray<T>& SArray<T>::operator*= (SArray<T> const& b) { for (size_t k = 0; k<size(); ++k) { (*this)[k] *= b[k]; } return *this;

단순 배열 클래스 template<class T> SArray<T>& SArray<T>::operator*= (T const& s) { for (size_t k = 0; k<size(); ++k) { (*this)[k] *= s; } return *this;

단순 배열 클래스 int main() { SArray<double> x(1000), y(1000); //... // process x = 1.2*x + x*y SArray<double> tmp(x); tmp *= y; x *= 1.2; x += tmp; }

단순 배열 클래스 문제점 표기방식이 보기에 이상하다 여전히 임시 tmp라는 배열이 필요하다 루프가 많은 연산에 분할돼 있기 때문에 메모리에서 double 요소를 읽는 횟수가 대략 6000회, double를 메모리에 쓰는 횟수는 4000번에 달함

아 놔~! 어쩌라고~!

우리가 원하는 계산 방식 int main() { SArray <double> x(1000), y(1000); //... for ( int idx = 0; idx < x.size(); ++idx ) x[idx] = 1.2*x[idx] + x[idx]*y[idx]; }

이걸 어떻게 해~!

진행 순서 단순 배열 클래스 구현하여 배열 연산 문제 제기 표현식 템플릿 구현 표현식 템플릿을 아는 랩퍼클래스와 연산자 구현 실재 표현식 템플릿 사용해서 동작 방법 추적

템플릿 인자에 표현식 표현 전체 표현식을 다 읽기 전에 표현식의 일부만 계산하지 않는다면 해결할 수 있다 (이번 예에서 할당 연산자 호출 될 때 까지) 계산 하기 전에 어떤 객체에 무슨 연산이 적용 됐는지 기록해둬야 한다 P.327

템플릿 인자에 표현식 표현 + A_Add * * A_Mult A_Scalar 1.2 x x y

( ( ) ( ) ) + * 1.2 x * x y 템플릿 인자에 표현식 표현 Prifix 트리 순회 방식 A_Add A_Mult A_Scalar A_Mult

템플릿 인자에 표현식 표현 1.2*x + x*y; 계산 결과 데이터 타입 A_Add< A_Mult<A_Scalar<double>,Array<double> >, A_Mult<Array<double>,Array<double> > > 아 이거 왜케 더럽게 생겼냐?

뚫어지게 쳐다봐 주세요~!

표현식 템플릿의 피연산자 template <typename T, typename OP1, typename OP2> class A_Add { private: // 나중에 알려드립니다 typename A_Traits<OP1>::ExprRef op1; typename A_Traits<OP2>::ExprRef op2;

표현식 템플릿의 피연산자 public: //생성자 //두개의 피연산자를 저장합니다 A_Add (OP1 const& a, OP2 const& b) : op1(a), op2(b) { }

표현식 템플릿의 피연산자 //할당 연산자 T operator[] (size_t idx) const { return op1[idx] + op2[idx]; } //계산 하기 전에 어떤 객체에 무슨 연산이 적용됐는지 기록해둬야 한다

표현식 템플릿의 피연산자 size_t size() const { assert (op1.size()==0 || op2.size()==0 || op1.size()==op2.size() ); return op1.size()!=0 ? op1.size() : op2.size(); } };

표현식 템플릿의 피연산자 template <typename T, typename OP1, typename OP2> class A_Mult { private: //나중에.. typename A_Traits<OP1>::ExprRef op1; typename A_Traits<OP2>::ExprRef op2;

표현식 템플릿의 피연산자 public: //생성자 //두개의 피연산자를 저장합니다 A_Mult (OP1 const& a, OP2 const& b) : op1(a), op2(b) { }

표현식 템플릿의 피연산자 //할당 연산자 T operator[] (size_t idx) const { return op1[idx] * op2[idx]; } //계산 하기 전에 어떤 객체에 무슨 연산이 적용됐는지 기록해둬야 한다

표현식 템플릿의 피연산자 size_t size() const { assert (op1.size()==0 || op2.size()==0 || op1.size()==op2.size() ); return op1.size()!=0 ? op1.size() : op2.size(); } };

표현식 템플릿의 피연산자 template <typename T> class A_Scalar { private: T const& s; public: A_Scalar (T const& v) : s(v) { } T operator[] (size_t) const { return s; } size_t size() const { return 0; }; };

표현식 템플릿의 피연산자 계산 하기 전에 어떤 객체에 무슨 연산이 적용 됐는지 기록해둬야 한다 T operator[] (size_t idx) const { return op1[idx] + op2[idx]; } { return op1[idx] * op2[idx]; }

A_Add, A_Mult 의미 외부 내부 두 피연산자 인 배열객체가 연산된 결과를 담고 있는 클래스 두 피연산자를 저장하고 어떤 연산을 하는지 기록된 클래스

표현식 템플릿의 피연산자 대부분의 임시 노드들은 최상위 표현식과 관련이 있기 때문에 전체 표현식을 모두 계산할 때 까지 계속 살아남아야 한다 A_Scalar 노드는 예외다 이들은 연산자 함수에 연결되며 전체 표현식의 계산이 종료 전에 사라진다 스칼라 피연산자는 값으로 복사돼야만 한다. typename A_Traits<OP1>::ExprRef op1; typename A_Traits<OP2>::ExprRef op2;

표현식 템플릿의 피연산자 template <typename T> class A_Traits { public: typedef T const& ExprRef; }; class A_Traits<A_Scalar<T> > public: typedef A_Scalar<T> ExprRef;

진행 순서 단순 배열 클래스 구현하여 배열 연산 문제 제기 표현식 템플릿 구현 표현식 템플릿을 아는 랩퍼클래스와 연산자 구현 실재 표현식 템플릿 사용해서 동작 방법 추적

Array형 실제 저장소를 제어하고 표현식 템플릿에 대해 아는 Array형 및 연산자 만들기 쉽게 얘기해서 "레퍼클래스" 만들어 보자

점점 귀찮아진다~!

Array형 template <typename T, typename Rep = SArray<T> > class Array { private: Rep expr_rep; public: //생성자 explicit Array (size_t s) : expr_rep(s) { } //복사 생성자 Array (Rep const& rb) : expr_rep(rb) { }

Array형 //할당연산자 Array& operator= (Array const& b) { assert(size()==b.size()); for (size_t idx = 0; idx<b.size(); ++idx) expr_rep[idx] = b[idx]; } return *this;

Array형 template<typename T2, typename Rep2> Array& operator= (Array<T2, Rep2> const& b) { assert(size()==b.size()); for (size_t idx = 0; idx<b.size(); ++idx) expr_rep[idx] = b[idx]; } return *this; } //다른 타입에 대한 할당 연산자

Array형 //크기 반환 size_t size() const { return expr_rep.size(); }

Array형 T operator[] (size_t idx) const { assert(idx<size()); return expr_rep[idx]; } T& operator[] (size_t idx)

Array형 Rep const& rep() const { return expr_rep; } Rep& rep() };

점점 깊이 들어간다…

코드가 참 어렵습니다 class A { public: A(B const& b) {} }; class B { public: B(C const& c, D const& d) {} A f(C const& c, D const& d) { return A(B(c,d)); }

덧셈 연산자 template <typename T, typename R1, typename R2> Array<T, A_Add<T,R1,R2> > operator+ (Array<T,R1> const& a, Array<T,R2> const& b) { return Array<T, A_Add<T,R1,R2> > (A_Add<T,R1,R2>(a.rep(),b.rep())); }

생성자 코드 Array<T, > ( ); A_Add<T,R1,R2> ( ); A_Add<T,R1,R2> A_Add<T,R1,R2>( ) a.rep(),b.rep()

operator+ Array Array SArray SArray Array Array A_Add A_Scalar SArray

곱셈 연산자 template <typename T, typename R1, typename R2> Array<T, A_Mult<T,R1,R2> > operator* (Array<T,R1> const& a, Array<T,R2> const& b) { return Array<T, A_Mult<T,R1,R2> > (A_Mult<T,R1,R2>(a.rep(), b.rep())); }

operator* Array Array SArray SArray Array Array A_Mult A_Scalar SArray

스칼라 곱셈 연산자 template <typename T, typename R2> Array<T, A_Mult<T,A_Scalar<T>,R2> > operator* (T const& s, Array<T,R2> const& b) { return Array<T,A_Mult<T,A_Scalar<T>,R2> > (A_Mult<T,A_Scalar<T>,R2>(A_Scalar<T>(s), b.rep())); }

operator* Array SArray double Array Array A_Mult A_Scalar double

점점 안드로메다로~!

진행 순서 단순 배열 클래스 구현하여 배열 연산 문제 제기 표현식 템플릿 구현 표현식 템플릿을 아는 랩퍼클래스와 연산자 구현 실재 표현식 템플릿 사용해서 동작 방법 추적

연산을 추적 해보자 int main() { Array<double> x(1000), y(1000); //... x = 1.2*x + x*y; }

연산을 추적 해보자 1.2*x (double, Array<double, Sarray<double> >) template <typename T, typename R2> Array<T, A_Mult<T,A_Scalar<T>,R2> > operator* (T const& s, Array<T,R2> const& b) { return Array<T,A_Mult<T,A_Scalar<T>,R2> > (A_Mult<T,A_Scalar<T>,R2>(A_Scalar<T>(s), b.rep())); }

operator* Array SArray double Array Array A_Mult A_Scalar double

연산을 추적 해보자 x*y (Array<double, Sarray<double> >) template <typename T, typename R1, typename R2> Array<T, A_Mult<T,R1,R2> > operator* (Array<T,R1> const& a, Array<T,R2> const& b) { return Array<T, A_Mult<T,R1,R2> > (A_Mult<T,R1,R2>(a.rep(), b.rep())); }

operator* Array Array SArray SArray Array Array A_Mult A_Scalar SArray

연산을 추적 해보자 1.2*x + x*y template <typename T, typename R1, typename R2> Array<T, A_Add<T,R1,R2> > operator+ (Array<T,R1> const& a, Array<T,R2> const& b) { return Array<T, A_Add<T,R1,R2> > (A_Add<T,R1,R2>(a.rep(),b.rep())); }

operator+ Array A_Mult A_Scalar double SArray Array A_Mult A_Scalar A_Add A_Mult A_Scalar double SArray Array A_Add A_Mult A_Scalar double SArray A_Mult A_Scalar SArray

연산을 추적 해보자 template<typename T2, typename Rep2> Array& operator= (Array<T2, Rep2> const& b) { assert(size()==b.size()); for (size_t idx = 0; idx<b.size(); ++idx) expr_rep[idx] = b[idx]; } return *this;

template <typename T, typename Rep = SArray<T> > class Array { T& operator[] (size_t idx) { assert(idx<size()); return expr_rep[idx]; } }; Array A_Add A_Mult A_Scalar double SArray

연산을 추적 해보자 template <typename T, typename OP1, typename OP2> class A_Add { public: //할당 연산자 T operator[] (size_t idx) const { return op1[idx] + op2[idx]; } }; A_Add A_Mult A_Scalar double SArray

연산을 추적 해보자 template <typename T, typename OP1, typename OP2> class A_Mult { public: //할당 연산자 T operator[] (size_t idx) const { return op1[idx] * op2[idx]; } }; A_Mult A_Scalar double SArray

연산을 추적 해보자 //실질적인 연산과정 for (size_t idx = 0; idx<b.size(); ++idx) { x[idx]= (1.2*x[idx]) + (x[idx]*y[idx]); }

좋아 복잡했지만 그래도 끝냈다

잠깐만요 아직 끝나지 않았습니다!!

표현식 템플릿 할당 Array 클래스는 랩퍼 클래스로 배열연산이 가능했습니다 그런데 다시 한번 살펴 볼까요???

표현식 템플릿 할당 다시 말해 A + B = C 라는 코드가 가능하나요? 이 녀석은 할당이 가능합니다 Array SArray 이 녀석은 할당이 가능합니다 Array A_Add or A_Mult A_Scalar SArray 이 녀석은 할당이 가능하나요? 다시 말해 A + B = C 라는 코드가 가능하나요?

표현식 템플릿 할당 결과로의 할당이 가능한 다른 표현식 템플릿을 만들자 예를 들어 정수값의 배열을 인덱스로 사용하는 것은 하위 집합의 선택

표현식 템플릿 할당 x[y] = 2*x[y]; 이거도 해보고 싶어요 그러니깐 for ( int idx = 0; idx < x.size(); ++idx ) { x[ y[idx] ] = 2*x[ y[idx] ]; }

표현식 템플릿 할당 template<typename T, typename A1, typename A2> class A_Subscript { public: A_Subscript (A1 const& a, A2 const& b) : a1(a), a2(b) { }

표현식 템플릿 할당 T operator[] (size_t idx) const { return a1[a2[idx]]; } T& operator[] (size_t idx)

표현식 템플릿 할당 size_t size() const { return a2.size(); } private: A1 const& a1; A2 const& a2; };

표현식 템플릿 할당 template < typename T2, typename R2> inline Array<T, A_Subscript<T, R, R2> > Array<T, R>::operator[](Array<T2, R2> const& b) { return Array<T, A_Subscript<T, R, R2> > (A_Subscript<T, R, R2>(*this, b)); }

표현식 템플릿의 성능과 한계 표현식 템플릿이라는 아이디어는 상당히 복잡하지만 배열 연산의 성능을 굉장히 향상 시킨다 서로를 호출하는 작은 인라인 함수가 많고 표현식 템플릿은 호출 스택에 할당됐다 인라인 처리와 작은 객체 제거가 관건

표현식 템플릿의 성능과 한계 모든 문제 상황을 해결하진 않음 행렬 벡터 곱셈 x = A*x x는 크기 n, A는 크기 n*n 달라지기 때문에 임시변수가 필요하다

표현식 템플릿의 성능과 한계 표현식 템플릿의 데이터형에 트리를 표현하는것이 아니라 표현식 트리를 나타내는 실행 시간 구조를 생성해야만 하는 것이다 람다라이브러리 http://www.boost.org/doc/libs/1_49_0/doc/html/lambda.html

감사합니다 페이지가 97페이지…