Пятничный JS: единственно верный способ вычисления факториала
- суббота, 29 апреля 2017 г. в 03:14:27
javascript
https://habrahabr.ru/post/327544/
Вычисление факториала — одна из традиционных программистских задач для собеседований. Если вдруг кто забыл, факториал натурального числа N обозначается как N! и равняется произведению всех натуральных чисел от единицы до N включительно. Например, . Казалось бы, что тут сложного? Однако есть свои нюансы.
Например, сравним два самых распространённых способа вычисления факториала.
Многие скажут, что первый способ лучше, но это не так. Во-первых, циклы уже не в тренде, сейчас модно функциональное программирование. Во-вторых, чем больше людей используют второй способ, тем быстрее в основных джаваскриптовых движках появится оптимизация хвостовой рекурсии.
В любом случае, оба эти способа слишком примитивны, чтобы по ним судить о знаниях кандидата. А вот опытный разработчик на React.js уже может написать что-то в этом роде:
Согласитесь, выглядит гораздо солиднее. Впрочем, невооружённым глазом видно, что это всего лишь вариант рекурсивного вычисления. Сходство станет ещё сильнее, если переписать Factorial как функциональный компонент. И, разумеется, я не стал бы писать этот хабрапост, если бы не был готов предложить нечто принципиально новое.
Какую из возможностей Javascript недолюбливают и недооценивают сильнее всего? Недолюбливают настолько, что про неё даже придумали специальную поговорку? Конечно же, это eval. Можно сказать, что eval — это тёмная сторона Силы. А как мы помним из фильмов Джорджа Лукаса, нет ничего более крутого и впечатляющего, чем тёмная сторона Силы, поэтому давайте попробуем ей овладеть.
Можно было бы запихнуть в строку какой-нибудь из методов, приведённых в начале поста, а затем передать эту строку в eval, но в этом не было бы новизны. Поставим задачу таким образом, чтобы сделать этот хак невозможным. Пусть у нас есть такой вот каркас:
— и мы хотим, внеся изменения лишь в литерал строки f, сделать так, чтобы функция factorial взаправду вычисляла факториал. Вот задача, достойная истинного ситха.
Нам нужен код, который возвращает код, который возвращает код… Если забыть про конечную задачу — вычисление факториала, то есть одна хорошо известная штука, которая нам подойдёт. Эта штука называется квайн — программа, которая выводит свой собственный текст.
Про квайны на Хабре написано уже немало, потому я напомню лишь основные принципы квайностроительства. Чтобы сделать простейший квайн, нам нужно:
Вооружившись этим знанием, можно написать следующий квайн на js (отступы и переносы строки добавлены для удобства читателя):
В строке o.s содержится весь остальной код, а также специальные подстановочные последовательности, начинающиеся с подчёркивания. Страшное выражение внутри console.log заменяет каждую подстановочную последовательность на соответствующее свойство объекта o, что обеспечивает выполнение пунктов 2 и 3 хитрого плана по созданию квайна.
Как же сделать так, чтобы наш квази-квайн модифицировал сам себя, а в результате превратился в одно-единственное число? Давайте забудем пока про вычисление факториала и постараемся просто написать строку, которая «схлопывается» через определённое количество eval'ов. Для этого нам понадобится:
Выглядеть это будет примерно так:
Обратите внимание на отсутствие return внутри строки: в нём нет необходимости, eval возвращает значение последнего выражения. Запустив этот код в консоли, можно c благоговением наблюдать, как с каждой итерацией цикла значение n уменьшается на 1. Если кто-то скажет, что для такого эффекта достаточно:
После этого подготовительного этапа уже совсем нетрудно написать итоговую версию вычисления факториала. Просто добавляется ещё одна переменная и чуть усложняется строчка с изменением.
Теперь вы можете смело идти на собеседование.
С живым кодом можно поиграться здесь. Как и в прошлой статье из рубрики «Пятничный JS» напоминаю: если вы сделаете что-нибудь подобное на продакшене, то попадёте в ад. С другой стороны, если вы сделаете это на собеседовании, то вам не дадут возможности сделать это на продакшене, и вы не попадёте в ад. Так что делайте это на собеседовании. Спасибо за внимание.
- Ненормальное программирование
- JavaScript
Введение
Вычисление факториала — одна из традиционных программистских задач для собеседований. Если вдруг кто забыл, факториал натурального числа 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 хитрого плана по созданию квайна.
Лирическое отступление
Здесь меня могут поправить: товарищ, это не простейший квайн, а монстр какой-то. Простейший квайн на 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» напоминаю: если вы сделаете что-нибудь подобное на продакшене, то попадёте в ад. С другой стороны, если вы сделаете это на собеседовании, то вам не дадут возможности сделать это на продакшене, и вы не попадёте в ад. Так что делайте это на собеседовании. Спасибо за внимание.