Skip to content

Instantly share code, notes, and snippets.

@extemporalgenome
Created February 8, 2014 23:21
Show Gist options
  • Save extemporalgenome/8891892 to your computer and use it in GitHub Desktop.
Save extemporalgenome/8891892 to your computer and use it in GitHub Desktop.
Tested on:
Linux 3.12-1-amd64 #1 SMP Debian 3.12.9-1 (2014-02-01) x86_64 GNU/Linux
[Dual Core] Intel(R) Atom(TM) CPU N450 @ 1.66GHz
(below output manually aligned)
Array#sort x 100,884 ops/sec ±1.54% (87 runs sampled)
mout/array/sort x 28,408 ops/sec ±1.98% (89 runs sampled)
nativeStableSort x 30,591 ops/sec ±4.26% (81 runs sampled)
nativeInPlaceStableSort x 66,010 ops/sec ±2.15% (97 runs sampled)
// Requires node packages: benchmark and mout, and preferrably microtime
var Benchmark = require('benchmark');
var suite = new Benchmark.Suite;
var sort = require('mout/array/sort')
function defaultCompare(a, b) {
a = String(a);
b = String(b);
if(a < b)
return -1;
else if(a == b)
return 0;
else
return 1;
}
function lenCompare(a, b) {
a = a.length;
b = b.length;
if(a < b)
return -1;
else if(a == b)
return 0;
else
return 1;
}
function makeData() {
return ["sed", "dolor", "ipsum", "foo", "bar", "cat", "sit", "man", "lorem", "amet", "maecennas"];
}
function _stableCompare(cmp) {
cmp = cmp || defaultCompare;
return function(a, b) {
return cmp(a.v, b.v) || a.i-b.i;
}
}
function nativeStableSort(arr, compareFunction) {
return arr
.map(function(v, i) { return { i: i, v: v } })
.sort(_stableCompare(compareFunction))
.map(function(e) { return e.v });
}
function nativeInPlaceStableSort(arr, compareFunction) {
var i, n = arr.length;
for(i = 0; i < n; i++) {
arr[i] = {i: i, v: arr[i]};
}
arr.sort(_stableCompare(compareFunction));
for(i = 0; i < n; i++) {
arr[i] = arr[i].v;
}
return arr;
}
suite.add('Array#sort', function() {
makeData().sort(defaultCompare);
})
.add('mout/array/sort', function() {
sort(makeData(), defaultCompare);
})
.add('nativeStableSort', function() {
nativeStableSort(makeData(), defaultCompare);
})
.add('nativeInPlaceStableSort', function() {
nativeInPlaceStableSort(makeData(), defaultCompare);
})
.on('cycle', function(event) {
console.log(String(event.target));
})
.run({async: true});
/*
// These will all produce the same output
console.log(sort(makeData(), lenCompare));
console.log(nativeStableSort(makeData(), lenCompare));
console.log(nativeInPlaceStableSort(makeData(), lenCompare));
*/
@extemporalgenome
Copy link
Author

In this case, leveraging the native v8 sort (via nativeInPlaceStableSort) is more than 2x faster than the tested pure JavaScript intrinsically stable sort (mout/array/sort). If brevity is desired, nativeStableSort uses a compact functional style, and is slightly faster than mout's merge sort. The Schwartzian Transform is trivially applicable to both of the native*StableSort approaches as well.

Additionally, Array#splice can be used as a final step to give any copying sort the same semantics as an in-place sort.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment