跳到主要内容

模板元编程：斐波那契数列

Sol
Sol
千里之行，始于足下。

在编程中，斐波那契数列是一个经典的数学问题。通常情况下，我们可以使用传统递归函数来计算斐波那契数列。但是运行时计算递归会造成比较长的耗时。

模板元编程可以解决这个问题，在编译时计算斐波那契数列，从而提高执行效率。

斐波那契数列有两种：

  • 从 00 开始： 0,1,1,2,3,5,8,...0,1,1,2,3,5,8,...
  • 从 11 开始： 1,1,2,3,5,8,...1,1,2,3,5,8,...

我们假设从 00 开始，即 f(0)=0，f(1)=1，f(2)=1，... f(0) = 0，f(1) = 1，f(2) = 1，...。

传统递归​

/**
 * @file fibonacci_recursive.cpp
 * @brief calculate fibonacci value recursively
 */
#include <iostream>

unsigned int calc_fibonacci(unsigned int i) {
    if (i == 0 || i == 1) {
        return i;
    }
    return calc_fibonacci(i - 1) + calc_fibonacci(i - 2);
};

int main() {
    std::cout << calc_fibonacci(42) << '\n';
    return 0;
}
> g++ -O0 -g a.out fibonacci_recursive.cpp -o prog_fibonacci_recursive

> ./prog_fibonacci_recursive
267914296

> hyperfine "./prog_fibonacci_recursive"
Benchmark 1: ./prog_fibonacci_recursive
  Time (mean ± σ):      1.657 s ±  0.015 s    [User: 1.652 s, System: 0.002 s]
  Range (min … max):    1.647 s …  1.696 s    10 runs

模板元编程实现​

C++11​

首先，我们定义一个模板类 fibonacci，它具有一个静态成员变量 value，用于存储斐波那契数列的值。该模板类使用递归定义，根据给定的大小计算斐波那契数列值。

template <int size>
struct fibonacci {
    static constexpr unsigned int value = fibonacci<size - 1>::value + fibonacci<size - 2>::value;
};

template <>
struct fibonacci<0> {
    static constexpr unsigned int value = 0;
};

template <>
struct fibonacci<1> {
    static constexpr unsigned int value = 1;
};

使用 fibonacci<42>::value 则可以得到对应的结果。这个语法类似于传统的递归，但是会在编译期进行求值。

使用模板元编程的斐波那契数列计算方法相比于传统的递归方法具有更高的效率。它在编译时完成计算，避免了运行时的重复计算，从而提高了程序的性能。

这里使用了编译期求值的关键字 constexpr，因此需要 C++11 版本及以上。

> g++ -O0 -g -std=c++11 a.out fibonacci_tmp.cpp -o prog_fibonacci_tmp

> ./prog_fibonacci_tmp
267914296

> hyperfine "./prog_fibonacci_tmp"
Benchmark 1: ./prog_fibonacci_tmp
  Time (mean ± σ):       0.8 ms ±   0.1 ms    [User: 0.9 ms, System: 0.2 ms]
  Range (min … max):     0.6 ms …   1.5 ms    1605 runs

在计算第 42 个斐波那契数的时候，运行时间仅需 ~0.8ms，相当于传统递归方法 ~1.6s 的 1/2000。

C++14​

在 C++17 中，通常使用 _v 结尾当作 value 类型 (参见这篇 proposal)，比如：

template <struct T>
constexpr bool is_integral_v = is_integral<T>::value;

类似的，我们可以定义一个模板变量 fibonacci_v，用于方便地获取斐波那契数列的值。

template <int size>
constexpr auto fibonacci_v = fibonacci<size>::value;

注意，这种 _v 的实现并不需要 C++17 的编译器；C++14 的编译器即可以满足需求。

编译：

> g++ -O0 -g -std=c++14 a.out fibonacci_tmp.cpp -o prog_fibonacci_tmp

C++20​

C++20 中，我们可以使用 concept / requires，合并两个偏特化模板。

template <int size>
concept FibonacciBaseCase = (size == 0) || (size == 1);

template <int size>
requires FibonacciBaseCase<size>
struct fibonacci<size> {
public:
    static constexpr unsigned int value = size;
};

编译：

> g++ -O0 -g -std=c++20 a.out fibonacci_tmp.cpp -o prog_fibonacci_tmp

完整代码​

#include <iostream>

template <int size>
struct fibonacci {
public:
    static constexpr unsigned int value = fibonacci<size - 1>::value + fibonacci<size - 2>::value;
};

template <>
struct fibonacci<0> {
public:
    static constexpr unsigned int value = 0;
};

template <>
struct fibonacci<1> {
public:
    static constexpr unsigned int value = 1;
};

int main() {
    std::cout << fibonacci<42>::value << '\n';
    return 0;
}

通过使用模板元编程技术，我们可以在编译时计算斐波那契数列，避免了递归函数的重复计算，在一些需要高效计算斐波那契数列的场景下，这种方法可以提供更好的性能。

希望这篇博客能帮助你理解如何使用模板元编程实现斐波那契数列的编译期计算，并对此有所启发。