|
Программистам на C++ хорошо (надеюсь!) известно, что во время компиляции можно производить разнообразные вычисления. Лишь бы эти вычисления были "чистыми", без побочных эффектов. Это делается на шаблонах и на constexpr функциях.
Чистое выражение означает, что, сколько бы раз мы его ни попытались вычислить, мы получим один и тот же результат. Поэтому из соображений эффективности результат желательно мемоизировать, чтобы второй раз не делать ту же работу. Но насколько хорошо это умеет делать компилятор?
Для стресс-тестирования возьмём наивную формулу чисел Фибоначчи:
f(n) = (n < 2) ? 1 : f(n-1) + f(n-2)
Она интересна нам по нескольким причинам:
-
глубина рекурсии линейно зависит от n
-
без мемоизации она сводится к суммированию f(n) единичек, а это, напомню, экспонента по основанию золотого сечения
-
с мемоизацией — к запоминанию n значений
Как вычислить эту формулу в compile time? | 
Главная 
