Sức mạnh của template trong C++

Có một số các phép tính toán tuy phức tạp, nhưng với input là những hằng số, nếu lợi dụng template khéo léo, chương trình sẽ chạy rất nhanh.

Trước hết lấy ví dụ đơn giản: tính số Fibonaci thứ 40. Có hai cách dễ thấy ngay: đệ quy, vòng lặp. Giờ ta tìm hiểu cách dùng template:

template<int N> struct TFib
{
	enum
	{
		EVal = TFib<N - 1>::EVal + TFib<N - 2>::EVal
	};
};

Trong code trên, ta định nghĩa một cấu trúc tên là TFib, TFib có template nhận tham số là một hằng N kiểu int. Nhiệm vụ của TFib<N> là tính số Fibonaci thứ N, phản ánh kết quả qua một enum tên là EVal:

EVal = TFib<N - 1>::EVal + TFib<N - 2>::EVal

Một cách đệ quy, compiler sẽ tiếp tục đi định nghĩa TFib<N – 1> và TFib<N – 2> để lấy về các số Fibonaci thứ N-1 và N-2. Điều kiện dừng đệ quy ở đây là khi N=0 hoặc N=1. Trong C++, để định nghĩa một trường hợp cụ thể của một cấu trúc có template, viết như ví dụ sau:

template<> struct TFib<0> { enum { EVal = 0 }; };
template<> struct TFib<1> { enum { EVal = 1 }; };

Để tính số Fibonaci thứ 40, ta chỉ việc viết: int fibo40 = TFib<40>::EVal; Vào lúc compile source code, compiler sẽ đi định nghĩa TFib<40>, TFib<39>, cứ thế… Cho nên code trên sẽ được compiler diễn lại là: int fibo40 = 102334155; Do đó chương trình chúng ta chạy rất nhanh, tuy nhiên lúc compile thì compiler chạy chậm.

Một ví dụ nữa là các hàm lượng giác. Giả sử ta có danh sách các góc radian (mỗi góc từ 0 đến 2PI) như sau:

#define PI 3.14159265358979323846
static const double KListAngle[] = { PI, PI * 0.27372, 1.234, 2.98765 };

Giờ tính sin(KListAngle[i]) bằng cách dùng template:

#define MAX_TERMS 15

// tính sin(KListAngle[I])
template<int I> struct TSin
{
	static inline double val()
	{
		return KListAngle[I] * TSeries<I, 0>::val();
	}
};

// tính term(J)
template<int I, int J> struct TSeries
{
	enum
	{
		NextI = J + 1 == MAX_TERMS ? -1 : I
	};

	static inline double val()
	{
		return 1.0 - KListAngle[I] * KListAngle[I] / (2.0 * J + 2.0) / (2.0 * J + 3.0)
							* TSeries<NextI, J + 1>::val();
	}
};

// trường hợp đặc biệt, dừng đệ quy tại đây
template<> struct TSeries<-1, MAX_TERMS>
{
	static inline double val()
	{
		return 1.0;
	}
};

// làm cho trông giống hàm
#define CalcSin(i) TSin<i>::val()

TSin<I> có nhiệm vụ tính sin(KListAngle[I]). Sở dĩ các hàm val() được viết như ở trên là vì công thức:

sin(x) = x – (x^3 / 3!) + (x^5 / 5!) – (x^7 / 7!) + (x^9 / 9!) – …

trong đó x đo bằng radian, 0 <= x <= 2PI. Công thức này có thể rút gọn lại:

sin(x) = x * term(0)

với term(n) được định nghĩa đệ quy:

term(n) = 1 – x^2 / (2n+2) / (2n+3) * term(n+1)

Khi n càng lớn, sin(x) càng chính xác. Ở đây ta chọn n lớn nhất = MAX_TERMS = 15, đó cũng chính là điều kiện dừng đệ quy. Với MAX_TERMS = 15, độ chính xác của sin(x) đạt tới 15 chữ số thập phân (sau dấu chấm).

Với các phép tính trên ma trận, template càng thể hiện rõ sức mạnh của mình:

//=====================================================================
// Matrix operation

typedef double matrix33[3][3];
typedef double matrix44[4][4];
typedef double matrix10[10][10];

//---------------------------------------------------------------------
// Utils struct

