Пятничный JS: единственно верный способ вычисления факториала

    Введение


    Вычисление факториала — одна из традиционных программистских задач для собеседований. Если вдруг кто забыл, факториал натурального числа N обозначается как N! и равняется произведению всех натуральных чисел от единицы до N включительно. Например, $6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720$. Казалось бы, что тут сложного? Однако есть свои нюансы.

    Например, сравним два самых распространённых способа вычисления факториала.

    Через цикл
    function factorial(n){
        var result = 1;
        while(n){
            result *= n--;
        }
        return result;
    }
    


    Через рекурсию
    function factorial(n, result){
        result = result || 1;
        if(!n){
            return result;
        }else{
            return factorial(n-1, result*n);
        }
    }
    


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

    В любом случае, оба эти способа слишком примитивны, чтобы по ним судить о знаниях кандидата. А вот опытный разработчик на React.js уже может написать что-то в этом роде:

    var React = require("react");
    
    var Factorial = React.createClass({
        render: function(){
            var result = this.props.result || 1,
                n = this.props.n;
            if(!n){
    	    return <span>{result}</span>
    	}else{
    	    return <Factorial n={n - 1} result={result*n}/>
    	}
        }
    });
    module.exports = Factorial;
    

    Согласитесь, выглядит гораздо солиднее. Впрочем, невооружённым глазом видно, что это всего лишь вариант рекурсивного вычисления. Сходство станет ещё сильнее, если переписать Factorial как функциональный компонент. И, разумеется, я не стал бы писать этот хабрапост, если бы не был готов предложить нечто принципиально новое.

    Начнём издалека


    Какую из возможностей Javascript недолюбливают и недооценивают сильнее всего? Недолюбливают настолько, что про неё даже придумали специальную поговорку? Конечно же, это eval. Можно сказать, что eval — это тёмная сторона Силы. А как мы помним из фильмов Джорджа Лукаса, нет ничего более крутого и впечатляющего, чем тёмная сторона Силы, поэтому давайте попробуем ей овладеть.

    Можно было бы запихнуть в строку какой-нибудь из методов, приведённых в начале поста, а затем передать эту строку в eval, но в этом не было бы новизны. Поставим задачу таким образом, чтобы сделать этот хак невозможным. Пусть у нас есть такой вот каркас:

    function factorial(n){
        var f = "это единственное место в коде, которое мы имеем право изменить";
        f = f.replace("$", n);
        for(let i = 0; i < n; i++){
            if(parseInt(f)){
                throw new Error("Cheaters are not allowed");
            }
            f = eval(f);
        }
        return parseInt(f);
    }
    

    — и мы хотим, внеся изменения лишь в литерал строки f, сделать так, чтобы функция factorial взаправду вычисляла факториал. Вот задача, достойная истинного ситха.

    Что-то это напоминает


    Нам нужен код, который возвращает код, который возвращает код… Если забыть про конечную задачу — вычисление факториала, то есть одна хорошо известная штука, которая нам подойдёт. Эта штука называется квайн — программа, которая выводит свой собственный текст.

    Про квайны на Хабре написано уже немало, потому я напомню лишь основные принципы квайностроительства. Чтобы сделать простейший квайн, нам нужно:

    1. Задать строку, которая содержит весь остальной текст программы.
    2. Подставить в эту строку её же саму
    3. Позаботиться об экранировании символов и прочих мелочах
    4. Вывести получившуюся строку
    5. ???
    6. PROFIT

    Вооружившись этим знанием, можно написать следующий квайн на js (отступы и переносы строки добавлены для удобства читателя):

    var o = {
        q: '\'', 
        b: '\\',
        s: 'var o = {q: _q_b_q_q, b:_q_b_b_q, s: _q_s_q}; console.log(Object.keys(o).reduce(function(a, k){return a.split(_q__q + k).join(o[k])}, o.s))'
    }; 
    console.log(Object.keys(o).reduce(function(a, k){return a.split('_' + k).join(o[k])}, o.s));
    

    В строке o.s содержится весь остальной код, а также специальные подстановочные последовательности, начинающиеся с подчёркивания. Страшное выражение внутри console.log заменяет каждую подстановочную последовательность на соответствующее свойство объекта o, что обеспечивает выполнение пунктов 2 и 3 хитрого плана по созданию квайна.

    Лирическое отступление
    Здесь меня могут поправить: товарищ, это не простейший квайн, а монстр какой-то. Простейший квайн на js выглядит так:
    !function $(){console.log('!'+$+'()')}()

    Это правда, но не совсем. Такой квайн считается «читерским», поскольку он из тела функции получает доступ к её же тексту. Это почти то же самое, что прочитать с жёсткого диска файл с исходным кодом программы. Моветон, одним словом.

    Скрещиваем ежа с ужом


    Как же сделать так, чтобы наш квази-квайн модифицировал сам себя, а в результате превратился в одно-единственное число? Давайте забудем пока про вычисление факториала и постараемся просто написать строку, которая «схлопывается» через определённое количество eval'ов. Для этого нам понадобится:

    • Некий счётчик
    • Соответствующая ему подстановочная последовательность
    • Место, где этот счётчик модифицируется
    • Проверка того, завершён ли обратный отсчёт

    Выглядеть это будет примерно так:

    var f = 
    "var o = {" +
        "q: '\\\''," +
        "b: '\\\\'," + 
        "n: 10," +
        "s: 'var o = {q: _q_b_q_q, b:_q_b_b_q, n:_n, s: _q_s_q}; o.n--; " + 
        "o.n ? Object.keys(o).reduce(function(a, k){return a.split(_q__q + k).join(o[k])}, o.s) : 0;'" +
    "};" +
    "o.n--;" +
    "o.n ? Object.keys(o).reduce(function(a, k){return a.split('_' + k).join(o[k])}, o.s) : 0;"
    
     for(let i = 0; i < 10; i++){
        f = eval(f);
        console.log(f);
    }
    

    Обратите внимание на отсутствие return внутри строки: в нём нет необходимости, eval возвращает значение последнего выражения. Запустив этот код в консоли, можно c благоговением наблюдать, как с каждой итерацией цикла значение n уменьшается на 1. Если кто-то скажет, что для такого эффекта достаточно:

    f.replace(/n: ([0-9]+)/, (_, n) => "n: " + (n - 1))
    — то у него нет чувства прекрасного.

    После этого подготовительного этапа уже совсем нетрудно написать итоговую версию вычисления факториала. Просто добавляется ещё одна переменная и чуть усложняется строчка с изменением.

    function factorial(n){
        var f = "var o = {" + 
            "q: '\\\''," +
            "b: '\\\\'," + 
            "r: 1," + 
            "n: $," +
    	"s: 'var o = {q: _q_b_q_q, b:_q_b_b_q, r: _r, n:_n, s: _q_s_q}; o.r *= o.n--; " + 
    	"o.n ? Object.keys(o).reduce(function(a, k){return a.split(_q__q + k).join(o[k])}, o.s) : o.r;'" +
        "};" +
        "o.r *= o.n--;" +
        "o.n ? Object.keys(o).reduce(function(a, k){return a.split('_' + k).join(o[k])}, o.s) : o.r;"
        f = f.replace("$", n);
      
        for(var i = 0; i < n; i++){
            if(parseInt(f)){
                throw new Error("Cheaters are not allowed.");
            }
    	f = eval(f);
        }
        return parseInt(f);
    }
    

    Теперь вы можете смело идти на собеседование.

    Заключение


    С живым кодом можно поиграться здесь. Как и в прошлой статье из рубрики «Пятничный JS» напоминаю: если вы сделаете что-нибудь подобное на продакшене, то попадёте в ад. С другой стороны, если вы сделаете это на собеседовании, то вам не дадут возможности сделать это на продакшене, и вы не попадёте в ад. Так что делайте это на собеседовании. Спасибо за внимание.

    image
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 47

      0
      Круто, прикольно, но где тут новый способ? Я вижу тут лишь необычную реализацию стандартного способа.
        0
        А вы таки хотите способ вычисления факториала без перемножения чисел от 1 до N? Ну, можно по формуле Стирлинга, или через гамма-функцию Эйлера. Но это уже статья в другой хаб.
        +12
        Многие скажут, что первый способ лучше, но это не так. Во-первых, циклы уже не в тренде, сейчас модно функциональное программирование.


        Аргументация уровня журнала Cosmopolitan
          +8
          Такая аргументация называется "социальное доказательство". А когда её используют в таком контексте, это называется "ирония".
            +2
            Табличку «Сарказм» нужно поднимать,
              0
              Дык руки устали уже.
          0
          Через цикл ведь все равно будет быстрее и короче, не?
            +4
            Ну, такие заявления нельзя делать без тестов. Нужно замерить перформанс в каждом конкретном случае.
              0
              Не совсем понимаю, о каких конкретных случаях речь, я говорил о самом банальном сравнении, которое вы дали в начале.На любом тесте, который бы я не находил на jsPerf, цикл выигрывал с довольно большим отрывом. И да, я не делал заявлений, я как раз таки задал вопрос, так как самому интересно.
                0
                Если отвечать серьёзно, то разумеется, цикл будет быстрее рекурсии. Я не уверен, можно ли как-то оптимизировать ещё сильнее, но из наивных реализаций цикл точно самый быстрый.
                  +2
                  Чтобы не быть голословными: https://jsperf.com/fastest-factorial

                  (1) cycle: 3.700.000 op/sec
                  (2) recursion: 1.450.000 op/sec
                  (3) eval: 500 op/sec
                    +1
                    Возможно вам будет полезно посмотреть доклад Вячеслава Егорова, человека который участвовал в разработке V8. Узнаете много нового о перфоманс тестах в JS.
                      0
                      Спасибо, сохранил
                +1
                А разве без теста не очевидно, что в обоих случаях выполняется одно и то же действие (перемножение чисел), только при рекурсии программа «распухает» за счёт вызова функции (самой себя) и передачи (копирования) ей данных?
                  0
                  Вообще да, но в данном случае нет. В то время, как наши космические корабли бороздят просторы вселенной, а в процессорах, компиляторах и интерпретаторах множатся неочевидные оптимизации, очевидных с точки зрения перформанса вещей становятся всё меньше. В комментарии выше я написал «разумеется», поскольку изучил вопрос и выяснил, что в современных js-движках рекурсия не оптимизирована. Без этого знания ответ не является очевидным.
              +1
              Возможно это и откровение с точки зрения факториала, а вот с точки зрения js кода этому творению место на свалке.
                +4
                Сильное заявление. Аргументировать его вы, конечно, не будете?
                  0
                  Так он же сказал, про реализацию, ад и все такое ;)
                  0
                  Скажите пожалуйста, а зачем в примере с рекурсией второй параметр? И что в него передается при вызове?
                    +2
                    Для реализации хвостовой рекурсии
                      0
                      Ну, собственно, да. Иначе можно было бы написать function factorial(n){return !n? 1: factorial(n-1)}. Но в таком случае, несмотря на то, что рекурсивный вызов стоит последним, это не будет хвостовой рекурсией, потому что последним вычисляемым выражением будет значение тернарного оператора.
                        0
                        function factorial(n){return !n? 1: n*factorial(n-1)}, конечно же
                    –1
                    Во-вторых, чем больше людей используют второй способ, тем быстрее в основных джаваскриптовых движках появится оптимизация

                    То есть давайте все ходить через лес, тогда там быстрее появится дорога.
                      +2
                      Там, где ходят люди, протаптываются тропинки этими самыми людьми. А потом там кладут асфальт и облагораживают дорожки.
                        0
                        Это если в 10 метрах уже не проложена дорога. По которой все ходят. И тут появляется такой человек, который хочет дорогу на 10 метров ближе к своему дому и говорит: ходите все через лес, в грязь, в снег, тогда через несколько лет тут будет дорога…
                        А имеющаяся дорога — это циклы.
                          +1
                          Я не понимаю, что Вам не нравится. Основную дорогу никто не закроет же.
                      –1
                      Ваш код настолько идеален, что изобретает новую математику: по мнению вашего алгоритма, 50! = 3. В чем тогда смысл такого запутанного кода, который ни поддерживать, ни отлаживать невозможно?
                        +1
                        Ну, в некотором смысле это действительно 3. Если быть точным, 3.0414093201713376e+64.
                        +2

                        Когда прочитал про eval ожидал что-то вроде


                        function factorial(n) {
                            return eval(
                                Array.apply(0, Array(n + 1))
                                    .map(Number.call.bind(Number))
                                    .slice(1)
                                    .join('*')
                            )
                        }

                        К сожалению, движки недостаточно оптимизированы, чтобы eval был быстрее обычного цикла.

                          0
                          Кстати да, я думал об этом, но потом самомодифицирующийся код захватил мою голову.
                          0
                          Господи боже, мы наконец-то дожили до сложения чисел с помощью JQuery!
                          Сарказм, конечно же, но все-таки…
                            +1
                            var React = require("react");
                            
                            var Factorial = React.createClass({
                                render: function(){
                                    var result = this.props.result || 1,
                                        n = this.props.n;
                                    if(!n){
                                    return <span>{result}</span>
                                }else{
                                    return <Factorial n={n - 1} result={result*n}/>
                                }
                                }
                            });
                            module.exports = Factorial;

                            Вот это вот? Выглядит солиднее? С кусками разметки? Это как в современном мире называется — шутка, сарказм или что?

                              +2
                              Ну наконец-то хоть кто-то задетектил сарказм =)
                              +2
                              Как-то слишком примитивно, я считаю. Нужно подключить несколько фреймворков, зафигачить с десяток микросервисов, общающихся через REST, утащить это всё в облако, подключить CDN… Короче, тема не раскрыта.
                                +3
                                const factorial = (n) => Math.sqrt(2 * Math.PI * n) * Math.pow((n / Math.E), n) * Math.exp(1 / (12 * n) - 1 / (360 * n * n * n));

                                Rate of growth and approximations for large n

                                  0
                                  Ну, я в своём первом комментарии упоминал формулу Стирлинга
                                    0

                                    Да, что-то пропустил. Но таким вот образом можно поставить в тупик неканоничным решением задачи.

                                    +1

                                    Если бы оно ещё давало целые числа…


                                    factorial(2) // 1.9999574974296939
                                      0
                                      Да никаких проблем:
                                      var factorial = n => Math.round(Math.sqrt(2 * Math.PI * n) * Math.pow((n / Math.E), n) * Math.exp(1 / (12 * n) - 1 / (360 * n * n * n)));
                                      
                                        0

                                        Тогда она даёт неверный ответ на нецелых числах…

                                          0
                                          А он же итак неверный (вернее, не совсем точный) о_О
                                            +1

                                            А как определён факториал нецелого числа?

                                              0
                                              Формула Стирлинга, думаю.
                                                0

                                                Формула Стерлинга — это способ вычисления, а не определение.

                                                  0
                                                  Так-так, а что мешает взять формулу Стирлинга за определение факториала нецелого числа?
                                                  Кроме, конечно, требования о непрерывности, которого у нас, впрочем, и нет.
                                                +1
                                                Гамма-функция Эйлера, например.
                                        0

                                        (комментарий оставлен в рамках федеральной целевой программы "говорить классным людям, что они классные")


                                        Эта статья, как и многие другие ваши статьи, восхитительно прекрасна. Пишите ещё, пожалуйста.

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

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