Введение
Вычисление факториала — одна из традиционных программистских задач для собеседований. Если вдруг кто забыл, факториал натурального числа N обозначается как N! и равняется произведению всех натуральных чисел от единицы до N включительно. Например, . Казалось бы, что тут сложного? Однако есть свои нюансы.
Например, сравним два самых распространённых способа вычисления факториала.
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 взаправду вычисляла факториал. Вот задача, достойная истинного ситха.
Что-то это напоминает
Нам нужен код, который возвращает код, который возвращает код… Если забыть про конечную задачу — вычисление факториала, то есть одна хорошо известная штука, которая нам подойдёт. Эта штука называется квайн — программа, которая выводит свой собственный текст.
Про квайны на Хабре написано уже немало, потому я напомню лишь основные принципы квайностроительства. Чтобы сделать простейший квайн, нам нужно:
- Задать строку, которая содержит весь остальной текст программы.
- Подставить в эту строку её же саму
- Позаботиться об экранировании символов и прочих мелочах
- Вывести получившуюся строку
- ???
- 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 хитрого плана по созданию квайна.
!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» напоминаю: если вы сделаете что-нибудь подобное на продакшене, то попадёте в ад. С другой стороны, если вы сделаете это на собеседовании, то вам не дадут возможности сделать это на продакшене, и вы не попадёте в ад. Так что делайте это на собеседовании. Спасибо за внимание.
Комментарии (39)
duger
28.04.2017 11:05+12Многие скажут, что первый способ лучше, но это не так. Во-первых, циклы уже не в тренде, сейчас модно функциональное программирование.
Аргументация уровня журнала Cosmopolitan
Sirion
28.04.2017 11:08+8Такая аргументация называется "социальное доказательство". А когда её используют в таком контексте, это называется "ирония".
alvvi
28.04.2017 11:12Через цикл ведь все равно будет быстрее и короче, не?
Sirion
28.04.2017 11:15+4Ну, такие заявления нельзя делать без тестов. Нужно замерить перформанс в каждом конкретном случае.
alvvi
28.04.2017 12:42Не совсем понимаю, о каких конкретных случаях речь, я говорил о самом банальном сравнении, которое вы дали в начале.На любом тесте, который бы я не находил на jsPerf, цикл выигрывал с довольно большим отрывом. И да, я не делал заявлений, я как раз таки задал вопрос, так как самому интересно.
Sirion
28.04.2017 12:47Если отвечать серьёзно, то разумеется, цикл будет быстрее рекурсии. Я не уверен, можно ли как-то оптимизировать ещё сильнее, но из наивных реализаций цикл точно самый быстрый.
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
AlNi89
29.04.2017 10:41+1А разве без теста не очевидно, что в обоих случаях выполняется одно и то же действие (перемножение чисел), только при рекурсии программа «распухает» за счёт вызова функции (самой себя) и передачи (копирования) ей данных?
Sirion
29.04.2017 10:55Вообще да, но в данном случае нет. В то время, как наши космические корабли бороздят просторы вселенной, а в процессорах, компиляторах и интерпретаторах множатся неочевидные оптимизации, очевидных с точки зрения перформанса вещей становятся всё меньше. В комментарии выше я написал «разумеется», поскольку изучил вопрос и выяснил, что в современных js-движках рекурсия не оптимизирована. Без этого знания ответ не является очевидным.
ilay
28.04.2017 12:00Скажите пожалуйста, а зачем в примере с рекурсией второй параметр? И что в него передается при вызове?
fsou11
28.04.2017 12:32+2Для реализации хвостовой рекурсии
Sirion
28.04.2017 12:41Ну, собственно, да. Иначе можно было бы написать function factorial(n){return !n? 1: factorial(n-1)}. Но в таком случае, несмотря на то, что рекурсивный вызов стоит последним, это не будет хвостовой рекурсией, потому что последним вычисляемым выражением будет значение тернарного оператора.
REPISOT
28.04.2017 12:08-1Во-вторых, чем больше людей используют второй способ, тем быстрее в основных джаваскриптовых движках появится оптимизация
То есть давайте все ходить через лес, тогда там быстрее появится дорога.
LoadRunner
28.04.2017 12:16+2Там, где ходят люди, протаптываются тропинки этими самыми людьми. А потом там кладут асфальт и облагораживают дорожки.
REPISOT
28.04.2017 14:04Это если в 10 метрах уже не проложена дорога. По которой все ходят. И тут появляется такой человек, который хочет дорогу на 10 метров ближе к своему дому и говорит: ходите все через лес, в грязь, в снег, тогда через несколько лет тут будет дорога…
А имеющаяся дорога — это циклы.
acerikfy
28.04.2017 12:31-1Ваш код настолько идеален, что изобретает новую математику: по мнению вашего алгоритма, 50! = 3. В чем тогда смысл такого запутанного кода, который ни поддерживать, ни отлаживать невозможно?
Sirion
28.04.2017 12:34+1Ну, в некотором смысле это действительно 3. Если быть точным, 3.0414093201713376e+64.
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был быстрее обычного цикла.Sirion
28.04.2017 15:13Кстати да, я думал об этом, но потом самомодифицирующийся код захватил мою голову.
Melorian
28.04.2017 14:40Господи боже, мы наконец-то дожили до сложения чисел с помощью JQuery!
Сарказм, конечно же, но все-таки…
zagayevskiy
28.04.2017 15:36+1var 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;
Вот это вот? Выглядит солиднее? С кусками разметки? Это как в современном мире называется — шутка, сарказм или что?
hdfan2
28.04.2017 16:06+2Как-то слишком примитивно, я считаю. Нужно подключить несколько фреймворков, зафигачить с десяток микросервисов, общающихся через REST, утащить это всё в облако, подключить CDN… Короче, тема не раскрыта.
kahi4
28.04.2017 16:53+3const factorial = (n) => Math.sqrt(2 * Math.PI * n) * Math.pow((n / Math.E), n) * Math.exp(1 / (12 * n) - 1 / (360 * n * n * n));
Sirion
28.04.2017 17:00Ну, я в своём первом комментарии упоминал формулу Стирлинга
kahi4
28.04.2017 17:07Да, что-то пропустил. Но таким вот образом можно поставить в тупик неканоничным решением задачи.
Bessmertnii
Круто, прикольно, но где тут новый способ? Я вижу тут лишь необычную реализацию стандартного способа.
Sirion
А вы таки хотите способ вычисления факториала без перемножения чисел от 1 до N? Ну, можно по формуле Стирлинга, или через гамма-функцию Эйлера. Но это уже статья в другой хаб.