Я написал программу вычисления числа Фибоначчи во время компиляции (constexpr) проблема с использованием методов метапрограммирования шаблонов, поддерживаемых в С++ 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));
}
Я запускал обе программы для N = 40 в моей системе GNU/Linux и измерял время и что это обычное решение (1,15 секунды) примерно в два раза медленнее, чем решение на основе шаблонов (0,55 секунды). Это значительное улучшение, поскольку оба подхода основаны на рекурсии.
Чтобы понять это, я скомпилировал программу (-fdump-tree-all) в g++ и обнаружил, что компилятор фактически сгенерировал 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
для обеих программ.