Array shuffle comparator (on huge array)

JavaScript performance comparison

Revision 2 of this test case created by zaus

Preparation code

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

<!-- define all functions, etc -->
<script>
	// make the test array in the first place
	var hugeTestArray = [];
	for (var i = 0; i < 100000; i++) {
		hugeTestArray[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;
	}
</script>


<i>Look in the console for example output from methods, just to confirm they work.</i>
<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'];

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

		console.log('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); });

	}
</script>
    

Preparation code output

<!-- add a library --> <!-- define all functions, etc --> <i>Look in the console for example output from methods, just to confirm they work.</i>

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
hugeTestArray.mezclar();
pending…
marlanga as for-loop
mezclar2(hugeTestArray);
pending…
marlanga for-loop as prototype
hugeTestArray.mezclar3();
pending…
Native sort with callback
hugeTestArray.sort(function() { return 0.5 - Math.random() });
pending…
Generic Shuffle1
hugeTestArray.shuffle1();
pending…
Generic Shuffle 2
hugeTestArray.shuffle2();
pending…
Naive Shuffle
NaiveShuffle(hugeTestArray);
pending…
Knuth-Fisher-Yates as for
knuthfisheryates(hugeTestArray);
pending…
Knuth-Fisher-Yates as while
knuthfisheryates2(hugeTestArray);
pending…
underscore.js
_.shuffle(hugeTestArray);
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

Look in the console for example output from methods, just to confirm they work.