7
\$\begingroup\$

NOTE: This post was moved from stackoverflow as codereview.stackexchange is a better place to discuss the performance of this code problem/solution.

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.

e.g: 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.

\$\endgroup\$
  • \$\begingroup\$ Dont slice and shift, just read the right index. The shift is your greatest performance killer. \$\endgroup\$ – slepic Jul 12 at 4:13
5
\$\begingroup\$

First: Since you already know how many chunks you want, there's no point in checking if the chunk exists and otherwise declare it. In general terms, you should not need to check for objects you can define deterministically.

So instead of doing this check on each loop:

if (typeof result[i] == 'undefined'){
  result[i] = [];
}

create an array of N empty arrays beforehand.

const result = Array.from(Array(chunks),item=>[]);

Second: Albeit the performance difference is negligible, checking for i's value and conditionally reassigning it is less efficient than using the modulo operator on its value regardless

So instead of

results[i].push(...)
i++
i = (i == chunks) ? 0 : i;

You can do

results[i % chunks].push(...)
i++

With the above, your function could be expressed as

function usingShift(myArray, chunks=5){
  const copiedArray = myArray.slice(),
        result=Array.from(Array(chunks),item=>[]);
  let i=0;
  while(copiedArray.length){
    result[i % chunks].push(copiedArray.shift());
    i++;
  }
  return result;
}

Third: As you've been told, shifting from an array is expensive. I understand you're doing it because you want to populate the chunks in the same order of the original array. However you can achieve the same popping from the a reversed array:

If you declare

const a = myArray.slice().reverse();

You can replace the usage of shift with

result[i].push(a.pop());

The function would be something like:

function usingPop(myArray, chunks=5){
  const reversedArr = myArray.slice().reverse(),
        result=Array.from(Array(chunks),item=>[]);
  let i=0;
  while(reversedArr.length){
    result[i % chunks].push(reversedArr.pop());
    i++;
  }
  return result;
}

However... you'd still be copying the array and performing a mutation on the copy. @Miklós Mátyás solution has the advantage of populating the result without copying nor extracting items from the source array. Now, you haven't said the source array will be always the same (9 elements from 1 to 9). It could as well have repeated/unsorted items, so his solution should take into account not the item itself but its index, which can be expressed as:

function filterByModulo(myArray, chunks=5){
  return Array.from(Array(chunks),(_,modulo)=>{
    return myArray.filter((item,index) =>  index % chunks === modulo);
  });
}

That's pretty clean, but it's filtering on the original array as many times as chunks you want, so it's performance degrades according to the source array length AND the chunk quantity.

Personally I believe this is a case in which reduce would be more appropiate and pretty concise, while avoiding the copying or mutation of the source array.

function usingReduce(myArray,chunks=5) {
   const result=Array.from(Array(chunks),i=>[]);

   return myArray.reduce( (accum,item,index)=>{ 
      accum[index%chunks].push(item);
      return accum;
   }, result);
}

Finally there's the classic for loop

function classicFor(sourceArr, chunks=5) {
  const lengthOfArray=sourceArr.length;
  const result=Array.from(Array(chunks),i=>[]);
   
  for(let index=0; index<lengthOfArray ; index++) {
     result[index % chunks ].push(sourceArr[index]);
  }
  return result;
}

I made a test case at JSPerf in which it shows that the for loop is the most efficient. (I threw in forEach and for..of implementations too).

Running with a source array of 5000 items and 5 chunks shows that using pop on the source is more efficient than using shift by a 2.89x factor. It even looks more efficient that reduce. The classic for loop is the fastest whereas filtering N times comes up last by a ratio of 9x the modulo filtering.

If you use a source of 100000 items and 15 chunks the classic for is still the most efficient (still 9x modulo filtering) but the other implementations do scale a bit better than modulo filtering.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

