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

    image


    Дело было вечером, накануне ежегодной конференции 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!


    Приложение


    image


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

    SEMrush 79,76
    Компания
    Поделиться публикацией
    Комментарии 17
      +7
      Хоть сейчас и набегут приверженцы чистого, читаемого кода, но, как по мне, такие эксперименты всегда помогают в изучении языка. Спасибо за такой подробный разбор!
        +1
        Вам на codegolf.stackexchange.com — там таких челленджей воз и маленькая тележка.

        P.S.: Если бы ещё сокращался результирующий асм-код…
          +1
          Да, там мы тоже искали возможные подсказки.
          +1
          JSON.stringify все равно покрывает не 100% возможных ситуаций (например, если передать объекты с циклическими ссылками внутри). Т.е. у нас уже есть ограничения на параметры мемоизиуемой функции. Можно эти ограничения расширить :) Например, пусть параметры реализуют toString, тогда можно сделать через join и будет 48 символов :)

          f=>(...a)=>f[k=a.join("\0")]=k in f?f[k]:f(...a);


            +1
            Про особенности JSON.stringify упомянул; циклические ссылки в контексте поставленной задачи кажутся особым кейсом — пренебрегаем.

            Если полагаться на toString, то join произойдет у Array.prototype.toString, так как мы отошли от arguments в пользу массива и будет еще короче. Но накладывать такие требования на данные — это слишком. Каноничней тогда на полифилы hashCode и equals посмотреть.
              0
              Разумно, согласен.
              0

              Тогда уже можно и:


              f=>(...a)=>f[a]=a in f?f[a]:f(...a);
                +2
                Я повторюсь, что если полагаться на toString, то можно и просто:

                f=>(...a)=>f[a]=a in f?f[a]:f(...a);
                


                Но по условию задачи в качестве аргумента может быть объект, и тогда тест 6 падает на [object Object]. В этом основная сложность: найти кратчайшую функцию сериализации или хэширования.
              +2
              А Perl за это ругали…
                +2

                Было бы хорошо все же вернуть пробелы и строки, статья ведь ход мыслей описывает.
                Финальный результат без пробелов, для наглядности, можно в конце привести.

                  +1
                  Да, в первой части статьи про чистую реализацию так и сделал. Это контрольная точка перед дальнейшей грязной доработкой, где уже за каждый символ приходится бороться: за тот же пробел перед in operator )
                    0
                    Я как-раз во второй части статьи перестал понимать, что происходит, из-за минификации. Действительно, лучше приводить полный, читаемый код, но количество символов в нём учитывать уже после минификации, раз уж статья для читателя, а не js-интерпретатора :)
                    0
                    К слову, когда мы принимали решения от соискателей, то часто звучали справедливые комментарии мол не думали что укорачивать надо так однострочно. Но при оценке решений мы обращали внимание именно на используемые языковые выражения и пропущенные подводные камни.
                    +1
                    На 50 символов можно попробовать так:
                    f=>(...a)=>f[k=JSON.stringify(a)]=f[k]||f(...a)||1

                    Тут конечно есть проблемы, функции без return будут возвращать единицу, но со своей задачей код справится :)
                      0
                      Отличная попытка ) но я боюсь мы не можем пренебречь сводимым к false результатами. Например, если вызов декорируемой функции используется в условии while или ожидается false для выхода из рекурсии. Опасная подмена 0 на 1, но спасибо за мысль!
                        0
                        Тогда оставляем 0 в конце, нам же без разницы, что вернет функция undefined, null, 0 или false, мы это в конце концов обработаем.
                          0
                          Получится такая же ситуация как и с:
                          f[k]||f(...a)

                          т.е. сохраняем 0 или любое другое сводимое к false и всегда проваливаемся во второй операнд ИЛИ.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое