14
\$\begingroup\$

Problem: Concat all sub-arrays of a given array.

Example input: [[0, 1], [2, 3], [4, 5]]

Example output: [0, 1, 2, 3, 4, 5]

Solution A: Use a loop

var flattened=[];
for (var i=0; i<input.length; ++i) {
    var current = input[i];
    for (var j=0; j<current.length; ++j)
        flattened.push(current[j]);
}

Solution B: Use reduce

var flattened = input.reduce(function(a, b) {
    return a.concat(b);
}, []);

Solution B looks much shorter and easier to understand, but, it seems to be much more resource-wasteful - for each element of the input, a new array is created - the concatenation of a and b. On the contrary, solution A uses a single array 'flattened', which is updated during the loop.

So, my question is: which solution is better? Is there a solution that combines the best of both worlds?

\$\endgroup\$
  • 5
    \$\begingroup\$ Typical solution is Array.prototype.concat.apply([],input) \$\endgroup\$ – elclanrs Jan 26 '14 at 10:08
  • \$\begingroup\$ @elclanrs this should be an answer. \$\endgroup\$ – Sukima Nov 20 '14 at 4:21
  • 1
    \$\begingroup\$ @elclanrs - This solution fails if there are a large number of arrays in input because it overflows the call stack. Otherwise, you are correct. \$\endgroup\$ – Centijo Mar 14 '15 at 15:54
10
\$\begingroup\$

Here is the performance test for these two and couple more approaches (one suggested by @elclanrs in the comments).

The performance differences will vary significantly across different browsers, and even different version on same browser, as browser these days try to optimize javascript very aggressively.

Unless you are dealing with very large arrays or this operation is performed repeatedly in quick succession, I would suggest you to use simplest and clearest approach. But, that being said the loop solution is also not that complex or big anyway (and it performs better than others especially on firefox)

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks a lot! It seems that a loop is indeed the most efficient approach, as I thought. \$\endgroup\$ – Erel Segal-Halevi Jan 26 '14 at 17:04
  • \$\begingroup\$ forEach+push is actually doing nothing. \$\endgroup\$ – André Werlang Feb 23 '15 at 14:49
6
\$\begingroup\$

Taking @elclanrs solution in the comments above and modifying slightly to overcome the limitations with ultra long arrays and argument expansion, you could use something like this:

function flattenLongArray(input) {
    var LIMIT = 32768;
    var end, result = [];


    for(var i = 0; i < input.length; i+=LIMIT) {
        end = Math.min(i+LIMIT, input.length) - 1;
        Array.prototype.concat.apply(result, input.slice(i, end));
    }

    return result;
}

This is admittedly verbose, but it works.

\$\endgroup\$
  • \$\begingroup\$ Sorry my friend, can you explain a little bit more this code? I can't understand why the use of LIMIT = 32768 \$\endgroup\$ – robe007 May 29 '18 at 19:38
  • \$\begingroup\$ The limit is there to overcome the stack limitation. For arrays larger than 32768, applying the concat function like this will result in the JS engine throwing an error because the call stack will exceed the 32k limit as it recurses. See my comment to elclanrs regarding his solution using concat in the discussion at the top. If you are never going to encounter arrays that large, the limit checking code isn't needed and you can just use concat directly. \$\endgroup\$ – Centijo May 30 '18 at 15:31
  • \$\begingroup\$ I want to add that the limit may vary depending on the JavaScript engine implementation. My chosen limit of 32768 is probably quite generous and should be lower. Here is an SE link which lists JavaScript stack limits in various browser versions. \$\endgroup\$ – Centijo May 30 '18 at 15:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.