Uso de plantillas. Matematicas Rapidas
Seguro que ya conocias antes las plantillas, y las habias usado a lo mejor para hacer clases genericas, o macros que sean independientes del tipo, etc... Pues bien, las plantillas se pueden utilizar de otro modo mucho mas util para nosotros: como compiladores virtuales. Esto que significa? que podemos optimizar nuestro codigo precompilando gandes cantidades de codigo utilizando las plantillas. Veamos como:
Numeros Fibonacci
Vamos a aplicar las plantillasl para un ejemplo muy sencillo: precompilar la serie de numeros Fibonacci. Esta serie es algo asi como 0, 1, 1, 2, 3, 5, 8, 13, ... La ecuacion general que nos da esta serie es Fib(n) = Fib(n-1) + Fib(n-2).
Pues bien, el modo tipico de resolver esto seria:
unsigned RecursiveFib( unsigned n )
{
if( n<=1 )
return n;
return RecusiveFib( n-1 ) + RecursiveFib( n-2);
}
Aunque no lo parezca, esta funcion nos arruinaria nuestro programa, porque consume tiempo de manera exponencial. Corremos un gran riesgo de colgar nuestro juegog incluso antes de arranque :)
Veamos como seria nuestra version echa con plantillas:
template<unsignned n> struct Fib
{
enum
{
//Definicion recursiva
Val = Fib<N-1>::Val + Fib<N-2>::Val
};
};
//tenemos en cuenta los casos especiales
//condiciones para el fin de la recursividad
template <> struct Fib<0> { enum { Val = 0 }; };
template <> struct Fib<1> { enum { Val = 1 }; };
//hacer que la plantilla parezca una funcion
#define FibT(n) Fib<n>::Val
un ejemplo de como hariamos para llamar a esta plantilla a traves de un #define seria
std::cout <<< FibT( 4 ); //Fib<4>::Val
Vamos a analizar un poco que hemos hecho:
- La function plantilla no es realmente una funcion, sino un integer enumerado llamado Val, el cual se determina recursivamente en tiempo de compilacion. La notacion empleada no es muy comun, pero valida en C++
- Fib la he definido como una estructura para simplificar la notacion. Por defecto los datos de una struct son publicos, justo lo que queremos.
- el parametro de la plantilla N se usa para definir el parametro de entrada de la funcion. Tampoco es muy comun este modo de emplear los parametros de las pllantillas, pero totalmemnte valido. Este parametro se debe conocer el tiempo de compilacion, asi que no hagas un FibT(i) porque dara error, tienes que hacer un FibT(5) por ejemplo.
- Para terminar la recursividad, he empleado un par de par de plantilas "espcializadas" (esto se consigue mediante la notacion template<> )
Visto lo visto, cuando el programa se haya compilado, ya tendremos el valor calculado, y nuestro cout << FibT(4) se habra convertido en cout << 3
Factoriales
Otro ejemplo, calculo de factoriales. Tenemos nuestra funcion de toda la vida:
unsigned RecursiveFact( unsigned n)
{
return( (n<=1) ? 1 : n*RecursiveFact(n-1) ) );
}
y la version mediante plantilla:
template<unsigned N> struct Fact
{
enum { Val = N * Fact <N-1>::Val };
}:
//Especializaciamos para el caso de factorial base
template<> struct Fact <1>
{
enum { Val = 1};
};
//Hacer que la plantilla parezca una funcion
#define FactT( n) Fact<n>::Val
del mismo modo que a antes, nuestro Fact(4) se convierte automaticamemnte en 24.
Trigonometria
Bueno, pues esto todo es muy bonito, de acuerdo. Pero seguro que para calcular el factorial o los fibonacci no hacia falta tanta complicacion. Donde realmente vamos a usar las plantillas de esta manera cuando programemos videojuegos va a ser a la hora de realizar funciones matematicas mas complejas. Vamos a continuar el tutorial viendo un ejemplo no tan sencillo como los anteriores....
casi todos los juegos usan tablas o metodos similares para hacer calculos trigonometricos rapidos. Las funciones estandar trigonometricas hacen uso de unas series de expansion, es decir por poner un ejemplo:
sine(x) = x - (x^3/ 3!) + (x^5 / 5!) - (x^7 / 7!) + (x^9 + 9!) - .... donde x son radianes, 0 <= x < 2µ
debemos reescribir lo anterior de un modo mas "manejable":
sine(x) = x * term(0);
donde term(n) se calcula recurivamente como term(n) = 1 - x^2 / (2n+2) / (2n+3) * term(n+1)
Esto escrito con funciones de toda la vida seria:
double Sine(double fRad)
{
const int iMaxTerms=10;
return fRad * SineSeries (fRad, 0 iMaxTerms)
}
double SineSeries(double fRad, int i, intiMaxTerms)
{
if(i>iMaxTerms)
return 1.0;
return 1.0 - (fRad * fRad / (2.0 * i + 2.0) / (2.0 * i + 3.0) * SineSeries (fRad, i+1, iMaxTerms) );
}
Incrementando el numero iMaxTerms se aumenta la precision, pero se pierde velocidad en la ejecucion por supuesto.
Veamos como quedaria esto con plantillas:
template <double R> struct Sine
{
enum { MaxTerms = 10 }; //incrementa esto para mayor precision
static inline double sin()
{
retrn R * Series<R,0, MaxTerms >::val()(;
}
};
template <double R, int I, int MaxTterrms>
struct Series
{
enum
{
Countinu = I + 1 != Maxterms,
NxtI = ( I + 1 ) * Continue,
NxtMaxTerms = MaxTerms * Continue
};
static inline double val()
{
return 1 - R * R / (2.0 * I + 2.0) / (2.0 * I + 3.0) * Series <R*Continue, NxtI, NxtMaxTrms>::Val();
}
};
template <> struct Series <0.0, 0, 0>
{
static inline double val() { return 1.0; }
};
//para hacer que parezca una funcion
#define SineT(r)Sine<r>::Sin()
Matrices
Por ultimo vamos a ver como usar plantillas para realizar operaciones con las matrices, esto va a a incrementar enormemente la velocidad de nuestros juegos.
Matriz Identidad
La matriz identidad tiene todos los elementos a 0, excepto la diagonal que tiene 1.
esto viene a ser algo asi como
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
:-)
Abajo tienes el codigo que implementa la matriz identidad mediante las plantillas:
//N es el tamano de la matriz
template <class Mtx, unsigned N> struct IdMtx
{
static inline void eval (Mtx& mtx)
{
IdMtxImpl <Mtx, , 0, 0, 0>::eval(mtx);
}
};
//asignar elementos a la matriz
template <cas Mtx, unsigned N, unsigned C, unsigned R, unsignett I>
struct IdMtxImpl
{
enum
{
NxtI = I+1, //Contador
NxtR = NxtI % N, //Fila
NxtC = NxtI / N % N //Columna
};
static inline void eval (Mtx& mtx)
{
mx[C][R] = (C==R) ? 1.0 : 0.0;
IDMtxImpl<Mtx, N, NxtC, NxtI >::eval(mtx);
}
};
//especializar para 3x3 y 4x4
template <> struct IdMtxImpl <matrix33, 3, 0, 0, 3*3>
{
static inline void eval (matrix33&) {}
};
template <> struct IdMtxImpl <matrix44, 4, 0, 0, 4*4>
{
static inline void eval (natrix44&) {}
};
//Hacer que parezca una funcion
#define IdentityMtxT (MtxType, Mtx, N) \ IdMtx <MtxType, N>::evall(Mtx)
de esta forma es el compilador el que desarrolla todo el
bucle. Ademas podemos especifical matrices cuadradas de cualquier tamano:
7matrix33& matrix33::identity()
{
IdentityMtxT(matrix33, *this, 3);
return *this;
}
matrix44& matrix44::identity()
{
IdentityMtxT(matrix44, *this, 4);
return *this;
}
Inicializar Matrices
de la misma tecnica de antes, podemos inicializar matrices de una manera sencilla. Lo unico que debemos hacer es cambiar una linea en el codigo anterior, para que en vez de crear la matriz identidad podamos crear cualquier otra matriz,
Por ejemplo, para inicializar la matriz a 0, utilizariamos el codigo anterior pero cambiando lo sigiente:
mtx[ C ][ R ] = ( C == R ) ?1.0 : 0.0; //matriz identidad
por...
mtx[ C ][ R ] = 0.0; //matriz 0
en una palabra, podemos generaizar asi:
mtx[ C ][ R ] = static_cast< F >(Init); // inicializar la matriz
donde F es el tipo de valor almacenado en cada elemento, y Init es un parametro numerico de plantilla que por defecto es 0. De esta manera podemos inicializar las matrices a cualquier valor.
Transposicion de Matrices
Esto es darle la vuelta a la matriz, utilizando como eje la diagonal.
Veamos el codigo para hacer esto con plantillas:
// N es el tamano de la matriz
template <class Mtx, unsigned N> struct TransMtx
{
static inline void eval( Mtx& mtx )
{
TransMtxImpl <Mtx, N, 0, 1, 0>::eval(mtx);
}
};
template <class Mtx, unsigned N, unsigned C, unsigned R, unsigned I> struct TransMtxImpl
{
enum
{
NxtI = I + 1,
Nxt = NxtI / N % N,
NxtR = (NxtI % N) + NxtC + 1
};
static inlin void eval( Mtx& mtx )
{
if (R<N)
std::swap( mtx[ C ][ R ], mtx[ R ][ C] );
TransMtxImpl< Mtx, N, NxtC, NxtR, NxtI >::eval(mtx);
}
};
// Especializar par 3x3 y 4x4
template<> struct TransMtxImpl< matrix33, 3, 0, 1, 3*3 >
{
static inline void eval( matrix33& ) {}
};
template<> struct TransMtxImpl< matrix44, 4, 0, 1, 4*4 >
{
static inline void eval( matrix44& ) {}
};
// Hacer que la plantitlla parezca una funcion
#define TransMtx( MtxType, Mtx, N ) \ TransMtx< MtxType, N >::eval(Mtx)
Veamos como funciona esto en la practica para tenerlo un poco mas claro:
en vez de usar una funcion tipica para dar la vuelta a la matriz del tipo ...
matrix33& matrix33::transpose()
{
for(unsigned c=0; c<3; c++)
for(unsigned r=c+1; r<3; r++)
std::swap(col[c][r],col[r][c]);
return *this;
}
...utilizaremos esto otro con nuestro sistema de plantillas...
matrix33& matrix33::transpose()
{
TransMtxT(matrix33, *this, 3);
return *this;
}
... que el compilador se encargara de traducir en ...
matrix33& mamtrix33::transpose()
{
std::swap( col[0][1], col[1][0] );
std::swap( col[0][2], col[2][0] );
std::swap( col[1][2], col[2][1] );
return *this;
}
este sistema esta mucho mucho mas optimizado, elimina los for y deja solamente los 3 swap. :)
Multiplicacion de matrices
Por ultimo vamos a ver como se pueden multiplicar matrices tambien utilizando las plantillas:
// N es el tamano de la matriz
template< class Mtx, unsigned N > struct MultMtx
{
static inline void eval( Mtx& r, const Mtx& a, const Mtx& b )
{
MultMtxImpl< Mtx, Nm 0, 0, 0, 0 >::eval(r,a,b);
}
}
template< class Mtx, unsigned N, unsigned C, unsigned R, unsigned K, unsigned I > struct MultMtxImpl
{
enum
{
NtxI = I + 1, //contador
NxtK = NxtI % N, //bucle interno
NxtC = NxtI / N % N //columna
NxtR = NxtI / N / N % N //fila
};
static inline void eval(Mtx& r, const Mtx& a, const Mtx& b)
{
r[C][R] += a[K][R] * b[C][K];
MultMtxImpl<Mtx,N,NxtC, NxtR,NxtK,NxtI>::eval(r,a,b);
}
};
//especializar para 3x3 y 4x4
template <> struct MultMtxImpl< matrix33, 3, 0, 0, 0, 3*3*3 >
{
static inline void eval( matrix33&, const matrix33&, const matrix33& ) {}
};
template <> struct MultMtxImpl< matrix44, 4, 0, 0, 0, 4*4*4 >
static inline void eval( matrix44&, const matrix44&, const matrix44& ) {}
};
// Hacer que parerzca una funcion
#define MultMtxT( MtxType, r, a, b, N ) \ MultMtx <MtxTpe, N>::eval(r,a,b)