时间戳

首页 > 解决方案 > C++ 编译器如何如此快速地评估递归 constexpr 函数？

c++ - C++ 编译器如何如此快速地评估递归 constexpr 函数？

问题描述

我一直在学习 C++constexpr函数，并且我实现了一个constexpr递归函数来查找第 n 个斐波那契数。

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>

constexpr long long fibonacci(int num) {
    if (num <= 2) return 1;
    return fibonacci(num - 1) + fibonacci(num - 2);
}

int main() {
    auto start = clock();
    long long num = fibonacci(70);
    auto duration = (clock() - start) / (CLOCKS_PER_SEC / 1000.);
    std::cout << num << "\n" << duration << std::endl;
}

如果我从函数中删除constexpr标识符，则需要很长时间来评估（超过 5 分钟）。但是，当我保持原样时，程序仍会在 3 秒内编译并在不到几毫秒的时间内打印出正确的结果。fibonacci()fibonacci(70)0.1

我了解到constexpr函数是在编译时评估的，所以这意味着fibonacci(70)编译器会在不到 3 秒的时间内计算出来！但是，C++ 编译器比 C++ 代码具有更好的计算性能似乎不太正确。

我的问题是，C++ 编译器是否真的在我按下“构建”按钮和编译完成之间评估函数？还是我误解了关键字constexpr？

编辑：这个程序是用g++ 7.5.0with编译的--std=c++17。

标签： c++functionrecursionconstexpr

解决方案

constexpr函数没有副作用，因此可以放心地记忆。鉴于运行时的差异，最简单的解释是编译器在编译时记忆 constexpr 函数。这意味着fibonacci(n)每个 只计算一次n，所有其他递归调用都从查找表返回。

推荐阅读