C++ コンパイラはどのようにして再帰 constexpr 関数を高速に評価するのでしょうか? 質問する

C++ コンパイラはどのようにして再帰 constexpr 関数を高速に評価するのでしょうか? 質問する

私は C++constexpr関数について学習しており、constexprn 番目のフィボナッチ数を見つけるための再帰関数を実装しました。

#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関数から識別子を削除するとfibonacci()fibonacci(70)とても長い評価に時間がかかります (5 分以上)。ただし、現状のままでも、プログラムは 3 秒以内にコンパイルされ、0.1数ミリ秒未満で正しい結果が出力されます。

constexpr関数は評価されることを学んだコンパイル時fibonacci(70)つまり、これはコンパイラによって 3 秒未満で計算されることになります。ただし、C++ コンパイラの計算パフォーマンスが C++ コードよりも優れているというのは、あまり正しくないようです。

私の質問は、C++ コンパイラは、「ビルド」ボタンを押してからコンパイルが終了するまでの間に実際に関数を評価するのかということです。それとも、キーワードを誤解しているのでしょうかconstexpr

編集: このプログラムは でコンパイルされましg++ 7.5.0--std=c++17

ベストアンサー1

constexpr関数には副作用がないので、心配することなくメモ化できます。実行時の差異を考慮すると、最も単純な説明は、コンパイラがコンパイル時に constexpr 関数をメモ化するということです。つまり、 はfibonacci(n)各 に対して 1 回だけ計算されn、他のすべての再帰呼び出しはルックアップ テーブルから返されます。

おすすめ記事