Введение


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

Комментарии (39)


  1. Bessmertnii
    28.04.2017 10:55

    Круто, прикольно, но где тут новый способ? Я вижу тут лишь необычную реализацию стандартного способа.


    1. Sirion
      28.04.2017 11:02

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


  1. duger
    28.04.2017 11:05
    +12

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


    Аргументация уровня журнала Cosmopolitan


    1. Sirion
      28.04.2017 11:08
      +8

      Такая аргументация называется "социальное доказательство". А когда её используют в таком контексте, это называется "ирония".


      1. captGreen
        28.04.2017 13:45
        +2

        Табличку «Сарказм» нужно поднимать,


        1. Sirion
          28.04.2017 15:38

          Дык руки устали уже.


  1. alvvi
    28.04.2017 11:12

    Через цикл ведь все равно будет быстрее и короче, не?


    1. Sirion
      28.04.2017 11:15
      +4

      Ну, такие заявления нельзя делать без тестов. Нужно замерить перформанс в каждом конкретном случае.


      1. alvvi
        28.04.2017 12:42

        Не совсем понимаю, о каких конкретных случаях речь, я говорил о самом банальном сравнении, которое вы дали в начале.На любом тесте, который бы я не находил на jsPerf, цикл выигрывал с довольно большим отрывом. И да, я не делал заявлений, я как раз таки задал вопрос, так как самому интересно.


        1. Sirion
          28.04.2017 12:47

          Если отвечать серьёзно, то разумеется, цикл будет быстрее рекурсии. Я не уверен, можно ли как-то оптимизировать ещё сильнее, но из наивных реализаций цикл точно самый быстрый.


          1. fsou11
            28.04.2017 13:26
            +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. AlNi89
        29.04.2017 10:41
        +1

        А разве без теста не очевидно, что в обоих случаях выполняется одно и то же действие (перемножение чисел), только при рекурсии программа «распухает» за счёт вызова функции (самой себя) и передачи (копирования) ей данных?


        1. Sirion
          29.04.2017 10:55

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


  1. copal
    28.04.2017 11:33
    +1

    Возможно это и откровение с точки зрения факториала, а вот с точки зрения js кода этому творению место на свалке.


    1. Sirion
      28.04.2017 11:33
      +4

      Сильное заявление. Аргументировать его вы, конечно, не будете?


    1. helgisbox
      28.04.2017 12:41

      Так он же сказал, про реализацию, ад и все такое ;)


  1. ilay
    28.04.2017 12:00

    Скажите пожалуйста, а зачем в примере с рекурсией второй параметр? И что в него передается при вызове?


    1. fsou11
      28.04.2017 12:32
      +2

      Для реализации хвостовой рекурсии


      1. Sirion
        28.04.2017 12:41

        Ну, собственно, да. Иначе можно было бы написать function factorial(n){return !n? 1: factorial(n-1)}. Но в таком случае, несмотря на то, что рекурсивный вызов стоит последним, это не будет хвостовой рекурсией, потому что последним вычисляемым выражением будет значение тернарного оператора.


        1. Sirion
          28.04.2017 13:24

          function factorial(n){return !n? 1: n*factorial(n-1)}, конечно же


  1. REPISOT
    28.04.2017 12:08
    -1

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

    То есть давайте все ходить через лес, тогда там быстрее появится дорога.


    1. LoadRunner
      28.04.2017 12:16
      +2

      Там, где ходят люди, протаптываются тропинки этими самыми людьми. А потом там кладут асфальт и облагораживают дорожки.


      1. REPISOT
        28.04.2017 14:04

        Это если в 10 метрах уже не проложена дорога. По которой все ходят. И тут появляется такой человек, который хочет дорогу на 10 метров ближе к своему дому и говорит: ходите все через лес, в грязь, в снег, тогда через несколько лет тут будет дорога…
        А имеющаяся дорога — это циклы.


        1. LoadRunner
          28.04.2017 14:07
          +1

          Я не понимаю, что Вам не нравится. Основную дорогу никто не закроет же.


  1. acerikfy
    28.04.2017 12:31
    -1

    Ваш код настолько идеален, что изобретает новую математику: по мнению вашего алгоритма, 50! = 3. В чем тогда смысл такого запутанного кода, который ни поддерживать, ни отлаживать невозможно?


    1. Sirion
      28.04.2017 12:34
      +1

      Ну, в некотором смысле это действительно 3. Если быть точным, 3.0414093201713376e+64.


  1. Aingis
    28.04.2017 13:46
    +2

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


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

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


    1. Sirion
      28.04.2017 15:13

      Кстати да, я думал об этом, но потом самомодифицирующийся код захватил мою голову.


  1. Melorian
    28.04.2017 14:40

    Господи боже, мы наконец-то дожили до сложения чисел с помощью JQuery!
    Сарказм, конечно же, но все-таки…


  1. zagayevskiy
    28.04.2017 15:36
    +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;

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


    1. Sirion
      28.04.2017 15:39
      +2

      Ну наконец-то хоть кто-то задетектил сарказм =)


  1. hdfan2
    28.04.2017 16:06
    +2

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


  1. kahi4
    28.04.2017 16:53
    +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


    1. Sirion
      28.04.2017 17:00

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


      1. kahi4
        28.04.2017 17:07

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


    1. Aingis
      28.04.2017 18:48
      +1

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


      factorial(2) // 1.9999574974296939


      1. Keyten
        29.04.2017 19:51

        Да никаких проблем:

        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)));
        


        1. Aingis
          29.04.2017 21:01

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


          1. Keyten
            30.04.2017 20:43

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