Skip to content

Instantly share code, notes, and snippets.

@gpakosz gpakosz/test.js Secret
Created Jul 18, 2017

Embed
What would you like to do?
Playing with Daniel's FastPriorityQueue
'use strict';
var QuickSelect = require('qselect');
var FastPriorityQueue = require('fastpriorityqueue');
var Benchmark = require('benchmark');
var os = require('os');
function FastPriorityQueueGP(maxSize, comparator) {
if (!(this instanceof FastPriorityQueueGP)) return new FastPriorityQueueGP(maxSize, comparator);
this.array = [];
this.size = 0;
this.maxSize = maxSize;
this.compare = comparator || defaultcomparator;
this.heapified = false;
}
FastPriorityQueueGP.prototype.add = function (myval) {
if (this.size < this.maxSize) {
var i = this.size;
this.array[this.size] = myval;
this.size += 1;
var p;
var ap;
while (i > 0) {
p = (i - 1) >> 1;
ap = this.array[p];
if (!this.compare(myval, ap)) {
break;
}
this.array[i] = ap;
i = p;
}
this.array[i] = myval;
}
else {
if (!this.compare(myval, this.array[0])) {
var ans = this.array[0];
this.array[0] = myval;
this._percolateDown(0 | 0);
return ans;
}
}
};
FastPriorityQueueGP.prototype.add2 = function (myval) {
if (this.size < this.maxSize) {
if (this.compare(myval, this.array[0])) {
this.array[this.size] = this.array[0];
this.array[0] = myval;
}
else
this.array[this.size] = myval;
this.size += 1;
if (this.size == this.maxSize)
this.heapify(this.array);
}
else {
if (!this.compare(myval, this.array[0])) {
var ans = this.array[0];
this.array[0] = myval;
this._percolateDown(0 | 0);
return ans;
}
}
};
FastPriorityQueueGP.prototype.replaceTop = function (myval) {
if (this.size == 0)
return undefined;
};
FastPriorityQueueGP.prototype.heapify = function (arr) {
this.array = arr;
this.size = arr.length;
var i;
for (i = (this.size >> 1); i >= 0; i--) {
this._percolateDown(i);
}
this.heapified = true;
};
FastPriorityQueueGP.prototype._percolateUp = function (i) {
var myval = this.array[i];
var p;
var ap;
while (i > 0) {
p = (i - 1) >> 1;
ap = this.array[p];
if (!this.compare(myval, ap)) {
break;
}
this.array[i] = ap;
i = p;
}
this.array[i] = myval;
};
FastPriorityQueueGP.prototype._percolateDown = function (i) {
var size = this.size;
var hsize = this.size >>> 1;
var ai = this.array[i];
var l;
var r;
var bestc;
while (i < hsize) {
l = (i << 1) + 1;
r = l + 1;
bestc = this.array[l];
if (r < size) {
if (this.compare(this.array[r], bestc)) {
l = r;
bestc = this.array[r];
}
}
if (!this.compare(bestc, ai)) {
break;
}
this.array[i] = bestc;
i = l;
}
this.array[i] = ai;
};
FastPriorityQueueGP.prototype.peek = function () {
if(this.size == 0) return undefined;
return this.array[0];
};
FastPriorityQueueGP.prototype.poll = function () {
if (this.size == 0)
return undefined;
var ans = this.array[0];
if (this.size > 1) {
this.array[0] = this.array[--this.size];
if (this.heapified)
this._percolateDown(0 | 0);
else
this.heapify(this.array);
} else {
this.size -= 1;
}
return ans;
};
FastPriorityQueueGP.prototype.trim = function () {
this.array = this.array.slice(0, this.size);
};
FastPriorityQueueGP.prototype.isEmpty = function () {
return this.size === 0;
};
// very fast semi-random function
function rand(i) {
i = i + 10000;
i = i ^ (i << 16);
i = (i >> 5) ^ i;
return i & 0xFF;
}
var defaultcomparator = function(a, b) {
return a < b;
};
var reverseddefaultcomparator = function(a, b) {
return a > b;
};
function compare(array1, array2) {
if (array1.length != array2.length) return false;
for (var i = 0; i < array1.length; i++) {
if (array1[i] != array2[i]) return false;
}
return true;
}
function check(streamsize, k) {
var expectedanswer = new Array();
for (var i = 0; i < streamsize; i++) {
expectedanswer.push(rand(i));
}
expectedanswer.sort(function(a, b) {
return a - b
})
expectedanswer = expectedanswer.slice(0, k);
{
var b = new FastPriorityQueue(reverseddefaultcomparator);
for (var i = 0; i < k; i++) {
b.add(rand(i));
}
for (i = k; i < streamsize; i++) {
var x = rand(i);
if (!reverseddefaultcomparator(x, b.peek())) {
b.replaceTop(x);
}
}
var answer = b.array.slice(0, k).sort(function(a, b) {
return a - b
});
if (!compare(answer, expectedanswer)) console.log("bug FastPriorityQueue-KWillets-replaceTop", answer, expectedanswer);
} {
var b = new FastPriorityQueueGP(k, reverseddefaultcomparator);
for (var i = 0; i < k; i++) {
b.add(rand(i));
}
for (i = k; i < streamsize; i++) {
b.add(rand(i));
}
var answer = b.array.slice(0, k).sort(function(a, b) {
return a - b
});
if (!compare(answer, expectedanswer)) console.log("bug FastPriorityQueueGP-add", answer, expectedanswer);
} {
var b = new FastPriorityQueueGP(k, reverseddefaultcomparator);
for (var i = 0; i < k; i++) {
b.add2(rand(i));
}
for (i = k; i < streamsize; i++) {
b.add2(rand(i));
}
var answer = b.array.slice(0, k).sort(function(a, b) {
return a - b
});
if (!compare(answer, expectedanswer)) console.log("bug FastPriorityQueueGP-add2", answer, expectedanswer);
} {
var a = new Array();
for (var i = 0; i < streamsize; i++) {
a.push(rand(i));
}
a.sort(function(a, b) {
return a - b
});
var answer = a.slice(0, k);
if (!compare(answer, expectedanswer)) console.log("bug sort");
}
}
function QueueEnqueueBench(streamsize, k) {
if (Math.floor(streamsize / k) * k != streamsize) {
console.log('bad streamsize ', streamsize, k);
return;
}
console.log('starting dynamic queue/enqueue benchmark');
var suite = new Benchmark.Suite();
// add tests
var ms = suite
.add('FastPriorityQueue-KWillets-replaceTop', function() {
var b = new FastPriorityQueue(reverseddefaultcomparator);
for (var i = 0; i < k; i++) {
b.add(rand(i));
}
for (i = k; i < streamsize; i++) {
var x = rand(i);
if (!reverseddefaultcomparator(x, b.peek())) {
b.replaceTop(x);
}
}
var answer = b.array.slice(0, k).sort(function(a, b) {
return a - b
});
return answer;
})
.add('FastPriorityQueueGP-add', function() {
var b = new FastPriorityQueueGP(k, reverseddefaultcomparator);
for (var i = 0; i < k; i++) {
b.add(rand(i));
}
for (i = k; i < streamsize; i++) {
b.add(rand(i));
}
var answer = b.array.slice(0, k).sort(function(a, b) {
return a - b
});
return answer;
})
.add('FastPriorityQueueGP-add2', function() {
var b = new FastPriorityQueueGP(k, reverseddefaultcomparator);
for (var i = 0; i < k; i++) {
b.add2(rand(i));
}
for (i = k; i < streamsize; i++) {
b.add2(rand(i));
}
var answer = b.array.slice(0, k).sort(function(a, b) {
return a - b
});
return answer;
})
.add('sort', function() {
var a = new Array();
for (var i = 0; i < streamsize; i++) {
a.push(rand(i));
}
a.sort(function(a, b) {
return a - b
});
var answer = a.slice(0, k);
return answer;
})
// add listeners
.on('cycle', function(event) {
console.log(String(event.target));
})
// run async
.run({
'async': false
});
}
var main = function() {
console.log('Platform: ' + process.platform + ' ' + os.release() + ' ' + process.arch);
console.log(os.cpus()[0]['model']);
console.log('Node version ' + process.versions.node + ', v8 version ' + process.versions.v8);
console.log();
console.log('');
check(1408 * 10, 128);
QueueEnqueueBench(1408 * 10, 128);
console.log('');
};
if (require.main === module) {
main();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.