У меня были проблемы с пониманием reduce( ) и рекурсии в JavaScript, так что я написал эту статью чтобы объяснить их в первую очередь себе (эй, смотрите, это же рекурсия!). Эти концепции имеют некоторые сходства с приготовлением яблочного пирога. Я очень надеюсь вы сочтёте мои примеры как полезными так и аппетитными.
Дан массив содержащий вложенные массивы:
Как результат мы хотим получить:
Если мы знаем максимальное количество вложенных массивов, с которыми нам предстоит работать (в примере их 4), то нам вполне подойдёт цикл for для итерации по каждому элементу массива, а затем оператор if, чтобы проверить является ли этот элемент сам по себе массивом, и так далее…
Что в принципе работает, но тяжело как для чтения, так и для понимания. Более того это работает только в случае, когда известно количество вложенных массивов. И вы вообще можете вообразить каково дебажить весь это бардак (даже сейчас кажется что я где-то лишнее i поставил).
К счастью у JavaScript есть пару методов для того чтобы сделать наш код понятнее и проще. Один из таких методов reduce( ). И выглядеть это всё будет вот так:
Получилось куда меньше кода, но мы пропускаем некоторые (в нашем примере один) вложенные массивы. Давайте вместе пошагово разберём как работает reduce ( ) и посмотрим что же он всё-таки делает, чтобы исправить это.
Это не так сложно, как кажется. Давайте поговорим о reduce ( ) как о чём-то вне работы разработчика. Знакомьтесь, это Адам. Основная функция Адама состоит в том, чтобы взять яблоки из кучи, помыть их, а затем поместить одно за другим в корзину. Эта корзина блестящих яблок предназначена для того, чтобы стать вкусными яблочными пирогами. Это очень важная работа.
Яблоки + Человеческие усилия = Пирог. Не путайте формулу с рецептом яблоко-человеческого пирога, он не столь вкусный.
В приведённом выше примере куча яблок — это наш массив arr. Корзина — это переменная done, аккумулятор. Начальным значением done является пустой массив, который мы видим как [] последним параметром нашего reduce( ). Яблоко, которое Адам в данный момент моет — это curr (от current). Как только Адам заканчивает мыть текущее яблоко он кладёт его в корзину (мы делаем это с помощью .concat( ) ). Когда гора яблок заканчивается Адам отдаёт корзину с чистыми яблоками нам и идёт домой к своему коту.
Ну что же, по итогу работы Адама мы имеем корзину чистых яблок и всё, вроде бы даже отлично. Но нам всё ещё нужно разобраться с этими вложенными массивами. Возвращаясь к нашей аналогии: предположим что некоторые яблоки были настолько хороши, что они упакованы в отдельные коробки ещё при продаже. Внутри каждой коробки могут быть ещё яблоки и ещё коробки, содержащие яблоки и коробки поменьше.
Прелестные, слегка перекошенные яблоки просто хотят быть любимыми / съеденными.
Вот что мы хотим от нашей яблоко-обрабатывающей функции/Адама:
Рекурсивная функция с reduce( ) будет выглядеть так:
Терпение и я всё объясню.
Если вы посмотрите на наш код выше, вы увидите, что flatten () появляется дважды. В первый раз, когда он появляется, он говорит Адаму, что делать с кучей яблок. Во второй раз он рассказывает ему, что делать с тем, что он сейчас держит, давая указания в случае, если это яблоко и в случае, если это не яблоко. Следует отметить, что эти инструкции являются повторением первоначальных инструкций, с которых мы начали — и это рекурсия.
Для ясности разберём всё строчка за строчкой:
И мы закончили! Мы перешли от 24-строкового, 4-слойного-вложенного цикла for к более сжатому и лаконичному 9-строчному рекурсивному решению. Reduce и рекурсия могут поначалу показаться сложными для понимания, но это ценные инструменты которые в будущем сэкономят вам множество усилий как только вы их поймёте.
И не беспокойтесь об Адаме, нашем неработающем разработчике. Он получил так много внимания после этой статьи, что он открыл свою собственную фабрику яблочных пирогов, управляемую AI. Он очень доволен.
+1 вам, если ожидали шутку про Адамово Яблоко.
Данная статья рискует констатировать очевидные вещи. Но следует задать вопрос: «Очевидные для кого?».
Впервые делаю перевод статьи, от того буду благодарен за любые правки, исправения и указание на недочёты.
Дан массив содержащий вложенные массивы:
var arr = [1, [2], [3, [[4]]]]Как результат мы хотим получить:
var flat = [1, 2, 3, 4]Использование цикла for и оператора if.
Если мы знаем максимальное количество вложенных массивов, с которыми нам предстоит работать (в примере их 4), то нам вполне подойдёт цикл for для итерации по каждому элементу массива, а затем оператор if, чтобы проверить является ли этот элемент сам по себе массивом, и так далее…
function flatten() {
var flat = [];
for (var i=0; i<arr.length; i++) {
if (Array.isArray(arr[i])) {
for (var ii=0; ii<arr[i].length; ii++) {
if (Array.isArray(arr[i][ii])) {
for (var iii=0; iii<arr[i][ii].length; iii++) {
for (var iiii=0; iiii<arr[i][ii][iii].length; iiii++) {
if (Array.isArray(arr[i][ii][iii])) {
flat.push(arr[i][ii][iii][iiii]);
} else {
flat.push(arr[i][ii][iii]);
}
}
}
} else {
flat.push(arr[i][ii]);
}
}
} else {
flat.push(arr[i]);
}
}
}
// [1, 2, 3, 4]
Что в принципе работает, но тяжело как для чтения, так и для понимания. Более того это работает только в случае, когда известно количество вложенных массивов. И вы вообще можете вообразить каково дебажить весь это бардак (даже сейчас кажется что я где-то лишнее i поставил).
Использование reduce.
К счастью у JavaScript есть пару методов для того чтобы сделать наш код понятнее и проще. Один из таких методов reduce( ). И выглядеть это всё будет вот так:
var flat = arr.reduce(function(done,curr){
return done.concat(curr);
}, []);
// [ 1, 2, 3, [ [ 4 ] ] ]
Получилось куда меньше кода, но мы пропускаем некоторые (в нашем примере один) вложенные массивы. Давайте вместе пошагово разберём как работает reduce ( ) и посмотрим что же он всё-таки делает, чтобы исправить это.
Array.prototype.reduce()
Метод reduce() применяет функцию к аккумулятору и каждому значению массива (слева-направо), сводя его к одному значению. (MDN)
Это не так сложно, как кажется. Давайте поговорим о reduce ( ) как о чём-то вне работы разработчика. Знакомьтесь, это Адам. Основная функция Адама состоит в том, чтобы взять яблоки из кучи, помыть их, а затем поместить одно за другим в корзину. Эта корзина блестящих яблок предназначена для того, чтобы стать вкусными яблочными пирогами. Это очень важная работа.
Яблоки + Человеческие усилия = Пирог. Не путайте формулу с рецептом яблоко-человеческого пирога, он не столь вкусный.
В приведённом выше примере куча яблок — это наш массив arr. Корзина — это переменная done, аккумулятор. Начальным значением done является пустой массив, который мы видим как [] последним параметром нашего reduce( ). Яблоко, которое Адам в данный момент моет — это curr (от current). Как только Адам заканчивает мыть текущее яблоко он кладёт его в корзину (мы делаем это с помощью .concat( ) ). Когда гора яблок заканчивается Адам отдаёт корзину с чистыми яблоками нам и идёт домой к своему коту.
Использование reduce( ) рекурсивно для обращения к вложенным массивам.
Ну что же, по итогу работы Адама мы имеем корзину чистых яблок и всё, вроде бы даже отлично. Но нам всё ещё нужно разобраться с этими вложенными массивами. Возвращаясь к нашей аналогии: предположим что некоторые яблоки были настолько хороши, что они упакованы в отдельные коробки ещё при продаже. Внутри каждой коробки могут быть ещё яблоки и ещё коробки, содержащие яблоки и коробки поменьше.
Прелестные, слегка перекошенные яблоки просто хотят быть любимыми / съеденными.
Вот что мы хотим от нашей яблоко-обрабатывающей функции/Адама:
- Если куча яблок это куча яблок, то возьми яблоко из кучи.
- Если то что ты взял — это яблоко, то мой его и клади в корзину.
- Если то что ты взял — коробка, то открой коробку. Если в коробке яблоко иди к шагу 2.
- Если же в коробке другая коробка, то иди к шагу 3.
- Когда от кучи яблок не осталось и следа отдай нам корзину.
- Если куча яблок совсем не куча яблок, то отдай это, чем бы они ни было.
Рекурсивная функция с reduce( ) будет выглядеть так:
function flatten(arr) {
if (Array.isArray(arr)) {
return arr.reduce(function(done,curr){
return done.concat(flatten(curr));
}, []);
} else {
return arr;
}
}
// [ 1, 2, 3, 4 ]Терпение и я всё объясню.
Рекурсия
Действия функции сопровождающееся вызовом самой себя. Рекурсия используется для решения проблем, которые содержат более мелкие проблемы. Рекурсивная функция, как правило, принимает два атрибуита: базовый регистр (конец рекурсии) или рекурсивный регистр (продолжается рекурсия). (MDN)
Если вы посмотрите на наш код выше, вы увидите, что flatten () появляется дважды. В первый раз, когда он появляется, он говорит Адаму, что делать с кучей яблок. Во второй раз он рассказывает ему, что делать с тем, что он сейчас держит, давая указания в случае, если это яблоко и в случае, если это не яблоко. Следует отметить, что эти инструкции являются повторением первоначальных инструкций, с которых мы начали — и это рекурсия.
Для ясности разберём всё строчка за строчкой:
- function flatten(arr) { — мы называем нашу общую функцию и указываем что она примет аргумент arr.
- if (Array.isArray(arr)) { — мы проверяем является ли полученное массивом.
- return arr.reduce(function(done,curr){ — если предыдущая строка возвращает true и аргумент является массивом вы передаём его в reduce ( ) — это наш рекурсивный регистр.
- return done.concat(flatten(curr)); — неожиданный поворот сюжета! Функция, которую мы вызываем — это та самая функция в которой мы находимся сейчас. Вкратце: начинайте заново с самого верха.
- }, []); — мы говорим нашей функции reduce начинать с пустого аккумулятора (done) и помещать то, что вернёт функция именно в него.
- } else { — это разрешает те случаи когда строка 2 возвращает false, то есть когда аргумент не является массивом.
- return arr; — вернуть то, чему бы arr не было бы равно (предположительно чистому яблоку). Это уже на базовый регистр, который выводит нас из рекурсии.
- } — завершение блока else.
- } — завершение общей функции.
И мы закончили! Мы перешли от 24-строкового, 4-слойного-вложенного цикла for к более сжатому и лаконичному 9-строчному рекурсивному решению. Reduce и рекурсия могут поначалу показаться сложными для понимания, но это ценные инструменты которые в будущем сэкономят вам множество усилий как только вы их поймёте.
И не беспокойтесь об Адаме, нашем неработающем разработчике. Он получил так много внимания после этой статьи, что он открыл свою собственную фабрику яблочных пирогов, управляемую AI. Он очень доволен.
+1 вам, если ожидали шутку про Адамово Яблоко.
Данная статья рискует констатировать очевидные вещи. Но следует задать вопрос: «Очевидные для кого?».
Впервые делаю перевод статьи, от того буду благодарен за любые правки, исправения и указание на недочёты.
Поделиться с друзьями
Комментарии (11)
kahi4
01.06.2017 18:37+2Ваш пример — отличный пример подмены понятий. Никаких сложностей переписать for на такую-же рекурсивную форму, как ваш reduce нет, и, соответственно, нет перечисленных проблем. Да еще и намеренно написан ужасный нечитаемый код. Нда.
И опять же, в первом случае у вас не создается сотен промежуточных массивов, что потребление памяти, что время выполнения меньше, даже если переписать на рекурсию (передавая var flat = [] как параметр).
Fen1kz
01.06.2017 18:47+2Я как-то против вашего решения.
Если начал использовать функциональный подход, то становится трудно остановиться, а вы решились на reduce и тут же остановились на грязной функции
flatten у вас делает слишком много работы — она и самим array занимается, и лезет в его вещи и там шурует и объявляет ещё функции внутри и создает кучу всего.
Предлагаю такую функцию:
var flattenReduceArray = (result, item) => Array.isArray(item) ? item.reduce(flattenReduceArray, result) : [...result, item]
Читабельный ES5 вариант:
function flattenReduceArrayES5 (result, item) { if (Array.isArray(item)) { return item.reduce(flattenReduceArrayES5, result) } else { result.push(item); return result; } }
Во-первых, не создается никаких функций и промежуточных массивов — все пишется в один массив
Во-вторых, функция занимается исключительно элементами массива и ничем больше.
В-третьих — она быстрее. Я тут ради эксперимента попробовал использовать jsperf, если кто-то может посмотреть и сказать что я таки правильно посчитал — буду благодарен.
TheShock
01.06.2017 18:52+6Если мы знаем максимальное количество вложенных массивов, с которыми нам предстоит работать (в примере их 4), то нам вполне подойдёт цикл for для итерации по каждому элементу массива, а затем оператор if, чтобы проверить является ли этот элемент самим массивом, и так далее…
function flatten() { var flat = []; for (var i=0; i<arr.length; i++) { if (Array.isArray(arr[i])) { for (var ii=0; ii<arr[i].length; ii++) { if (Array.isArray(arr[i][ii])) { for (var iii=0; iii<arr[i][ii].length; iii++) { for (var iiii=0; iiii<arr[i][ii][iii].length; iiii++) { if (Array.isArray(arr[i][ii][iii])) { flat.push(arr[i][ii][iii][iiii]); } else { flat.push(arr[i][ii][iii]); } } } } else { flat.push(arr[i][ii]); } } } else { flat.push(arr[i]); } } } // [1, 2, 3, 4]
Слишком мало вложенности, хипстеры могут не клюнуть! Давайте вручную напишем цикл глубиной в 20! А еще лучше глубиной в 30 элементов!
Блин, автор, неужели вы считаете своих читателей такими идиотами, что скармливаете им такую ересь? Это уже просто оскорбительно!
пс. да, это перевод.TheShock
01.06.2017 19:23То есть те двое, кто меня минусанули считают, что в императивном стиле пишут именно так? Серьезно?
AngReload
02.06.2017 08:16+3Я думаю иперативно можно написать так:
let arr = [1, [2], [3, [[4]]]]; while (arr.some(Array.isArray)) { arr = [].concat(...arr); } console.log(arr);
Sirion
02.06.2017 13:22Дорогой дневник! Сегодня я узнал, что Array#concat принимает больше одного аргумента. Это знание изменит мою жизнь. Или нет, но всё равно прикольно.
justboris
02.06.2017 15:15В вашем подходе будет много лишних проходов по массиву в
arr.some(Array.isArray). В рекурсивном варианте такого не случитсяAngReload
02.06.2017 18:42Быстрее, чем вариант из статьи (в Chrome и Edge), рекурсия — это тоже не бесплатно:
https://jsperf.com/flatten2
Но в Firefox — худший. И в целом не лучший, особенно в сравнении с flattenReduceArrayES5 от Fen1kz
Но, согласитесь, ни одной новой переменной, даже функции нет, простой однострочник, TheShock правильно подметил, что автор нас пытается ввести в заблуждение.
baldrs_asgaardson
05.06.2017 12:41+1C римскими цифрами вместо i: XVIII, XIX, XX… Я всегда думал, что лучше писать как в математике, i, j, k и т.д., а тут вот какой пример страшный.
Tynnopet
05.06.2017 12:41А можно использовать js «магию»:
const arr = [1, [2], [3, [[4]]]] const result = arr.toString().split(',').map(el => parseInt(el)); console.log(result); // [1, 2, 3, 4]
Sirion
С одной стороны, очень хочется оставить едкий комментарий типа «когда будет статья про понимание Array.length?». С другой, я действительно нередко наблюдал, как начинающие погромисты тупят при знакомстве с reduce. В следующий раз попробую подвергнуть такого человека чтению этой статьи.