Как реализовать мемоизацию функции в JavaScript

Что проверяют

Умеете ли вы написать обёртку с кешем без типичных дыр и понимаете ли, когда мемоизация вредна. Следом обычно просят мемоизировать рекурсивный fib или спрашивают, чем ваша версия отличается от useMemo.

Как отвечать

Каркас: функция высшего порядка принимает fn, в замыкании держит кеш и возвращает обёртку, которая по ключу из аргументов либо отдаёт готовый результат, либо считает и запоминает.

• хранилище: Map, а не объект. Проверка через cache.has(key), а не по истинности значения, иначе результат 0, '' или false будет пересчитываться каждый раз;
• ключ: для одного примитивного аргумента это сам аргумент. JSON.stringify(args) годится только для простых данных: он теряет undefined и функции, превращает Map в {}, падает на циклических ссылках и выдаёт разные ключи для объектов с разным порядком полей;
• контекст: вызывать fn.apply(this, args), чтобы мемоизированный метод объекта не потерял this;
• объекты в аргументах: WeakMap с ключом по ссылке, тогда запись уйдёт вместе с объектом при сборке мусора;
• ограничение размера: LRU поверх Map, пользуясь тем, что Map помнит порядок вставки. При попадании запись удаляют и вставляют заново, при переполнении выкидывают cache.keys().next().value.

Для рекурсии покажите, что внутри функция должна вызывать уже мемоизированную версию, иначе кешируется только верхний вызов. Отдельно назовите условие применимости: функция чистая, аргументы повторяются, а вычисление дороже построения ключа. Во фронтенде это useMemo, React.memo и селекторы createSelector из Reselect, а у _.memoize из lodash ключом по умолчанию служит только первый аргумент.

Где спотыкаются

Проверяют if (cache[key]). Ложные результаты не кешируются, и оптимизация молча перестаёт работать.

Мемоизируют функцию с побочными эффектами или зависимостью от времени и сети. Второй вызов вернёт старый ответ, и такой баг ищут долго.

Забывают про память. Кеш без ограничения на долгоживущей странице растёт бесконечно, а мемоизация дешёвой функции вроде a + b медленнее самого вычисления из-за сериализации ключа.