I am not sure I can give you a breakdown of your code as to why and how I would do things differently, but here are my two cents.

  • The very first thing I would say is try to use const and let instead of var, it's the more modern syntax.
  • Also as @slepic mentioned it, shift is a very costly operation. It has to create a new array and therefore it's O(n), while push just adds one to the and and it's O(1) on some cases and O(n) on other log(n) cases.
  • The last thing is that whenever I see while loops, for loops, i++ and stuff like that with array operations, I get the feeling in the back of my head that there has to be a way to write this with array operations like map, filter, reduce etc. The reason why I say this is that a lot of work has gone into these array operations to be as performance optimal as possible, and you just can't compete with them with your own loops.

So I came up with a solution to the problem, it's my first try, feel free to improve on it!

The thoughtprocess behind it is the following: You have the number of chunks you want at the end, so first create an array that long and later map each element to a subarray of the original array. Now the question is what is the rule to create the subarrays. From your post I see that every subarray has the same modulo with regards to the number of chunks needed.

into_subarrays(myArray, chunks=2){
  // Create the array that is as long as the number of chunks needed, and starts with 1
  if(chunks === 1) return myArray;
  const result = Array.from(Array(chunks), (_, i) => i + 1);
  result.map(modulo => {
     // Map each element of the array to a subarray of the original array
     return myArray.filter(aElement => {
                      // The subarray can only contain the elements of the original array
                      // that have the same modulo 
                      // the reason I used a ternary operator here is that the last 
                      // element of the array would otherwise be empty. This part probably
                      // can be improved on.
                      return modulo === aElement ? 
                                        true : 
                                        aElement % lengthOfArray === modulo
                         })
                   })
  return result;
}

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Push is not always O(1) actually. It Is O(1) on average and O(n) when the internal memory needs to be reallocated, which happens in log(n) cases. Although this is not by standard, most implementations behave that way. \$\endgroup\$ – slepic Jul 12 at 7:53
  • \$\begingroup\$ did not know that, thanks! \$\endgroup\$ – Miklós Mátyás Jul 12 at 8:08
  • \$\begingroup\$ As a follow-up on slepic's comment, what you're looking for is the term amortized \$\mathcal O(1)\$. However, it depends on the actual implementation. \$\endgroup\$ – Zeta Jul 12 at 8:45
  • \$\begingroup\$ Btw I had to take a paper and do the maths to figure out that pushing n items to array that keeps doubling its internal memory when filled, is still O(n). Although where creating and filling an array of known size in advance is a*n, pushing n items to a "doubling array" is more like (a+b)*n-a*log(n). So although big O will stay the same it might gain some miliseconds if push was avoided as well, especialy when dividing a big array into only a few subarrays. And im pretty sure that the size of all the subarrays can be computed in advance. \$\endgroup\$ – slepic Jul 12 at 17:11
1
\$\begingroup\$

If you want to make the code "as efficient as possible" then avoid additional function calls - that includes iterator methods like Array.map(), Array.forEach(), etc., and while it would allow the code to be written in a more readable way, the ES6 for...of loop would also be affect efficiency because it calls an iterator function for each element in the array.

I suggest using a basic for loop after creating an array of arrays (for each chunk). As others have mentioned, modulo division can be used to determine which sub-array to put each element into.

function into_subarrays(myArray, chunks=2){
  const result = Array(chunks);
  for (let i = chunks; i--; ) {
    result[i] = [];  //initialize sub-arrays
  }
          
  for(let i = 0, length = myArray.length; i < length; i++) {
    result[i%chunks].push(myArray[i]);
  }
  return result;
}
const a = [1,2,3,4,5,6,7,8,9];
console.log(into_subarrays(a, 2));

Notice the first loop to set the arrays of result iterates from chunks down to zero - this minimizes the number of operations in the for loop conditions. This wouldn't work for the second loop because the order of i values is important.

I see the function has a default parameter value for chunks - this is an ES6 feature. While not specifically ES6 features, the let and const keywords can be used to declare variables scoped to the blocks they are contained in.

In the existing code there are theres lines towards the end of the while block:

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

selector

Whenever I see a pre/post increment operator on a single line I look to see if it could be combined with another operation - e.g.

  result[i++].push(a.shift());

or

i = (++i == chunks) ? 0 : i; //Wrap around chunk 

Also, prefer using === over == to avoid unnecessary type coercion.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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