Javascript split array into n subarrays, size of chunks don't matter

Viewed 308

I want to split an array into n subarrays. I don't care how many elements end up in each array but the elements must be spread through all the available sub arrays.

Like this, solutions A & B are two ways of doing it but I'm looking for Solution A:

a = [1,2,3,4,5,6,7,8,9]

into_subarrays(a, 2);

  • Solution A => [[1,3,5,7,9],[2,4,6,8]]
  • Solution B => [[1,2,3,4,5],[6,7,8,9]]

into_subarrays(a, 4);

  • Solution A => [[1,5,9],[2,6],[3,7],[4,8]]
  • Solution B => [[1,2,3],[4,5],[6,7],[8,9]]

into_subarrays(a, 6);

  • Solution A => [[1,7],[2,8],[3,9],[4],[5],[6]]
  • Solution B => [[1,2],[3,4],[5,6],[7],[8],[9]]

into_subarrays(a, 12);

  • Solution A => [[1],[2],[3],[4],[5],[6],[7],[8],[9],[],[],[]]
  • Solution B => [[1],[2],[3],[4],[5],[6],[7],[8],[9],[],[],[]]

I have this solution, I just want to make sure it's as efficient as possible:

into_subarrays(myArray, chunks=2){
  var a = myArray.slice(); //Copy array so that the original is not modified
  var i = 0;
  var result = [];
          
  while(a.length){
   //Create array if needed
   if (typeof result[i] == 'undefined'){
     result[i] = [];
   }

   result[i].push(a.shift());
   i++;
   i = (i == chunks) ? 0 : i; //Wrap around chunk selector
  }

  return result;
}

Thanks.

4 Answers

I may suggest something that is much more compact and works 20% faster:

const src = [...'abcdefghijklmn'],

      chunkArr = (arr, qty) =>
        arr.reduce((r,e,i) => 
          (r[i%qty].push(e),r), 
          [...Array(qty)].map(_ => []))
        
console.log(chunkArr(src, 4))
.as-console-wrapper{min-height:100%;}

There are a few things to note about your current approach.

  1. I personally wouldn't use if (typeof result[i] == 'undefined'). Instead you could omit the typeof and do if (result[i] === undefined). However since you know the value is either an array or not present at all the check if (!result[i]) would be enough.

  2. The lines i++ and i = (i == chunks) ? 0 : i could be combined if you use the remainder operator %. Resulting in i = (i + 1) % chunks.

  3. You solution only adds an empty array when it needs a new one. This will lead to an invalid result when you try to execute into_subarrays(a, 12) with your current solution. It is probably better to create the correct amount of arrays up front with something like Array.from({length: chunks}, () => []). This will also remove the need for the if-statement.

Applying the above the result would look something like:

function into_subarrays(array, chunks = 2) {
  array = array.slice(); // Copy array so that the original is not modified
  const result = Array.from({length: chunks}, () => []);

  for (let i = 0; array.length; i = (i + 1) % chunks) {
    result[i].push(array.shift());
  }

  return result;
}

const array = [1,2,3,4,5,6,7,8,9];
console.log(into_subarrays(array, 4));
console.log(into_subarrays(array, 12));

You could omit the slice if you didn't shift the elements out of the array.

function into_subarrays(array, chunks = 2) {
  const result = Array.from({length: chunks}, () => []);

  for (let i = 0; i < array.length; ++i) {
    const chunk = result[i % chunks];
    chunk.push(array[i]);
  }

  return result;
}

const array = [1,2,3,4,5,6,7,8,9];
console.log(into_subarrays(array, 4));
console.log(into_subarrays(array, 12));

I would like to point out that there is also an opportunity here to use a generator function to cycle through the resulting arrays.

function* cycle(iterable) {
  while (true) yield* iterable;
}

function into_subarrays(array, chunks = 2) {
  const result = Array.from({length: chunks}, () => []);
  const cycler = cycle(result);
  
  for (const item of array) {
    const chunk = cycler.next().value;
    chunk.push(item);
  }

  return result;
}

const array = [1,2,3,4,5,6,7,8,9];
console.log(into_subarrays(array, 4));
console.log(into_subarrays(array, 12));

Most of the micro-benchmark differences will come down to these optimizations:
https://v8.dev/blog/elements-kinds

Your question requires more context to be relevant. Depends on things like engine/environment specific optimizations, chunk size, data set size, and type of data (for taking advantage of packed optimizations). Performance characteristics can vary, and it becomes a matter of opinion rather than fact as it just becomes conjecture, when the real world case is probably that more likely than not it isn't anywhere near being your bottleneck.
eg: In React, immutability giving performance advantages for users of the library, but the React developers make use of the above linked optimizations internally.
Even withstanding all that, the relevance of the performance is debatable, and should be measured with real world data. It's not likely these optimizations will apply to you.

For example, the generator approach not having to iterate over the entire list and build the whole list may be significantly more performant for the case that it does not have to iterate over the entire array and store everything in memory. In a microbench where it's being run many times and the challenge is to build the entire list with a homogeneous array with native level optimizations for access, it just ends up adding overhead.

A few takeaways on performance of the other answers and your demo code so far:

  • Array.from is slow (relatively on V8(Chrome))
  • using shift(+push) is very slow
  • accessing indexes of arrays outside their actual length breaks the fast path
  • generators defer performance, and in microbench for OP's given problem only adds overhead to array access
  • for small arrays almost no difference is seen. It's almost all just object initialization
  • larger chunks also closes the gap

Benchmark here: https://jsben.ch/JrtTv benchmark

NOTE: tweaking array size and chunk size will change the results drastically

For loop implementation will outperform all the other answers due to avoidance of overhead, object initialization, and packed optimizations. Also controlled memory usage:

array = [1,2,3,4,5,6,7,8,9]
const chunk = (a, n) => {
  const res = []
  for(let i = 0; i < n; i++) {
    const r = []
    res.push(r)
    for(let j = 0; j < (a.length/n|0)+(i<a.length%n); j++)
      r.push(a[j*n+i])
  }
  return res
}
console.log(chunk(array, 4));
console.log(chunk(array, 12));

a bit faster (but slower than for-loop) because of pre-allocation (and ensures array indexing optimizations):

a = [1,2,3,4,5,6,7,8,9]

const chunk = (a, n) =>
  Array(n).fill().map((_,i)=>
    Array((a.length/n|0)+(i<a.length%n)).fill().map((_,j)=>a[j*n+i]))
    
    
console.log(chunk(a,4))
console.log(chunk(a,12))

into_subarrays(myArray, chunks=2){
  var a = myArray.slice(); //Copy array so that the original is not modified
  var i = 0;
  var result = [];
          
  while(a.length){
   //Create array if needed
   if (typeof result[i] == 'undefined'){
     result[i] = [];
   }

   result[i].push(a.shift());
   i++;
   i = (i == chunks) ? 0 : i; //Wrap around chunk selector
  }

  return result;
}
Related