BLOG C++

Esse é o verdadeiro Fibonacci em C++…

Lógico que no post anterior sobre o desempenho do Java o objetivo não era calcular Fibonacci, mas mostrar que em chamadas recursivas o otimizador do Java leva a melhor. Uma implementação de Fibonacci em C++ usando este algoritmo recursivo,  sem passar para outros algoritmos mais óbvios como manter os dois últimos valores ou somar em um vetor, deve usar uma característica funcional da linguagem C++: a metaprogramação.

Este é o primeiro  post sobre metaprogramação que faço, mas é o exemplo clássico, muito simples e que causa um impacto enorme…

#include <iostream>;

using namespace std;

template<int n>
struct Fib {
  enum X { value = Fib<n-1>::value + Fib<n-2>::value };
};
template <>
struct Fib<1> {
  enum X { value = 1 };
};

template <>
struct Fib<0> {
  enum X { value = 0 };
};

int main(int argc, char *argv[]) {
  cout << Fib<45>::value << endl;
  return 0;
}

Tempo de execução: 0.01 segundo!

Às vezes 0.00 segundo (o sistema não conseguiu medir…). E o tempo de compilação foi normal, 0.58 segundos. Bom, esse programa não é genérico o suficiente para calcular para n, apenas para uma constante conhecida a tempo de compilação. Mas é um recurso do C++, e a gente programa em C++ para usar todos os recursos que a linguagem oferece.  É rápido por que é calculado em tempo de compilação. Não torna a compilação mais lenta pois o compilador instancia Fib<x> apenas uma vez e reaproveita o valor nas vezes seguintes.

Mas também é possível fazer um Fibonacci recursivo para qualquer n mesmo que ele não seja conhecido durante a compilação.

using namespace std;

template <int n>
struct FIB {
  enum X { value = FIB<n-1>::value + FIB<n-2>::value };

  static int generico( int k ) {
    return k > n ? FIB<n>::generico( k-1 ) + FIB<n>::generico( k-2 ) : especifico( k );
  }

  static int especifico( int k ) {
    return k == n ? value : FIB<n-1>::especifico( k );
  }
};

template <>
struct FIB<0> {
  enum X { value = 0 };

  static int especifico( int k ) { return 0; }
};

template <>
struct FIB<1> {
  enum X { value = 1 };

  static int especifico( int k ) {return k == 1 ? value : FIB<0>::especifico( k ); }
};

inline int fib( const int n ) {
  return FIB<15>::generico( n );
}

int main(int argc, char *argv[])
{
  cout << fib( 45 ) << endl;
  return 0;
}

No exemplo acima o tempo de execução foi de 0.03 segundo. O pulo do gato é o 15 na função fib. Ele instancia a série para os 15 primeiros elementos. Detalhe que esse número é configurável durante a compilação somente. Mas de qualquer forma o programa funciona usando o mesmo algoritmo original – só que muito mais rápido.

Foi uma mistura de metaprogramação com programação. Uma possibilidade do C++, que a gente usa de acordo com o problema em questão…

“Nunca diga nunca!”