template<class TMatrix, int N> struct TMatrixUtils
{
	static inline void makeZero(TMatrix& mtx)
	{
		TMakeZero<TMatrix, N, 0>::make(mtx);
	}

	static inline void makeIdentity(TMatrix& mtx)
	{
		TMakeIdentity<TMatrix, N, 0>::make(mtx);
	}

	static inline void makeMultiply(TMatrix& mtxC, const TMatrix& mtxA, const TMatrix& mtxB)
	{
		TMakeMultiply<TMatrix, N, 0, 0>::make(mtxC, mtxA, mtxB);
	}
};

//---------------------------------------------------------------------
// Identity

template<class TMatrix, int N, int I> struct TMakeIdentity
{
	enum
	{
		R = I / N,
		C = I % N
	};

	static inline void make(TMatrix& mtx)
	{
		mtx[R][C] = R == C ? 1.0 : 0.0f;
		TMakeIdentity<TMatrix, N, I + 1>::make(mtx);
	}
};

template<> struct TMakeIdentity<matrix33, 3, 3 * 3>
{
	static inline void make(matrix33&) { }
};

template<> struct TMakeIdentity<matrix44, 4, 4 * 4>
{
	static inline void make(matrix44&) { }
};

template<> struct TMakeIdentity<matrix10, 10, 10 * 10>
{
	static inline void make(matrix10&) { }
};

#define MakeIdentityMatrix(TMatrix, N, mtx) TMatrixUtils<TMatrix, N>::makeIdentity(mtx)

//---------------------------------------------------------------------
// Zero

template<class TMatrix, int N, int I> struct TMakeZero
{
	enum
	{
		R = I / N,
		C = I % N
	};

	static inline void make(TMatrix& mtx)
	{
		mtx[R][C] = 0.0;
		TMakeZero<TMatrix, N, I + 1>::make(mtx);
	}
};

template<> struct TMakeZero<matrix33, 3, 3 * 3>
{
	static inline void make(matrix33&) { }
};

template<> struct TMakeZero<matrix44, 4, 4 * 4>
{
	static inline void make(matrix44&) { }
};

template<> struct TMakeZero<matrix10, 10, 10 * 10>
{
	static inline void make(matrix10&) { }
};

#define MakeZeroMatrix(TMatrix, N, mtx) TMatrixUtils<TMatrix, N>::makeZero(mtx)

//---------------------------------------------------------------------
// Multiply

template<class TMatrix, int N, int I, int J> struct TMakeMultiply
{
	enum
	{
		R = I / N,
		C = I % N,
		NextJ = J >= N - 1 ? 0 : J + 1
	};

	static inline void make(TMatrix& mtxC, const TMatrix& mtxA, const TMatrix& mtxB)
	{
		mtxC[R][C] += mtxA[R][J] * mtxB[J][C];
		TMakeMultiply<TMatrix, N, I + 1, NextJ>::make(mtxC, mtxA, mtxB);
	}
};

template<> struct TMakeMultiply<matrix33, 3, 3 * 3, 0>
{
	static inline void make(matrix33&, const matrix33&, const matrix33&) { }
};

template<> struct TMakeMultiply<matrix44, 4, 4 * 4, 0>
{
	static inline void make(matrix44&, const matrix44&, const matrix44&) { }
};

template<> struct TMakeMultiply<matrix10, 10, 10 * 10, 0>
{
	static inline void make(matrix10&, const matrix10&, const matrix10&) { }
};

#define MakeMultiplyMatrix(TMatrix, N, mtxC, mtxA, mtxB) TMatrixUtils<TMatrix, N>::makeMultiply(mtxC, mtxA, mtxB)

void main()
{
	printf("Fib(40) = %d\n\n", CalcFib(40));

	printf("My_Sin(%f) = %.10f\n\n", KListAngle[1], CalcSin(1));
	printf("FP_Sin(%f) = %.10f\n\n", KListAngle[1], sin(KListAngle[1]));

	matrix10 m1;
	MakeIdentityMatrix(matrix10, 10, m1);

	matrix10 m2;
	MakeIdentityMatrix(matrix10, 10, m2);

	matrix10 m3;
	MakeZeroMatrix(matrix10, 10, m3);

	MakeMultiplyMatrix(matrix10, 10, m3, m1, m2);
}

Thực ra thì compiler sẽ diễn dịch MakeIdentityMatrix(matrix10, 10, m1); thành một đống code tuần tự gán từng phần tử của m1. Tương tự như vậy cho MakeZeroMatrix và MakeMultiplyMatrix. Để ý nếu size của ma trận càng lớn thì file .exe được compile ra sẽ có dung lượng càng lớn do đống code sinh ra quá dài.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s