Ryan Dunton

Posted on Dec 17, 2018

Flattening an Array, a Performance Test

#javascript #arrays #performance

The Question

What is the most efficient way to flatten an array in Javascript? This questions comes up often in interviews and also has some practical use cases, which is rare for interview questions.

By "flattening" an array, we mean taking a multidimensional array and turning it into a regular "single" dimensional array. I'm not sure if that is the right phrasing but I'm going with it. See an example below.



let initialArray = [[0, 1], [2, 3], [4, 5]];

let flattenedArray = [0, 1, 2, 3, 4, 5]

Possible Solutions

So what is the most efficient way to go about this? Well I sketched out four possible solutions.

Solution 1: Concat + Apply



let flattenedArray = Array.prototype.concat.apply([], initialArray);

This is a fairly simple one line solution. We create a new array and concat each element onto it.

Solution 2: Use a Reduce



let flattenedArray = initialArray.reduce((a, b) => {
  return a.concat(b);
});

We execute a concat function on each first level element in the array. Then concat it onto the previous element. Giving us a new flattened array.

Solution 3: The Faithful Loop



let flattenedArray = [];
for (let i = 0; i < initialArray.length; i++) {
  let current = initialArray[i];
  for (let j = 0; j < initialArray.length - 1; j++)
    flattenedArray.push(current[j]);
}

The most basic solution. We loop through the first level arrays, loop through the internal arrays and push them up to an empty array. I should note, this is a lot more written code than our other solutions.

Solution 4: A ForEach Loop



let flattenedArray = [];
initialArray.forEach(entry => {
  flattenedArray = flattenedArray.concat(entry);
});

A little more modern approach. We loop through each first level array, concat it with the other and reassign the flattenedArray.

Testing the Results

So which is the fastest?

Full test results here . Wow! The old fashioned "for" loop was by far the fastest.

Going be a straight operations per second metric the classical for loop performs best! This was actually fairly shocking to me. Does anyone have a better flattening method?

Top comments (7)

Andrew • Dec 17 '18

You could speed it up a little by counting and pre-allocating the array. Because that's going to be the slowest part of the classical for loop - the array allocations attributed to the pushes. Something like:

let size = 0;
for (let i = 0; i < initialArray.length; i++) {
  let current = initialArray[i];
  for (let j = 0; j < initialArray.length - 1; j++)
    size++;
}


let flattenedArray = new Array(size);
let k = 0;
for (let i = 0; i < initialArray.length; i++) {
  let current = initialArray[i];
  for (let j = 0; j < initialArray.length - 1; j++)
    flattenedArray[k] = current[j];
    k++;
}

Anton Frattaroli • Oct 9 '19

Because some of the results bothered me, I took a look at the JSPerf. I saw some revisions to it since this article was posted. Erik Hughes found that for loop performance declines for large samples (10,000 arrays of 10 elements)

I modified the forEach a bit, found a solution that is middle-of-the-road performant regardless of array size (may be even better using push.apply over the spread operator):

small arrays - jsperf.com/flatten-array-tests-by-...
large arrays - jsperf.com/flatten-array-tests-by-...

rhymes • Dec 17 '18

Can you test with the spread operator too?

function flatten(array) {
  return [].concat(...array)
}

And also using Array.prototype.flat ?

array.flat()

This last one is not available in all browsers (no Edge or IE).

Ryan Dunton • Dec 17 '18

I updated the test suite to take in the spread operator and flat() tests, but it didn't seem to be marketly faster than the others, actually flat seems like it is the slowest so far. You can see the results here.

I actually hadn't heard of the flat() function until you mentioned it. I had trouble getting it to work in my local node environment but was able to work it in Chrome. Not sure why.

rhymes • Dec 17 '18

I actually hadn't heard of the flat() function until you mentioned it. I had trouble getting it to work in my local node environment but was able to work it in Chrome. Not sure why.

It's not supported by Node :D

Thanks for the updated info!