为什么C模板计算如此之快?
发布时间:2020-12-16 10:41:41 所属栏目:百科 来源:网络整理
导读:我想知道下一个代码. #include iostreamusing std::cout;templateint N struct Fib { enum { v = FibN - 1::v + FibN - 2::v };};template struct Fib0 { enum { v = 0 };};template struct Fib1 { enum { v = 1 };};int fib(int n) { return n 2 ? n : fib(
我想知道下一个代码.
#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. 解决方法
这是由于模板解决方案中固有的
memoization.
在编译期间,诸如Fib< 1>,Fib< 2>等的每个实例化仅由编译器执行一次并且被记住. 另一方面,当你运行fib(n)时,计算fib(1),fib(2)等多次.解决方案可能是记住它,即记住地图或数组中每个fib调用的结果,如果结果已经存在则返回该结果. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |