Array shuffle comparator (on small array)

JavaScript performance comparison

Revision 9 of this test case created by

Preparation code

<!-- add a library -->
src="http://cdnjs.cloudflare.com/ajax/libs/lodash.js/2.4.1/lodash.min.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('lo-dash', smallTestArray, function (o) { return _.shuffle(o); });
		debugTest('fisheryates2b', smallTestArray, function (o) { return knuthfisheryates2b(o); });


	}
</script>
    

Preparation code output

<!-- add a library --> src="http://cdnjs.cloudflare.com/ajax/libs/lodash.js/2.4.1/lodash.min.js"></script> <!-- define all functions, etc --> <i>Example output from methods.</i> <div id="debug"></div>

Test runner

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

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
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…
lodash
_.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.

0 Comments

src="http://cdnjs.cloudflare.com/ajax/libs/lodash.js/2.4.1/lodash.min.js"> Example output from methods.