ЛР 4. Бенчмарк рекурсии и итерации¶

Тема: Сравнение скорости рекурсивного и итеративного подходов с использованием LRU-кеширования

Цель работы¶

Сравнить производительность рекурсивного и итеративного подходов к вычислениям. Изучить влияние кеширования (functools.lru_cache) на скорость рекурсии.

Задание¶

Реализовать рекурсивную и итеративную версии вычисления (факториал / бинарное дерево).
Замерить время выполнения с помощью функции бенчмарка.
Добавить @lru_cache к рекурсивной версии и повторить замеры.
Сравнить результаты, построить графики.

Ход выполнения¶

Без LRU-кеша (lab_4.1_withoutLRU): рекурсия значительно медленнее итерации, так как каждый вызов пересчитывается заново.
С LRU-кешем (lab_4.1_withLRU): добавление @lru_cache ускоряет рекурсию, так как повторные вызовы с одинаковыми аргументами берутся из кеша.
Факториал без LRU (lab_4.2_withoutLRU): график сравнения рекурсивного и итеративного факториала.
Факториал с LRU (lab_4.2_withLRU): после кеширования рекурсия сравнима по скорости с итерацией.

Подробные материалы: Google Drive

Выводы¶

Рекурсия без кеширования значительно уступает итерации по производительности из-за повторных вычислений. Применение functools.lru_cache устраняет этот недостаток, делая рекурсию сопоставимой по скорости с итерацией. Выбор подхода зависит от задачи: рекурсия удобнее для древовидных структур, итерация — для линейных вычислений.