Возможно ли решить задачу без циклов?

Question

[lexstile]

Есть массив:

const array = [
	[1,4],
	[11],
	[3,5,7]
];
// 31

Нужно найти сумму его элементов (заранее неизвестны вложенность и количество элементов).
И можно ли вообще решить подобную задачу без циклов?
Под циклами я понимаю и стандартные методы js - reduce, forEach и т. д., которые под капотом используют цикл(-ы).

Comments

[Владлен Хеллсайт]

А почему без циклов? Задача на рекурсию?

[lexstile]

Владлен Хеллсайт, слишком просто и задача стоит именно такой)

Answer 1

[Сергей Соколов]

Возможно, но это извращение (никогда так не делайте!):

eval(JSON.stringify(array).replace(/[^\d]+/g, '+') + '0') // 31

Перевести массив в JSON-строку, все не-цифры заменить на знаки «+» и выполнить полученное выражение.

Например:

const a = [1, 2, [3, 4, [[5, 6], 7], 8]];
// Вжух! и получится строка:
"+1+2+3+4+5+6+7+8+"

Comments

[gcj]

ужас какой)

[Алексей Николаев]

Гениально. Смотрю на это и понимаю, что, попадись такой вопрос на собесе, я бы его завалил.

[Виталий]

Алексей Николаев, я хз стоит ли работать в фирмах, где любят велосипеды )))

[Сергей Соколов]

Виталий, может, так ищут умеющих взять на гитаре ми 2-й октавы не только стандартно 1-й на 12-м, или с флажолетом над 12-м, но и, скажем, на 6-й струне флажолетом над 2+ ладом )

Answer 2

[Владимир Проскурин]

Чтобы итерировать массив, всегда нужен минимум один цикл (если считать даже рекурсию таковой). Поэтому ответ - нет.
UPD: только это настолько бессмысленно, что даже вредит скорости. Я взял вариант Сергей Соколов и 0xD34F и добавил очевидный вариант

[].concat.apply([], array).reduce(function (res, item) { return res + item; })

И замерил их скорость.

const array = [
  [1,4],
  [11],
  [3,5,7]
];
function sum(arr) {
  if (!arr.length) {
    return 0;
  }
  let val = arr[0];
  if (val instanceof Array) {
    val = sum(val);
  }
  return val + sum(arr.slice(1));
}


console.time('eval');
for (let i = 0; i < 1000; i++) {
	eval(JSON.stringify(array).replace(/[^\d]+/g, '+') + '0') // 31
}
console.timeEnd('eval');

console.time('sum recursion');
for (let i = 0; i < 1000; i++) {
	sum(array);
}
console.timeEnd('sum recursion');


console.time('sum normal');
for (let i = 0; i < 1000; i++) {
	[].concat.apply([], array).reduce(function (res, item) { return res + item; })
}
console.timeEnd('sum normal');

На таком массиве при 1000 выполнений у меня вот такие результаты

eval: 44.69287109375ms
sum recursion: 2.64501953125ms
sum normal: 0.951904296875ms

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

Comments

[lexstile]

Через рекурсию можно, я имею ввиду без использования стандартный циклов - for, while, do while и т. д.

[lexstile]

На реальном проекте это использоваться не будет)
А то, что с циклом быстрее - я знал)
Тем не менее, благодарю за показательный анализ и выводы :)

[Виталий]

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

[Роман]

Владимир Проскурин

заранее неизвестны вложенность и количество элементов

Ваш вариант

[].concat.apply([], array).reduce(function (res, item) { return res + item; })

немного не доработан:)
он не верно обработает такой массив:

let array = [
	[1, 2],
	3, 4,
	[5, [6, 7]],
	[8, 9, 10]
];

Answer 3

[0xD34F]

Рекурсия:

const sum = (val, index = 0) =>
  val instanceof Array
    ? val.length > index
      ? sum(val[index]) + sum(val, index + 1)
      : 0
    : val;

Answer 4

[Александр]

Если превратить его в строку и удалить все скобочки - убрав вложенность, а потом заменить запятые на знаки + то можно сделать eval() и получить результат.

eval(JSON.stringify(array).replace(/\[/g,"").replace(/\]/g,"").replace(/,/g,"+"))

Comments

[Сергей Соколов]

great minds think alike )

Answer 5

[Роман]

Еще 1 вариант с рекурсией (правда он уничтожает исходный массив):

function sum(arr) {
	var val = arr.pop();
	if( !val ) return 0;
	if( Array.isArray(val)) return sum(val)  + sum(arr);
	return val + sum(arr);
}

демка:


PS: так же провел тесты:

код

let array = [];

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



function sum_1(arr) {
	if (!arr.length) {
		return 0;
	}
	let val = arr[0];
	if (val instanceof Array) {
		val = sum_1(val);
	}
	return val + sum_1(arr.slice(1));
}


function sum_2(arr) {
	var val = arr.pop();
	if (!val) return 0;
	if (Array.isArray(val)) return sum_2(val) + sum_2(arr);
	return val + sum_2(arr);
}

console.time('init array');
for (let i = 0; i < 1000; i++) {
	array = [
		[1, 4],
		[11],
		[3, 5, 7]
	];
}
console.timeEnd('init array');

console.time('eval');
for (let i = 0; i < 1000; i++) {
	array = [
		[1, 4],
		[11],
		[3, 5, 7]
	];
	eval(JSON.stringify(array).replace(/[^\d]+/g, '+') + '0') // 31
}
console.timeEnd('eval');

console.time('sum recursion 1');
for (let i = 0; i < 1000; i++) {
	array = [
		[1, 4],
		[11],
		[3, 5, 7]
	];
	sum_1(array);
}
console.timeEnd('sum recursion 1');


console.time('sum normal');
for (let i = 0; i < 1000; i++) {
	array = [
		[1, 4],
		[11],
		[3, 5, 7]
	];
	[].concat.apply([], array).reduce(function(res, item) {
		return res + item;
	})
}
console.timeEnd('sum normal');



console.time('sum recursion 2');
for (let i = 0; i < 1000; i++) {
	array = [
		[1, 4],
		[11],
		[3, 5, 7]
	];
	sum_2(array);
}
console.timeEnd('sum recursion 2');

init array: 0.615ms
eval: 6.717ms
sum recursion 1: 6.927ms
sum normal: 1.921ms
sum recursion 2: 3.753ms

из которых видно что второй вариант рекурсии достаточно быстрый