Metaprogramação X SPOJ

A metaprogramação por template é uma técnica de metaprogramação usada pelo compilador para  gerar um código fonte temporário que é acoplado ao resto do código fonte para ser compilado depois. A saída desse templates podem ser constante em tempo de compilação, estrutura de dados ou funções completas. O uso de templates pode ser pensando como uma execução em tempo de compilação.  

No blog do ricbit, ele sugere que é possível utilização da metaprogramação através de templates para transferir partes das tarefas que são realizadas em tempo de execução para tempo de compilação e, assim, diminuir o tempo de execução no spoj. Eu resolvi testar essa idéia em um problema simples do spoj:

http://br.spoj.pl/problems/FATORIA2/

Primeiramente, vamos considerar a versão mais lenta do algoritmo:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

unsigned int factorial(unsigned int n)

{

    if (n == 0)

      return 1;

    return n * factorial(n - 1);

}

int main(){

     unsigned int n;

     scanf("%u",&n);

     printf("%d\n",factorial(n));

     return 0;

}

O tempo de execução no spoj é 0.03 (o tempo de execução do spoj nem sempre é muito confiável :( ).

A versão mais rápida seria pré-calcular previamente todos os valores do fatorial:

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <string.h>

int n;

unsigned int fat[13];

int main(){

    fat[0] = 1;

    fat[1] = 1;

    fat[2] = 2;

    fat[3] = 6;

    fat[4] = 24;

    fat[5] = 120;

    fat[6] = 720;

    fat[7] = 5040;

    fat[8] = 40320;

    fat[9] = 362880;

    fat[10] = 3628800;

    fat[11] = 39916800;

    fat[12] = 479001600;

    scanf("%d",&n);

    printf("%u\n",fat[n]);

    return 0;

}

O menor tempo de execução do spoj foi 0.01s.

Podemos definir um programa usando metaprogramação com o mesmo tempo de execução da seguinte maneira:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};
 
template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

int n;
unsigned int fat[13];

int main(){
 
 fat[0] = Factorial<0>::value;
 fat[1] = Factorial<1>::value;
 fat[2] = Factorial<2>::value;
 fat[3] = Factorial<3>::value;
 fat[4] = Factorial<4>::value;
 fat[5] = Factorial<5>::value;
 fat[6] = Factorial<6>::value;
 fat[7] = Factorial<7>::value;
 fat[8] = Factorial<8>::value;
 fat[9] = Factorial<9>::value;
 fat[10] = Factorial<10>::value;
 fat[11] = Factorial<11>::value;
 fat[12] = Factorial<12>::value;
 scanf("%d",&n);
 printf("%u\n",fat[n]);
        return 0;
}

Os valores de cada fat[i] é substituído por um valor constante calculado em tempo de compilação.

Uma versão mais enxuta do código acima, seria essa aqui:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};
 
template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

int n;
unsigned int fat[13]={
#define f(n) Factorial<n>::value
f(0),f(1),f(2),
f(3),f(4),f(5),
f(6),f(7),f(8),
f(9),f(10),f(11),
f(12)
};
int main(){
 
 scanf("%d",&n);
 printf("%u\n",fat[n]);
              return 0;
}