История одной задачи: Кратчайший мемоизатор на JavaScript
Дело было вечером, накануне ежегодной конференции HolyJS в Санкт-Петербурге. Наша компания уже не первый год является спонсором: соответственно, имеет и свой стенд с интересностями для пытливого ума неравнодушных разработчиков. Когда основное блюдо было готово и все задания были отревьювены и законфирмены, я решил подкинуть на ночь глядя еще интеллектуальной пищи коллегам:
Напишите мемоизатор — функцию-декоратор, сохраняющую результаты выполнения оборачиваемой функции для предотвращения повторных вычислений. У вас есть всего 50 символов.
Язык — разумеется, JavaScript. Сама задача — классика, но ограничение в 50 символов обернулось настоящим челенджем.
В перерывах первого дня конференции мы обсуждали варианты достижения цели, постепенно сокращая ответ. Весь ажиотаж увенчался идеей поделиться задачей со всеми участниками конференции, и на второй день мы визуализировали задачу (см. приложение) и стали раздавать бланки желающим. В итоге получили около 40 решений и в очередной раз убедились в незаурядности сообщества js-разработчиков, но рекорд Дмитрия Катаева (SEMrush) в 53 символа остался. Давайте разбираться!
Привычная реализация
function memoize(f) {
let cache = {};
return function ret() {
let key = JSON.stringify(arguments);
if (!cache.hasOwnProperty(key)) {
cache[key] = f.apply(this, arguments);
}
return cache[key];
}
}
Результат: ~190 символов
- memoize — наш мемоизатор
- f — декорируемая, оборачиваемая функция
- ret — результирующая функция
Чтобы получить ответ — размер функции — воспользуемся:
memoize.toString().replace(/\s+/g, ' ').length
При оценке размера функции обращаем внимание на ее тело и список параметров. Если функция анонимна, то объявление не учитывается.
Простые тесты для проверки работоспособности после надругательств:
const log = memoize(console.log);
const inc = memoize(o => o.x + 1);
| № | Вызов функции | Результат выполнения в консоли |
|---|---|---|
| 1. | log(false) |
> false |
| 2. | log('2', {x:1}) |
> '2', {x:1} |
| 3. | log(false) |
Ничего, так как для этих значений функция уже выполнялась. |
| 4. | log('2', {x:1}) |
Ничего, так как для этих значений функция уже выполнялась. |
| 5. | inc({x:1}) |
2 |
| 6. | inc({x:2}) |
3 |
Далее результат каждой реализации будет отмечен результатом тестов.
Чистая реализация
Первым делом хочется избавиться от Function Declaration в пользу стрелочной функции, так как контекст this нам не интересен, к arguments мы не обращаемся и как конструктор через new вызывать не намереваемся. Заодно сократим имена используемых локальных переменных:
const memoize = f => {
let c = {};
return function() {
let k = JSON.stringify(arguments);
if (!c.hasOwnProperty(k)) {
c[k] = f.apply(this, arguments);
}
return c[k];
}
}
Результат: 154, тесты прошли
Далее можно провести аналогичную операцию с результирующей функцией, но там нам необходим arguments. Тут нам на помощь приходит spread operator, позволяющий заменить передаваемый итерируемый объект аргументов переменной-массивом a. Кроме того, мы больше не будем передавать декорируемой функции контекст this: если это необходимо, то поможет Function.prototype.bind или свой полифил.
const memoize = f => {
let c = {};
return (...a) => {
let k = JSON.stringify(a);
if (!c.hasOwnProperty(k)) {
c[k] = f(...a);
}
return c[k];
}
}
Результат: 127, тесты прошли
Теперь обратимся к телу результирующей функции. Очевидно, что нахождение ключа в кэше и возврат значения — громоздки. Попробуем сократить как:
const memoize = f => {
let c = {};
return (...a) => {
let k = JSON.stringify(a);
return c[k] || (c[k] = f(...a));
}
}
Результат: 101, упали тесты 3 и 4
Здесь мы отказываемся от метода hasOwnProperty. Мы можем себе это позволить, так как результат сериализации массива аргументов через JSON.stringify всегда будет »[…]» и маловероятно, что в прототипе кэша (Object) окажется такое свойство.
Далее мы используем особенность «логического» оператора ИЛИ возвращать первое выражение, если оно может быть преобразовано в true, или в противном случае — второе с предшествующим вычислением функции.
И тут у нас упали тесты 3 и 4. Это произошло потому что декорируемая функция console.log не возвращает значение: результатом будет undefined. Мы кладем это в кэш, а когда при повторном вызове пытаемся через особенность дизъюнктора проверить, то получаем неявно выведенный false в первом операнде и, соответственно, попадаем во второй, что приводит к вызову функции. Этот эффект будет иметь место для всех сводимых к false результатам: 0,», null, NaN и др.
Вместо ИЛИ и if statement можем использовать условный тернарный оператор:
const memoize = f => {
let c = {};
return (...a) => {
let k = JSON.stringify(a);
return c.hasOwnProperty(k) ?c[k] :c[k] = f(...a);
}
}
Результат: 118, тесты прошли
Сократили совсем незначительно. А что если использовать вместо простого объекта — Map в качестве хранилища? Там же есть короткий метод has:
const memoize = f => {
let c = new Map;
return (...a) => {
let k = JSON.stringify(a);
return (c.has(k) ?c :c.set(k, f(...a))).get(k);
}
}
Результат: 121, тесты прошли
Сократить совсем не удалось. Но отбрасывать Map сразу не стоит. Эта реализация key-value хранилища позволяет использовать в качестве ключа — объекты. А это значит, не отказаться ли нам от JSON.stringify вообще?
const memoize = f => {
let c = new Map;
return (...a) => (c.has(a) ?c :c.set(a, f(...a))).get(a);
}
Результат: 83, упали тесты 3 и 4
Выглядит очень многообещающе! Однако, начали снова падать тесты 3 и 4. Это потому что сравнение ключей в объекте Map реализовано с помощью алгоритма SameValueZero. Если опустить детали с NaN, -0 и 0, то работает он аналогично strict comparison operator (===). А у нас — новый массив аргументов (а значит — объект) на каждый вызов обернутой функции, даже при одинаковых значениях. Сравнение же происходит по референсу объекта и поэтому метод Map.prototype.has никогда ничего не найдет.
Таким образом, использование Map не сократило нам hasOwnProperty или JSON.stringify.
На помощь приходит in operator, который проверяет наличие свойства в объекте или в цепочке его прототипов. Почему мы можем не бояться поиска в прототипах было объяснено выше.
const memoize = f => {
let c = {};
return (...a) => {
let k = JSON.stringify(a);
return k in c ?c[k] :c[k] = f(...a);
}
}
Результат: 105, тесты прошли
Тело и мемоизатора, и результирующей функции состоит из двух выражений с необходимостью объявления и инициализации локальной переменной перед логикой в return statement. Можно ли здесь сократить тело стрелочной функции до одного выражения? Конечно, с помощью паттерна IIFE (Immediately Invoked Function Expression):
const memoize = f => (c => (...a) =>
(k => k in c ?c[k] : c[k] = f(...a))(JSON.stringify(a))
)({});
Результат: 82, тесты прошли
Пора избавиться от лишних пробелов:
f=>(c=>(...a)=>(k=>k in c?c[k]:c[k]=f(...a))(JSON.stringify(a)))({});
Результат: 68, тесты прошли
Очевидно, что теперь узким местом является длинный метод JSON.stringify, который рекурсивно сериализует объект в JSON-строку, которая используется у нас в качестве ключа. На самом деле, нам нужна не функция сериализации, а хэш-функция, с помощью которой мы могли бы проверить равенство объектов, как это работает в других языках. Но нативного решения в JavaScript, к сожалению, нет, а самописный полифил hashCode в прототипе Object явно выходит за рамки.
Хм, а зачем нам вообще заниматься сериализацией самим? При добавлении элемента в объект по ключу, произойдет его неявный вызов toString. Так как мы отказались от использования итерируемого объекта arguments в пользу массива через spread operator, то вызов toString будет не от Object.prototype, а от Array.prototype, в котором он переопределен и джойнит через запятую свои элементы. Таким образом, для разного набора аргументов получим разный ключ.
f=>(c=>(...a)=>a in c?c[a]:c[a]=f(...a))({});
Результат: 44, упал тест 6
Только начинает падать тест 6. Кажется, что возвращаемое значение — это результат предыдущего вызова функции в тесте 5. Почему так происходит? Да, мы обошли вызов toString для объекта arguments, но мы не учли, что любой аргумент тоже может быть сложным объектом, вызывая toString у которого мы получим всеми любимый [object Object]. Это значит, что аргументы {x:1} и {x:2} будут использовать один и тот же ключ в хэше.
Хорошим претендентом на функцию сериализации казался btoa, используемый для преобразования в base64. Но и он приводит сначала к строке, поэтому без шансов. Мы думали и в сторону генерации URI, и формирования ArrayBuffer, любых функций для получения какого-либо хэша или сериализованного значения. Но так и остались на месте.
Кстати, и у JSON.stringify есть свои особенности: Infinity, NaN, undefined, Symbol будут приведены к null. То же касается функций. При возможности происходит неявный вызов toJSON от объекта, а Map и Set будут представлены просто перечислимыми элементам. Оно и понятно, учитывая конечный формат: JSON.
Что же дальше?
Токсичная доработка
Все мы безусловно любим чистые функции, но в условиях задачи такого требования не стоит. А это значит, что пора бы добавить щепотку side-effect«ов.
Первое, почему бы не инициировать кэш следующим образом:
(f,c={})=>(...a)=>(k=>k in c?c[k]:c[k]=f(...a))(JSON.stringify(a));
Результат: 66, тесты прошли
Здесь мы используем default parameter в стрелочной функции. Конечно, мы предоставляем клиенту возможность задать свой кэш, ну и что? Зато мы сократили 2 символа.
Как еще можно инициировать кэш для декорируемой функции? Правильный ответ:, а зачем нам его инициировать? Почему бы не использовать что-то готовое в контексте оборачиваемой функции. А что если саму функцию? Все мы знаем что функции в JavaScript — это тоже объекты:
f=>(...a)=>(k=>k in f?f[k]:f[k]=f(...a))(JSON.stringify(a));
Результат: 59, тесты прошли
Здесь JSON.stringify обезопасит нас от пересечения с другими свойствами и методами объекта (функции), оборачивая аргументы в »[…]».
В этот самый момент примененный ранее паттерн IIFE перестает себя оправдывать. Но сохранить единственное выражение для стрелочной функции остро необходимо, чтобы избежать return statement:
f=>(...a)=>(k=JSON.stringify(a),k in f?f[k]:f[k]=f(...a));
Результат: 57, тесты прошли
Так как мы не используем block statement в стрелочной функции, то не можем объявить переменную (var или let), но можем воспользоваться глобальным контекстом — side-effect! Тут конфликт уже имеет некоторые шансы быть.
С помощью comma operator мы конкатенируем два выражения в одно: операнды вычисляются слева-направо, а результатом является значение последнего.
f=>(...a)=>(k=JSON.stringify(a))in f?f[k]:f[k]=f(...a);
Результат: 54, тесты прошли
Так, с помощью перестановки одной лишь скобки, мы избавились сразу от трех символов. Grouping operator над вычислением ключа позволил нам объединить оба операнда выражения просто в одно выражение, а закрывающая скобка убрала пробел перед in operator.
И наконец:
f=>(...a)=>f[k=JSON.stringify(a)]=k in f?f[k]:f(...a);
Результат: 53, тесты прошли
Почему бы не вычислить ключ в момент обращения к значению. А далее — все тот же тернарный оператор и присвоение. Итого: 53 символа!
Возможно ли убрать оставшиеся 3 символа?
Осмысление
Зачем все это? Эта простая задача и последующая цепочка приведений привычного к неприличному демонстрирует немалое количество особенностей языка JavaScript. В своих рассуждениях мы затронули такие вещи как:
- Arrow function expression
- Lexical scoping & IIFE
- Array-like arguments object
- Spread, comma, or operators
- Strict comparison operator
- JSON.stringify & toString
- In operator & hasOwnProperty
- Grouping operator & block statement
- Map object
- и что-то еще
Подобные этой истории являются хорошим поводом погрузиться в изучение специфики языка, помогают лучше его понять (или наоборот). Ну и конечно just for fun!
Приложение
В своих приключениях Рику часто приходится калибровать свою портальную пушку. Процедура требует времени, но входные данные часто повторяются. Ученый старается запоминать уже когда-то полученные результаты чтобы не производить расчеты повторно, но алкоголизм и старческий маразм сильно сказываются на его памяти. Он попросил Морти улучшить модуль настройки пушки, дополнив функцией-мемоизатором. Эта функция должна сохранять результаты декорируемой функции, чтобы предотвратить повторные вычисления. Только Морти панически боится длинных функций. Помогите ему решить задачу максимально компактно. В качестве аргументов декорируемая функция может принимать целые числа, строки, булева и объекты.
