Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Flatten an array in Javascript without recursion
'use strict'
var Benchmark = require('benchmark')
var suite = new Benchmark.Suite;
var list = [1, 2, 3, [[4]], [[[5]]], [6], [[7]]]
function flattenRecursive (list) {
var flatList = []
list.forEach(function (item) {
if (item instanceof Array === true) {
flatList = flatList.concat(flattenRecursive(item))
} else {
flatList.push(item)
}
})
return flatList
}
function flatten (list) {
var clonedList = list.slice(0)
var flatList = []
while (clonedList.length) {
var item = clonedList.shift()
if (item instanceof Array === true) {
clonedList = item.concat(clonedList)
} else {
flatList.push(item)
}
}
return flatList
}
suite.add('flattenRecursive', function() {
flattenRecursive(list)
})
.add('flatten', function() {
flatten(list)
})
.on('cycle', function(event) {
console.log(String(event.target));
})
.on('complete', function() {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run()
@jacoborus

This comment has been minimized.

Copy link

jacoborus commented Apr 21, 2016

Your tests are running over an empty array. Try this in every test instead passing list var:

function getList () {
  return [1, 2, 3, [[4]], [[[5]]], [6], [[7]]]
}
.add('flatten', function() {
  flatten(getList())
})
@Hypercubed

This comment has been minimized.

Copy link

Hypercubed commented Apr 22, 2016

@thetutlage I think the majority of the performance difference between the flattenRecursive and flatten is that .forEach is very slow. Try this:

function flattenRecursive2 (arr) {
  var flatList = []
  var i = -1;
  var len = arr.length - 1;
  while (i++ < len) {
    if (Array.isArray(arr[i])) {
      flatList = flatList.concat(flattenRecursive2(arr[i]))
    } else {
      flatList.push(arr[i])
    }
  }
  return flatList;
}

or how about how about:

function flattenRecursive3(array) {
  return (function traverse(arr, flatList) {
    var i = -1;
    var len = arr.length - 1;
    while (i++ < len) {
      if (Array.isArray(arr[i])) {
        traverse(arr[i], flatList);
      } else {
        flatList.push(arr[i])
      }
    }
    return flatList;
  })(array, []);
}
@gauravmuk

This comment has been minimized.

Copy link

gauravmuk commented Feb 22, 2017

@thetutlage the solution with recursion is much faster when written in the right way :) https://jsperf.com/flatten-array-r1

@rofrol

This comment has been minimized.

Copy link

rofrol commented Jan 31, 2020

@gauravmuk your link is 404

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.