Главная » Хабрахабр » История одной задачи: Кратчайший мемоизатор на JavaScript

История одной задачи: Кратчайший мемоизатор на JavaScript

image

Наша компания уже не первый год является спонсором: соответственно, имеет и свой стенд с интересностями для пытливого ума неравнодушных разработчиков. Дело было вечером, накануне ежегодной конференции HolyJS в Санкт-Петербурге. Когда основное блюдо было готово и все задания были отревьювены и законфирмены, я решил подкинуть на ночь глядя еще интеллектуальной пищи коллегам:

У вас есть всего 50 символов. Напишите мемоизатор — функцию-декоратор, сохраняющую результаты выполнения оборачиваемой функции для предотвращения повторных вычислений.

Сама задача — классика, но ограничение в 50 символов обернулось настоящим челенджем. Язык — разумеется, JavaScript.

Весь ажиотаж увенчался идеей поделиться задачей со всеми участниками конференции, и на второй день мы визуализировали задачу (см. В перерывах первого дня конференции мы обсуждали варианты достижения цели, постепенно сокращая ответ. В итоге получили около 40 решений и в очередной раз убедились в незаурядности сообщества js-разработчиков, но рекорд Дмитрия Катаева (SEMrush) в 53 символа остался. приложение) и стали раздавать бланки желающим. Давайте разбираться!

Привычная реализация

function memoize(f) ; 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, тесты прошли

Тут нам на помощь приходит spread operator, позволяющий заменить передаваемый итерируемый объект аргументов переменной-массивом a. Далее можно провести аналогичную операцию с результирующей функцией, но там нам необходим arguments. Кроме того, мы больше не будем передавать декорируемой функции контекст 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

Мы можем себе это позволить, так как результат сериализации массива аргументов через JSON.stringify всегда будет "[...]" и маловероятно, что в прототипе кэша (Object) окажется такое свойство. Здесь мы отказываемся от метода hasOwnProperty.

Далее мы используем особенность "логического" оператора ИЛИ возвращать первое выражение, если оно может быть преобразовано в true, или в противном случае — второе с предшествующим вычислением функции.

Это произошло потому что декорируемая функция console.log не возвращает значение: результатом будет undefined. И тут у нас упали тесты 3 и 4. Этот эффект будет иметь место для всех сводимых к false результатам: 0, "", null, NaN и др. Мы кладем это в кэш, а когда при повторном вызове пытаемся через особенность дизъюнктора проверить, то получаем неявно выведенный false в первом операнде и, соответственно, попадаем во второй, что приводит к вызову функции.

Вместо ИЛИ и 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 сразу не стоит. Сократить совсем не удалось. А это значит, не отказаться ли нам от JSON.stringify вообще? Эта реализация key-value хранилища позволяет использовать в качестве ключа — объекты.

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. Выглядит очень многообещающе! Если опустить детали с NaN, -0 и 0, то работает он аналогично strict comparison operator (===). Это потому что сравнение ключей в объекте Map реализовано с помощью алгоритма SameValueZero. Сравнение же происходит по референсу объекта и поэтому метод 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

Кажется, что возвращаемое значение — это результат предыдущего вызова функции в тесте 5. Только начинает падать тест 6. Да, мы обошли вызов toString для объекта arguments, но мы не учли, что любой аргумент тоже может быть сложным объектом, вызывая toString у которого мы получим всеми любимый [object Object]. Почему так происходит? Это значит, что аргументы {x:1} и {x:2} будут использовать один и тот же ключ в хэше.

Но и он приводит сначала к строке, поэтому без шансов. Хорошим претендентом на функцию сериализации казался btoa, используемый для преобразования в base64. Но так и остались на месте. Мы думали и в сторону генерации URI, и формирования ArrayBuffer, любых функций для получения какого-либо хэша или сериализованного значения.

То же касается функций. Кстати, и у JSON.stringify есть свои особенности: Infinity, NaN, undefined, Symbol будут приведены к null. Оно и понятно, учитывая конечный формат: JSON. При возможности происходит неявный вызов toJSON от объекта, а Map и Set будут представлены просто перечислимыми элементам.

Что же дальше?

Токсичная доработка

А это значит, что пора бы добавить щепотку 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 обезопасит нас от пересечения с другими свойствами и методами объекта (функции), оборачивая аргументы в "[...]".

Но сохранить единственное выражение для стрелочной функции остро необходимо, чтобы избежать return statement: В этот самый момент примененный ранее паттерн IIFE перестает себя оправдывать.

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! Подобные этой истории являются хорошим поводом погрузиться в изучение специфики языка, помогают лучше его понять (или наоборот).

Приложение

image

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


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

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Особенности работы в интернациональной команде. Япония

Причины переезда всегда разные, но чаще всего люди просто хотят перемен. Поработать в другой стране это, как говорят сейчас, challenge (вызов) для многих российских специалистов: сможешь ли «найти» себя в новой стране, в новой роли. И хорошо, если они к ...

[Перевод] Как работают браузеры — введение в безопасность веб-приложений

Давайте начнем серию статей по безопасности веб-приложений с объяснением того, что делают браузеры и как именно они это делают. Поскольку большинство ваших клиентов будут взаимодействовать с вашим веб-приложением через браузеры, необходимо понимать основы функционирования этих замечательных программ. Chrome и lynx ...