require('regenerator-runtime/runtime');
const {increasing} = require('@aureooms/js-compare');
const {issorted} = require("@aureooms/js-sort");
const {sorted} = require('@aureooms/js-itertools');
const array = require('@aureooms/js-array');
const totalOrder = require('total-order').default;
const isSameSet = (A,B) => totalOrder(sorted(increasing, A), sorted(increasing, B)) === 0;
const isSorted = (array) => issorted(increasing, array, 0, array.length) === array.length;
Radix sort
const {radixsort} = require("radixsort");
Quick sort
const {singletco, dualtco} = require('@aureooms/js-quicksort');
const {yaroslavskiy, hoare, lomuto} = require('@aureooms/js-partition');
const {shuffle} = require('@aureooms/js-random');
const quicksort_yaro = dualtco(yaroslavskiy);
const quicksort_hoar = singletco(hoare);
const quicksort_lomu = singletco(lomuto);
Merge sort
const {tapemerge} = require('@aureooms/js-merging');
const {recursive, iterative} = require('@aureooms/js-mergesort');
const mergesort_recu = recursive(tapemerge, array.copy);
const mergesort_iter = iterative(tapemerge, array.copy);
Allocation
const N = 1 << 16;
const randomFloat32 = () => {
const sign = Math.random() < .5 ? 1 : -1;
const base = (Math.random() - .5) * 100;
const exponent = (Math.random() - .5) * 100;
return sign * Math.exp(base, exponent) ;
};
const treference = new Float32Array(N);
array.fillfn(treference, 0, N, randomFloat32);
const reference = array.alloc(N);
array.copy(treference, 0, N, reference, 0);
delete treference;
Object.freeze(reference);
// Copy to normal array.
const a = array.alloc(N);
const ta = new Float32Array(N);
array.copy(reference, 0, N, a, 0);
array.copy(reference, 0, N, ta, 0);
Bench
const Benchmark = require('benchmark');
const suite = new Benchmark.Suite("Sorting benchmark");
const output = {};
const setup = function(){};
const setupQuicksort = function(){
let tmp;
};
//const setupMergesort = function(){
// let tmp1;
// const tmp2 = new Float32Array(N); // For some reason N is not defined
//};
suite
.add('NOP (slice)', function() {
output[this.name] = ta.slice();
}, {setup})
.add('NOP (slice + shuffle)', function() {
tmp = ta.slice();
shuffle(tmp, 0, tmp.length);
output[this.name] = tmp;
}, {setup: setupQuicksort})
.add('Array.prototype.sort', function() {
output[this.name] = a.slice().sort(increasing);
}, {setup})
.add('Float32Array.prototype.sort', function() {
output[this.name] = ta.slice().sort(increasing);
}, {setup})
.add('npm/radixsort', function() {
output[this.name] = radixsort(ta.slice());
}, {setup})
.add('npm/@aureooms/js-quicksort (hoare)', function() {
tmp = ta.slice();
shuffle(tmp, 0, tmp.length);
quicksort_hoar(increasing, tmp, 0, tmp.length);
output[this.name] = tmp;
}, {setup: setupQuicksort})
.add('npm/@aureooms/js-quicksort (lomuto)', function() {
tmp = ta.slice();
shuffle(tmp, 0, tmp.length);
quicksort_lomu(increasing, tmp, 0, tmp.length);
output[this.name] = tmp;
}, {setup: setupQuicksort})
.add('npm/@aureooms/js-quicksort (yaroslavskiy)', function() {
tmp = ta.slice();
shuffle(tmp, 0, tmp.length);
quicksort_yaro(increasing, tmp, 0, tmp.length);
output[this.name] = tmp;
}, {setup: setupQuicksort})
.add('npm/@aureooms/js-mergesort (recursive)', function() {
const tmp1 = ta.slice();
const tmp2 = new Float32Array(N);
mergesort_recu(increasing, tmp1, 0, tmp1.length, tmp2, 0, tmp2.length);
output[this.name] = tmp2;
}, {setup})
.add('npm/@aureooms/js-mergesort (iterative)', function() {
const tmp1 = ta.slice();
const tmp2 = new Float32Array(N);
mergesort_iter(increasing, tmp1, 0, tmp1.length, tmp2, 0, tmp2.length);
output[this.name] = tmp2;
}, {setup})
.on('cycle', function(event) {
console.log(String(event.target));
})
.on('complete', function() {
console.log('Fastest is ' + Benchmark.filter(this.filter(x => x.name.slice(0,3) !== 'NOP'), 'fastest').map(x => x.name));
})
// do not run async
.run({ 'async': false });
Correctness
const isCorrect = (title, output) => {
console.assert(isSorted(output), `The output of ${title} is not sorted.`);
console.assert(isSameSet(reference, output), `The output of ${title} does not contain the correct elements.`);
} ;
console.log(`Checking output of ${Object.keys(output).join(', ')}...`, Object.keys(output));
for (const [title, out] of Object.entries(output)) isCorrect(title, out);
no comments
sign in to comment