Вместо использования циклов Arrayобъект JavaScript является достаточно мощным средством для создания последовательностей . А как насчет более сложных серий, а не просто списка последовательных цифр или букв? К счастью, у нас еще есть функции другого массива , например filter, map, every, и reduceв нашем распоряжении. Они могут быть использованы для генерации списка простых чисел , вычисления факториала и получения ряда Фибоначчи .
Простые числа
Простые числа завораживают, в частности потому, что концепция очень проста, и, тем не менее, существует множество способов справиться с ними, так что задачи часто используются в интервью для решения проблем. Каждый программист JavaScript, достойный ее соли, должен иметь возможность найти простой способ проверить, является ли данное целое число i простым числом или нет. Одно возможное решение на основе цикла при i> = 2 задается следующим образом:
function isPrime(i) {
for (var c = 2; c < = Math.sqrt(i); ++c)
if (i % c === 0) return false;
return true;
}
Вышеприведенная реализация теста простоты , вероятно, не самая оптимальная, достаточно проиллюстрировать концепцию.
Следующей задачей этой функции является печать всех простых чисел от 0 до N :
function primeList(N) {
var list = [];
for (var i = 2; i != N; ++i)
if (isPrime(i)) list.push(i);
return list;
}
Мы уже узнали, что некоторые основанные на циклах итерации могут быть превращены в однострочники Array. Можем ли мы применить ту же технику к вышеуказанной проблеме?
Давайте решать isPrime()сначала. Подходящим решением здесь является использование Array.prototype.every . В разделе 15.4.4.16 спецификация ECMAScript 5.1 гласит:
каждый вызывает callbackfn один раз для каждого элемента, присутствующего в массиве, в порядке возрастания, пока не найдет элемент, где callbackfn вернет false. Если такой элемент найден, каждый сразу возвращает false. В противном случае, если callbackfn вернул true для всех элементов, каждый вернет true.
Другими словами, мы можем использовать everyдля проверки каждого потенциального делителя и посмотреть, является ли один из них делителем для кандидата. Если да, очевидно, что кандидат не простое число, и нам просто нужно немедленно выручить. Если после исчерпывающего поиска есть подходящий делитель, это означает, что мы находим наше простое число.
Удивительно, но код короче приведенного выше объяснения. Кроме того, ~~вместо какой- Math.floorто дополнительной загадки используется трюк .
function isPrime(i) {
return (i > 1) && Array.apply(0, Array(1 + ~~Math.sqrt(i))).
every(function (x, y) { return (y < 2) || (i % y !== 0) });
}
Другая функция primeList()довольно проста для рефакторинга. Вспомните еще раз подход с использованием комбинации конструктора Array apply, и mapмы в итоге получим следующее окончательное решение. Обратите внимание, что тест на простоту теперь встроен с помощью Array.prototype.filter .
function primeList(N) {
return Array.apply(0, Array(N)).map(function (x, y) { return y }).
filter(function (i) {
return (i > 1) && Array.apply(0, Array(1 + ~~Math.sqrt(i))).
every(function (x, y) { return (y < 2) || (i % y !== 0) });
});
}
(Красавка) сочетание map, filterи everyдостаточно очевидно , чтобы избежать петли!
Если вы заботитесь о готовящемся выпуске ECMAScript 6 , использование функции со стрелкой и понимания массива позволяет записать вышеуказанную конструкцию в виде:
function primeList(N) {
return [for (i of Array.apply(0, Array(N)).map((x, y) => y))
if ((i > 1) && Array.apply(0, Array(1 + ~~Math.sqrt(i))).
every((x, y) => (y < 2) || (i % y !== 0) ))
i];
}
Факториал
Вычислительный факториал — еще одна интригующая математическая деятельность. Фактически, из-за своей природы, это становится обычным упражнением для введения в рекурсивное программирование. А сейчас давайте сосредоточимся на нерекурсивной реализации, что-то вроде:
function factorial(n) {
var f = 1;
for (var c = 1; c < = n; ++c) f *= c;
return f;
}
Здесь, если мы хотим избежать императивного стиля использования цикла, стратегия будет другой. Поскольку вычисление факториала n зависит от всех предыдущих значений, мы не можем просто использовать mapили даже everyкак в предыдущем примере. Для этого нам нужна помощь Array.prototype.reduce . В разделе 15.4.4.21 спецификации есть, что сказать об этой функции высшего порядка:
callbackfn вызывается с четырьмя аргументами: previousValue (или значение из предыдущего вызова callbackfn), currentValue (значение текущего элемента), currentIndex и просматриваемый объект.
Вероятно, это легче понять reduceиз следующей простой иллюстрации:
[1, 2, 3, 4, 5].reduce(function (x, y) { return x + y }); // 15
[1, 2, 3, 4, 5].reduce(function (x, y) { return x + y }, 100); // 115
Из-за x + yвышеприведенного кода по существу выдает сумму каждого числа в массиве. Здесь x соответствует предыдущему значению, а y — текущему значению (которое будет изменяться от 1 до 5). В этом контексте представьте, что х действует как аккумулятор. Обратите внимание также, что reduceможет принимать необязательный второй аргумент, который станет начальным значением. В приведенном выше примере 100 это сместит вычисленную сумму.
Мы также можем сделать что-то вроде следующего. Не только элемент массива (текущее значение, y ) используется, обратный вызов также использует индекс элемента, переданный в качестве третьего аргумента z .
[14, 3, 77].reduce(function(x, y, z) { return x + y * z }, 0); // 0*14 + 1*3 + 2*77
Если вы сделаете это так далеко, вы, вероятно, уже придумали решение проблемы факториала. Вот примерная реализация. Обратите внимание на возвращаемое значение обратного вызова, оно не является простым, потому что индекс элемента z начинается с 0, а не с 1.
function factorial(n) {
return Array.apply(0, Array(n)).reduce(function(x, y, z) { return x + x * z; }, 1);
}
Как обычно, вот версия ECMAScript 6 с функцией стрелки:
function factorial(n) {
return Array.apply(0, Array(n)).reduce((x, y, z) => x + x * z, 1);
}
Наконец, для сравнения смотрите также этот твит от Ангуса Кролла ( @angustweets ). Для другого варианта ознакомьтесь с версией Джеда Шмидта ( @jedschmidt ), где сама функция также используется в качестве обратного вызова для reduce.
Серия Фибоначчи
Этот короткий трактат неполон без ряда Фибоначчи , часто связанного с ростом популяции кроликов. Идея чисел Фибоначчи относительно проста, но с ней могут быть связаны десятки головоломных задач программирования.
Если попросить показать первые n чисел Фибоначчи, ее реализация может выглядеть так:
function fibo(n) {
var f = [];
for (var c = 0; c < n; ++c) {
f.push((c < 2) ? c : f[c-1] + f[c-2]);
}
return f;
}
Если мы хотим переключить реализацию для использования Arrayобъекта JavaScript , ситуация с двумя предыдущими значениями становится реальной проблемой. Опираясь на reduceбудет сложно , так как его обратного вызова получает только одно предыдущее значение. Кроме того, мы можем взглянуть на последние два значения из последнего аргумента обратного вызова, через который перемещается массив, потому что этот массив неизменен (в конце концов, это функциональное программирование).
К счастью, мир программирования полон волшебных трюков и секретных переходов. Среди других возможностей, одна хитрость, которую мы можем продолжать использовать, reduceэто использовать (пустой) массив в качестве начального значения. Фактически, этот массив будет содержать окончательный ряд Фибоначчи. Так как мы продолжаем хранить больше чисел в этом массиве, просмотр двух предыдущих чисел становится очень простым. На самом деле, полный код для этого совсем не скучен.
function fibo(n) {
return Array.apply(0, Array(n)).
reduce(function(x, y, z){ return x.concat((z < 2) ? z : x[z-1] + x[z-2]); }, []);
}
Обновление: оригинальная версия содержит, mapно Джед Шмидт ( @jedschmidt ) любезно указал, что в этом нет необходимости, потому что мы просто хотим использовать индекс элемента, а нам не важно само значение элемента.
Переписав выше функции для использования ECMAScript 6 «s массив понимания и функции стрелка остается в качестве упражнения для читателя.
Наконец, если вы все еще подвергаете сомнению мощь объекта Array JavaScript, подумайте еще раз. Среди смертных вторые мысли — самые мудрые.