c++ - 在 C++11 中的编译时 (constexpr) 计算斐波那契数(递归方法)

Question

我在编译时写了斐波那契数计算程序(constexpr) 使用 C++11 支持的模板元编程技术的问题。目的 这是为了计算模板元编程方法与旧的传统方法之间的运行时间差异。

// 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> ...斐波那契<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中调试了程序，发现上面的函数都是 执行次数与传统递归方法相同。 如果程序的两个版本执行函数的次数相同(递归)，那么模板元编程技术如何实现这一点？我还想知道您对基于模板元编程的方法如何以及为什么与其他版本相比花费一半时间的看法？这个程序可以比当前程序更快吗？

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

我的机器是 GNU/Linux 和 GCC 4.8.1，我对这两个程序都使用了优化 -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>()在编译时，但不需要。在您的情况下，全部或部分计算留给运行时。在我的例子中，所有计算都在编译时尝试，因此永远不会结束。