Fisher-Yates shuffle

JavaScript performance comparison

Revision 12 of this test case created

Info

Compare two variations of a Fisher-Yates shuffle

add optimization using binary or operator instead of Math.Floor

http://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array-in-javascript#http://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array-in-javascript#6274398

check if actual Knuth shuffle: http://bost.ocks.org/mike/shuffle/compare.html

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    var orderedlist = ["000", "001", "003", "004", "005", "006", "007", "008", "009", "010", "011", "012", "013", "014", "015", "016", "017", "018", "019", "020", "021", "022", "023", "024", "025", "026", "027", "028", "029", "030", "031", "032", "033", "034", "035", "036", "037", "038", "039", "040", "041", "042", "043", "044", "045", "046", "047", "048", "049", "050", "051", "052", "053", "054", "055", "056", "057", "058", "059", "060", "061", "062", "063", "064", "065", "066", "067", "002", "068", "069", "070", "071", "072", "073", "074", "075", "076", "077", "078", "079", "080", "081", "082", "083", "084", "085", "086", "087", "088", "089", "090", "091", "092", "093", "094", "095", "096", "097", "098", "099"];
   
   
    // Fisher-Yates shuffles
   
    function shuffle1(array) {
      var i = array.length,
          j, t;
      while (--i > 0) {
        j = ~~ (Math.random() * (i + 1));
        t = array[j];
        array[j] = array[i];
        array[i] = t;
      }
      return array;
    }
   
   
   
    function shuffle2(array) {
      var tmp, current, top = array.length;
      if (top) while (--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
      }
      return array;
    }
   
    function shuffle2BinOr(array) {
      var tmp, current, top = array.length;
      if (top) while (--top) {
        current = (Math.random() * (top + 1)) | 0;
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
      }
      return array;
    }
   
    function shuffle3(array) {
      var tmp, current, top = array.length;
      if (top) while (top) {
        current = Math.floor(Math.random() * (top--));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
      }
      return array;
    }
   
    function shuffle3BinOr(array) {
      var tmp, current, top = array.length;
      if (top) while (top) {
        current = (Math.random() * (top--)) | 0;
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
      }
      return array;
    }
   
    function shuffle5(arr) {
      var i, j, _ref;
      i = arr.length;
      if (i === 0) {
        return false;
      }
      while (--i) {
        j = Math.floor(Math.random() * (i + 1));
        _ref = [arr[j], arr[i]], arr[i] = _ref[0], arr[j] = _ref[1];
      }
      return arr;
    };
   
    function shuffle6(a) {
      var i, j, _i, _ref, _ref1;
      for (i = _i = _ref = a.length - 1; _ref <= 1 ? _i <= 1 : _i >= 1; i = _ref <= 1 ? ++_i : --_i) {
        j = Math.floor(Math.random() * (i + 1));
        _ref1 = [a[j], a[i]], a[i] = _ref1[0], a[j] = _ref1[1];
      }
      return a;
    };
   
    function shuffle7(array) {
      var m = array.length, t, i;
      while (m) {
        i = Math.floor(Math.random() * m--);
        t = array[m];
        array[m] = array[i];
        array[i] = t;
      }
    };
   
    function shuffle8(array) {
      var random = array.map(Math.random);
      array.sort(function(a, b) {
        return random[a] - random[b];
      });
    };
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Fisher-Yates Shuffle1
shuffle1(orderedlist);
pending…
Fisher-Yates Shuffle2
shuffle2(orderedlist);
pending…
Fisher-Yates Shuffle3
shuffle3(orderedlist);
pending…
Fisher-Yates Shuffle5
shuffle5(orderedlist);
pending…
Fisher-Yates Shuffle3 - Binary OR
shuffle3BinOr(orderedlist);
pending…
Fisher-Yates Shuffle2 - Binary OR
shuffle2BinOr(orderedlist);
pending…
Fisher-Yates Shuffle7
shuffle7(orderedlist);
pending…
double random
shuffle8(orderedlist);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment