DEV Community

Ryan Dunton
Ryan Dunton

Posted on

Flattening an Array, a Performance Test

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]


Enter fullscreen mode Exit fullscreen mode

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);


Enter fullscreen mode Exit fullscreen mode

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);
});


Enter fullscreen mode Exit fullscreen mode

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]);
}


Enter fullscreen mode Exit fullscreen mode

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);
});


Enter fullscreen mode Exit fullscreen mode

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.

Test results

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)

Collapse
 
areddish profile image
Andrew

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++;
}
Collapse
 
antonfrattaroli profile image
Anton Frattaroli

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):

Collapse
 
rhymes profile image
rhymes

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).

Collapse
 
ryan_dunton profile image
Ryan Dunton

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.

Collapse
 
rhymes profile image
rhymes

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!

Collapse
 
yaireo profile image
Yair Even Or

All these tests need to take the depth parameter into account, because the default is 1....

Collapse
 
ayoubkhial94 profile image
ayoubkhial94 • Edited

For me the concat-apply method is the fastest by far.

here's the test data: jsben.ch/z6nnv