Что такое мемоизация

Мемоизация — техника оптимизации кода, сокращающая время его исполнения.

Представим, что у нас есть функция foo, которая выполняется 10 секунд. Нам нужно вызвать эту функцию 3 раза подряд с одними и теми же аргументами. Несложно посчитать, что такой код будет выполняться 30 секунд. Но мы можем применить мемоизацию:

1. Вызовем функцию, подождём 10 секунд и сохраним результат её выполнения в кэш
2. Вызовем функцию ещё раз с теми же аргументами. Вместо того, чтобы исполнять тяжелый код, обратимся к кэшу и проверим нет ли там нужного для нас результат вычислений
3. Если нужный результат есть, вернём его. Если нет, см. шаг 1

Любую ли функцию можно мемоизировать? Конечно же нет. Мемоизировать можно только чистые функции. О том, что это такое, я писал отдельный пост.

Также стоит учитывать, что со временем жизни программы кэш может очень сильно разрастись. Из-за этого сама программа может занимать очень много памяти. Решением может быть несколько подходов:

1. Установить время жизни для каждого из значение кэша
2. Подход LRU (Last Recently Used), когда мы удаляем из кэша значения, которые дольше всего не запрашивались. Такой подход позволяет сохранять в кэше только самые часто используемые данные.
3. Ограничение размера кэша, то есть, когда кэш достигает порогового значения по количеству записей или памяти, старые записи удаляются для освобождения места под новые
4. Просто удалять весь кэш по какому-то таймауту

Сложность тут в том, что нам необходимо реализовать собственный кэш с поддержкой всех необходимых апи для того, что мы описали выше. В JavaScript, например, LRU кэша из коробки, то есть его придётся написать самостоятельно. Самая примитивная же форма кэша для мемоизации, которая и используется чаще всего — Map или же обычный объект.

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