Мемоізація та карірування (Python)
Мемоізація (memoization)
Це спосіб оптимізації, при якому зберігається результат виконання функції і цей результат використовується при наступному виклику.
Беремо рекурсивну реалізацію знаходження числа Фібоначчі та дивимося час виконання.
Час роботи буде дуже швидко зростати при збільшенні числа, яке потрібно знайти, плюс можлива помилка RecursionError.
Для оптимізації подібного алгоритму добре підходить метод мемоізації, тобто збереження і повторне використання ранніх обчислених значень (але спочатку потрібно постаратися зовсім відмовитися від рекурсивного алгоритму).
Або у вигляді декоратора:
І хороша новина в тому, що в стандартній бібліотеці functools вже чудово реалізований подібний декоратор lru_cache.
LRU розшифровується як Least Recently Used.
lru_cache має два необов'язкові аргументи. maxsize - це кількість збережених результатів. typed - при рівному true, наприклад, значення 1 і 1.0 будуть вважатися різними.
Мемоізація досить проста та ефективна практика. Завдяки functools.lru_cache їй зручно користуватися в Python. Під капотом у неї словник у вигляді хеш-таблиці, відповідно, ключ повинен реалізувати хешування.
Тепер про карирування або карринг (currying)
Карринг - це перетворення функції від багатьох аргументів на набір функцій, кожна з яких є функцією від одного аргументу. Ми можемо передати частину аргументів у функцію і отримати назад функцію, що очікує на інші аргументи.
Створимо просту функцію greet, яка приймає як аргументи привітання та ім'я:
Невелике покращення дозволить нам створити нову функцію для будь-якого типу привітання та передати цій новій функції ім'я:
А далі можназробити це з будь-якою кількістю аргументів:
Або варіант з lambda:
Часткове застосування (partial application)
Це процес застосування функції до її аргументів. Іншими словами, функція, яка приймає функцію з кількома параметрами та повертає функцію з меншою кількістю параметрів.
Часткове застосування перетворює функцію від n аргументів (x-n), а карринг створює n функцій з 1 аргументів.
Така можливість має Python у стандартній бібліотеці functools, це функція partial.
Ще один приклад із partial, вирішує проблему замикання в циклі:
На сьогодні все. Дякую!
Хардкорна конфа за С++. Ми запрошуємо лише профі.