Array shuffle comparator (on small array)

JavaScript performance comparison

Revision 5 of this test case created

Info

Comparing a bunch more shufflers than original revision. Performed on small (100) array.

Preparation code

<!-- add a library -->
<script src="http://underscorejs.org/underscore.js"></script>

<!-- define all functions, etc -->
<script>
        // make the test array in the first place
        var testArray = [];
        for (var i = 0; i < 100; i++) {
                testArray[i] = i;
        }


        // a generic shuffle function ("mezclar" is "to mix" in spanish?)
        Array.prototype.mezclar = function () {
                var n = this.length;
                while (n--) {
                        var i = Math.floor(n * Math.random());
                        var tmp = this[i];
                        this[i] = this[n];
                        this[n] = tmp;

                }
                return this;
        }

        // same thing, compressed loop into for declaration
        var mezclar2 = function (arr) {
                for (var i, tmp, n = arr.length; n; i = Math.floor(Math.random() * n), tmp = arr[--n], arr[n] = arr[i], arr[i] = tmp);
                return arr;
        }


        // same as mezclar2, only as prototype fn
        Array.prototype.mezclar3 = function () {
                for (var i, tmp, n = this.length; n--; i = Math.floor(Math.random() * n), tmp = this[i], this[i] = this[n], this[n] = tmp);
                return this;
        }

        // yet another generic implementation, from http://jsperf.com/shuffle-optimization-00129393
        Array.prototype.shuffle1 = function () {
                var l = this.length + 1;
                while (l--) {
                        var r = ~~(Math.random() * l),
                                o = this[r];

                        this[r] = this[0];
                        this[0] = o;
                }

                return this;
        }

        // again, another generic implementation that almost the same from http://jsperf.com/shuffle-optimization-00129393
        Array.prototype.shuffle2 = function () {
                var len = this.length;
                var i = len;
                while (i--) {
                        var p = parseInt(Math.random() * len);
                        var t = this[i];
                        this[i] = this[p];
                        this[p] = t;
                }

                return this;
        };

        // http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html
        function NaiveShuffle(arr) {
                var i, temp, j, len = arr.length;
                for (i = 0; i < len; i++) {
                        j = ~~(Math.random() * len);
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                }
                return arr;
        }

        // http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html
        function knuthfisheryates(arr) {
                var i, temp, j, len = arr.length;
                for (i = 0; i < len; i++) {
                        j = ~~(Math.random() * (i + 1));
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                }
                return arr;
        }

        // http://stackoverflow.com/a/2450976/1037948
        function knuthfisheryates2(arr) {
                var temp, j, i = arr.length;
                while (--i) {
                        j = ~~(Math.random() * (i + 1));
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                }

                return arr;
        }

        // same as above, moved +1 outside loop
        function knuthfisheryates2b(arr) {
                var temp, j, i = arr.length+1;
                while (--i) {
                        j = ~~(Math.random() * i);
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                }

                return arr;
        }
</script>


<i>Example output from methods.</i>
<div id="debug"></div>
<script>

        // and a smaller test for confirming that they're actually shuffling - see console

        if (/*console && console.log &&*/ JSON && JSON.stringify) {
                smallTestArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 'foo', 'bar', 'baz'];

                var $debug = document.getElementById('debug');
                function debugWrite() {
                        //console.log.apply(Array.prototype.slice.call(arguments, 0));
                        $debug.innerHTML += "\n\n<p>\n";
                        for (var a in arguments) {
                                if( arguments.hasOwnProperty(a) )
                                        $debug.innerHTML += arguments[a].toString() + "\n &nbsp; &nbsp; \n";
                        }
                        $debug.innerHTML += "</p>\n\n";
                }

                function debugTest(testname, arr, operation) {
                        debugWrite('-------');
                        //console.log('  arr before ', JSON.stringify(arr));
                        debugWrite(testname, ': results: ', JSON.stringify(operation(arr)));
                        // console.log('  arr after', arr);
                }

                debugWrite('Initial Array:', JSON.stringify(smallTestArray));

                debugTest('mezclar', smallTestArray, function (o) { return o.mezclar(); });
                debugTest('mezclar as for', smallTestArray, function (o) { return mezclar2(o); });
                debugTest('mezclar for as prototype', smallTestArray, function (o) { return o.mezclar3(); });
                debugTest('native', smallTestArray, function (o) { return o.sort(function () { return 0.5 - Math.random() }); });
                debugTest('generic1', smallTestArray, function (o) { return o.shuffle1(); });
                debugTest('generic2', smallTestArray, function (o) { return o.shuffle2(); });
                debugTest('naive', smallTestArray, function (o) { return NaiveShuffle(o); });
                debugTest('fisheryates1', smallTestArray, function (o) { return knuthfisheryates(o); });
                debugTest('fisheryates2', smallTestArray, function (o) { return knuthfisheryates2(o); });
                debugTest('underscore', smallTestArray, function (o) { return _.shuffle(o); });
                debugTest('fisheryates2b', smallTestArray, function (o) { return knuthfisheryates2b(o); });


        }
</script>

Preparation code output

Example output from methods.

Test runner

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

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
marlanga's version
testArray.mezclar();
pending…
marlanga as for-loop
mezclar2(testArray);
pending…
marlanga for-loop as prototype
testArray.mezclar3();
pending…
Native sort with callback
testArray.sort(function() {
  return 0.5 - Math.random()
});
pending…
Generic Shuffle1
testArray.shuffle1();
pending…
Generic Shuffle 2
testArray.shuffle2();
pending…
Naive Shuffle
NaiveShuffle(testArray);
pending…
Knuth-Fisher-Yates as for
knuthfisheryates(testArray);
pending…
Knuth-Fisher-Yates as while
knuthfisheryates2(testArray);
pending…
Knuth-Fisher-Yates as while, v2
knuthfisheryates2b(testArray);
pending…
underscore
_.shuffle(testArray)
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