Мемоизация в JavaScript

Иногда наши рекурсивные или часто вызываемые функции очень сильно «тормозят» выполнение программы, потому что результаты промежуточных вычислений нигде не сохраняются, а вычисляются заново. Решить проблему может мемоизация.

Из википедии:

Мемоизация — сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее: если не вызывалась, функция вызывается и результат её выполнения сохраняется; если вызывалась, используется сохранённый результат.

Классическим примером для иллюстрации является функция, вычисляющая последовательность чисел Фибоначчи:

Для больших чисел n количество вызовов функции растёт очень быстро. Уже для n=50 это порядка 40 миллиардов вызовов.

Используя идею мемоизации, то есть кеширования промежуточного результата, можно добиться уменьшения количества вызовов для n=50 до всего лишь 99:

Если функция имеет дело с несколькими аргументами, то нужно хранить в кеше их все. Вместо того,  чтобы каждый раз писать «мемоизированную» версию функции, можно использовать функцию-обёртку вроде такой:

Используется она очень просто:

Мемоизация полезна, когда вы передаёте в функцию заранее известный набор аргументов и когда результат функции будет всегда одинаковым при одинаковых аргументах. Если же функция не даёт одинакового результата при тех же аргументах, то мемоизация будет бесполезна.

Код большинства примеров взят из статьи   Implementing Memoization in Javascript

Поделиться: Share on LinkedIn
Linkedin
Share on VK
VK
Share on Facebook
Facebook
0Tweet about this on Twitter
Twitter

2 комментария

    1. действительно, большинство примеров взяты оттуда, но с другой стороны пример с фибоначчи — это классика, и подобный код есть и на stackoverflow.com, и на девелоперском ресурсе mozilla. в этом смысле, ни идея примера, ни то, что он иллюстрирует, не уникальны. могу поставить ссылку, конечно.

Оставить комментарий

Ваш e-mail не будет опубликован.

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.

Яндекс.Метрика