c++ - 为什么 C++ 模板计算如此之快？

Question

我想知道下一个代码。

#include <iostream>
using std::cout;
template<int N> struct Fib {
    enum { v = Fib<N - 1>::v + Fib<N - 2>::v };
};
template<> struct Fib<0> {
    enum { v = 0 };
};
template<> struct Fib<1> {
    enum { v = 1 };
};
int fib(int n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
int main() {
    cout << Fib<46>::v << '\n';
//    cout << fib(46) << '\n';
    return 0;
}

它在编译时计算结果，没有任何明显的延迟。这怎么可能？如果我们使用对 fib(46) 的调用，即使使用最快的 PC，我们也将不得不等待几秒钟。该模板使用相同的计算模式，并且可以立即生成。令我惊讶的是，使用模板生成的可执行文件的大小与不使用模板时几乎一样。我用的是 GCC。

Answer 1

这是由于固有 memoization 在模板解决方案中。

在编译期间，每个实例化如Fib<1> , Fib<2>等(由编译器)仅执行一次并记住。

当你运行 fib(n)另一方面，fib(1) , fib(2)等计算了很多次。解决方案可能是记住它，即记住每个 fib 的结果。调用映射或数组，如果结果已存在则返回。