在C++ 11中计算编译时(fibtexpr)中的Fibonacci数(递归方法)

Question

我使用C++ 11中支持的模板元编程技术在编译时(constexpr)问题中编写了Fibonacci数计算程序.这样做的目的是计算模板元编程方法和旧的传统方法之间的运行时间差异.

// Template Metaprograming Approach
template<int  N>
constexpr int fibonacci() {return fibonacci<N-1>() + fibonacci<N-2>(); }
template<>
constexpr int fibonacci<1>() { return 1; }
template<>
constexpr int fibonacci<0>() { return 0; }



// Conventional Approach
 int fibonacci(int N) {
   if ( N == 0 ) return 0;
   else if ( N == 1 ) return 1;
   else
      return (fibonacci(N-1) + fibonacci(N-2));
} 

我在GNU/Linux系统上运行N = 40的两个程序并测量时间,发现传统解决方案(1.15秒)比基于模板的解决方案(0.55秒)慢两倍左右.这是一个重大改进,因为这两种方法都基于递归.

为了更好地理解它,我用g ++ 编译了程序(-fdump-tree-all标志),发现编译器实际上生成了40个不同的函数(如fibonacci <40>,fibonacci <39> ... fibonacci <0>).

constexpr int fibonacci() [with int N = 40] () {
  int D.29948, D.29949, D.29950;
  D.29949 = fibonacci<39> ();
  D.29950 = fibonacci<38> ();
  D.29948 = D.29949 + D.29950;
  return D.29948;
}

constexpr int fibonacci() [with int N = 39] () {
  int D.29952, D.29953, D.29954;
  D.29953 = fibonacci<38> ();
  D.29954 = fibonacci<37> ();
  D.29952 = D.29953 + D.29954;
  return D.29952;
}
...
...
...
constexpr int fibonacci() [with int N = 0] () {
  int D.29962;
  D.29962 = 0;
  return D.29962;
}

我还在GDB中调试了程序,发现所有上述函数的执行次数与传统的递归方法相同.如果程序的两个版本执行函数的次数相同(递归),那么这是如何通过模板元编程技术实现的呢？我还想知道您对基于模板元编程的方法与其他版本相比如何以及为什么花费半个时间的意见？这个程序可以比现在更快吗？

基本上我的目的是尽可能地了解内部发生的事情.

我的机器是带有GCC 4.8.1的GNU/Linux,我使用了-o3两个程序的优化.

Answer 1

试试这个:

template<size_t N>
struct fibonacci : integral_constant<size_t, fibonacci<N-1>{} + fibonacci<N-2>{}> {};

template<> struct fibonacci<1> : integral_constant<size_t,1> {};
template<> struct fibonacci<0> : integral_constant<size_t,0> {};

使用clang和-Os,这可以在大约0.5秒内编译并在零时间内运行N=40.您的"常规"方法大约编写为0.4秒,运行时间为0.8秒.只是为了检查,结果是102334155对的？

当我尝试你自己的constexpr解决方案时,编译器运行了几分钟,然后我停止了它,因为显然内存已满(计算机开始冻结).编译器试图计算最终结果,并且您的实现在编译时使用效率极低.

有了这个解决方案,在模板实例N-2,N-1被实例化时重新使用N.因此,fibonacci<40>在编译时实际上将其称为值,并且在运行时无需执行任何操作.这是一个动态规划方法,当然,如果你在存储所有的值,你可以做在运行时相同0,通过N-1在计算之前N.

使用您的解决方案,编译器可以fibonacci<N>()在编译时进行评估,但不是必需的.在您的情况下,全部或部分计算留给运行时.在我的例子中,所有计算都是在编译时尝试的,因此永远不会结束.

Answer 2

原因是您的运行时解决方案不是最佳的.对于每个fib数,函数被调用几次.斐波那契序列具有重叠的子问题,例如fib(6)调用fib(4)和fib(5)调用fib(4).

基于模板的方法使用(无意中)动态编程方法,意味着它存储先前计算的数字的值,避免重复.所以,在fib(5)通话时fib(4),数字已经计算好fib(6)了.

我建议查找"动态编程斐波纳契"并尝试这一点,它应该大大加快速度.