История одной задачи: Кратчайший мемоизатор на 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!

Приложение

В своих приключениях Рику часто приходится калибровать свою портальную пушку. Процедура требует времени, но входные данные часто повторяются. Ученый старается запоминать уже когда-то полученные результаты чтобы не производить расчеты повторно, но алкоголизм и старческий маразм сильно сказываются на его памяти. Он попросил Морти улучшить модуль настройки пушки, дополнив функцией-мемоизатором. Эта функция должна сохранять результаты декорируемой функции, чтобы предотвратить повторные вычисления. Только Морти панически боится длинных функций. Помогите ему решить задачу максимально компактно. В качестве аргументов декорируемая функция может принимать целые числа, строки, булева и объекты.