14
\$\begingroup\$

I had a situation when I needed to move all array elements in circular fashion. When I say this, I mean:

0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2

The array:

var players = ["hash1","hash2","hash3","hash4"];
  • Players is the array that contains user hashes and their place on the table. Table is round, so array must rotate in circular fashion.
  • Step dictates by how much it should move.

I came up with following algorithm (if you can call that, probably not) that works fine. I was just wondering if there was a more efficient way. Or cleaner way to do same?

The offset variable is probably wrongly named; I couldn't come up with a better name.

var step = 0 // 3,2,1,0
    var offset = 0;
    var players_new = [];
    for (var i = 0; i <= players.length - 1; i++) {
        if (i + step <= players.length - 1) {
            players_new[i + step] = players[i];
            offset++;
        } else {
            players_new[i - offset] = players[i];
        }
    };

I tested many different versions, and looks like vazha's version is the fastest all around, except in Firefox.

jsperf

Since I'm using this code in node.js, which uses the Chrome engine, results are important.

\$\endgroup\$

migrated from stackoverflow.com Feb 5 '14 at 21:37

This question came from our site for professional and enthusiast programmers.

  • 2
    \$\begingroup\$ Why not leave the data as-is and use %? \$\endgroup\$ – Matt Ball Feb 5 '14 at 21:38
  • \$\begingroup\$ @MattBall Can you illustrate? I'm not following. \$\endgroup\$ – user36275 Feb 5 '14 at 21:40
  • \$\begingroup\$ If you haven't already see stackoverflow.com/questions/1985260/javascript-array-rotate \$\endgroup\$ – megawac Feb 5 '14 at 22:37
  • 1
    \$\begingroup\$ Yea it seems like shift() is the performance killer and reading the specs, shift is a generic method that reads properties of the array to determine how to shift it. So in a all rounder way shift is easy but your solution only works for your use case. It is impressive performance increase in your case :) I hope your Array contains millions of players :) \$\endgroup\$ – Piotr Kula Feb 6 '14 at 9:25
  • \$\begingroup\$ @ppumkin yep, shift is the culprit. thanks for the heads up :) \$\endgroup\$ – user36275 Feb 6 '14 at 9:34
11
\$\begingroup\$

You should use shift and push

function rotate( array , times ){
  while( times-- ){
    var temp = array.shift();
    array.push( temp )
  }
}

//Test
var players = ['Bob','John','Mack','Malachi'];
rotate( players ,2 )
console.log( players );

shift removes the first element, push adds an element at the end. I am not sure whether you are using players_new because you do not know how to modify the original array or because you do not want to modify the original. If you do not want to modify the original array you could:

function rotate( array , times ){
  array = array.slice();
  while( times-- ){
    var temp = array.shift();
    array.push( temp )
  }
  return array;
}

//Test
var players = ['Bob','John','Mack','Malachi'];
console.log( rotate( players ,2 ) );

Finally, if you meant to declare an array, you should have var players_new = [];, not var players_new = {};. Plus players_new is an unfortunate name.

Golfic edition:

while(times--)array.push(array.shift());
\$\endgroup\$
  • \$\begingroup\$ I need to read more about built in capabilities of javascript :) \$\endgroup\$ – user36275 Feb 5 '14 at 21:44
  • \$\begingroup\$ what would you call players_new? p.s. I need original array too. \$\endgroup\$ – user36275 Feb 5 '14 at 21:51
  • \$\begingroup\$ Probably I would use seatings and newSeatings ? \$\endgroup\$ – konijn Feb 5 '14 at 21:59
  • \$\begingroup\$ Thanks. Btw, my version is much faster than shift and push you proposed. \$\endgroup\$ – user36275 Feb 5 '14 at 22:03
  • \$\begingroup\$ Take a look, maybe I'm doing something wrong. But your proposed solution is 63% slower. jsperf.com/rotate-array \$\endgroup\$ – user36275 Feb 5 '14 at 22:05
4
\$\begingroup\$

Sometimes it is a good idea to abstract this sort of problem. In many languages doing array-based shifts is very expensive.

Do you need to rotate the array? Why not just virtually 'rotate' your pointer....

for (int turn = 0; turn < 10; turn++) {

    console.log("First player is " + players[(turn + 0) % players.length]);
    console.log("Last player is " + players[(turn + players.length - 1) % players.length]);

}

Alternatively, if you need to create the full array for other reasons, consider the slice and concat:

for (turn = 0; turn < 10; turn++) {
    var offset = turn % players.length;
    console.log(offset);
    var playturn = players.slice(offset).concat(players.slice(0, offset));
    console.log(playturn.join(", "));

}
\$\endgroup\$
  • \$\begingroup\$ I like your 2nd suggestion is smart, +1 \$\endgroup\$ – konijn Feb 5 '14 at 23:19
  • \$\begingroup\$ @konijn Well smart, but 80% slower than my solution. \$\endgroup\$ – user36275 Feb 6 '14 at 8:45
  • \$\begingroup\$ jsperf.com/rotate-array/3 \$\endgroup\$ – user36275 Feb 6 '14 at 8:46
  • \$\begingroup\$ @salivan I am surprised it is that much slower, but it is my plan-B suggestion. Plan-A is to use the modulo on the index to just 'logically' rotate the array. It requires a different type of support-code outside the function \$\endgroup\$ – rolfl Feb 6 '14 at 11:19
  • \$\begingroup\$ looks like we have a winner: jsperf.com/rotate-array-javascript \$\endgroup\$ – user36275 Feb 6 '14 at 14:05

Your Answer

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