Вторник, 20.04.2021, 01:33
Информатика и ИКТ
Приветствую Вас Гость | RSS
Главная Регистрация Вход
Меню сайта

Yandex_tech

Хабр-news

mail_news

Rambler

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

oszone.net

IT-N-образование

Главная » 2021 » Март » 2 » Мемоизация в compile time вычислениях в C++
21:44
Мемоизация в compile time вычислениях в C++

Мемоизация в compile time вычислениях в C++

Программистам на C++ хорошо (надеюсь!) известно, что во время компиляции можно производить разнообразные вычисления. Лишь бы эти вычисления были "чистыми", без побочных эффектов. Это делается на шаблонах и на constexpr функциях.

Чистое выражение означает, что, сколько бы раз мы его ни попытались вычислить, мы получим один и тот же результат. Поэтому из соображений эффективности результат желательно мемоизировать, чтобы второй раз не делать ту же работу. Но насколько хорошо это умеет делать компилятор?

Для стресс-тестирования возьмём наивную формулу чисел Фибоначчи:

f(n) = (n < 2) ? 1 : f(n-1) + f(n-2)

Она интересна нам по нескольким причинам:

  • глубина рекурсии линейно зависит от n

  • без мемоизации она сводится к суммированию f(n) единичек, а это, напомню, экспонента по основанию золотого сечения

  • с мемоизацией — к запоминанию n значений

Как вычислить эту формулу в compile time?

Просмотров: 22 | Добавил: niko | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Поиск

Календарь
«  Март 2021  »
ПнВтСрЧтПтСбВс
1234567
891011121314
15161718192021
22232425262728
293031

Форма входа

nixp.ru

OpenNet

Новые программы

SLO.ru

Погода
Яндекс.Погода

Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • Архив записей

    Copyright MyCorp © 2021