Public
Edited
Sep 12, 2023
1 star
ints2 = (randomise,Uint32Array.from({length:2**17.5},()=>((0+(Math.random()*Math.random()))*2**17.5)|0))
QuickSet = class QuickSet {
// NOTE THAT THIS IS A PROTOTYPING CLASS
// NOT ALL METHODS CORRESPOND WITH GITHUB
#view; #bits;
constructor({
mode = "minsum" || "winsum",
clip = 0 , span = 512 , // integer range min - max
slot = 0 , high = 128 , // frequency slots + range
freq = 1 , // minimum item cut frequency
fifo = false
} = {}) {
if (span > 2**28)
throw Error('Expected integers outside memory range');
if (high > (2**32)-1)
throw Error('Expected frequency outside memory range');
if (slot > 64)
throw Error('Rank slots performance degradation > 64');
if (span < slot) slot = span;
this.constructor.prototype.sum = fifo ? new Function('return function '
+this[mode].toString().replaceAll('#','').replace('val>this.tmin','val>=this.tmin')).call() : this[mode]
let [ Rank , mult ] = this.expects( span - 1 ), m = 2**(mult*8)-0;
let [ Pool , byte ] = this.expects( high - 1 ), b = 2**(byte*8)-1;
const data = new ArrayBuffer(byte*( span + 1 )); // range+1 to make inclusive //
this.constructor.prototype.default = { Rank, Pool, mode , mult, byte };
// this.view = new Float64Array(data);
this.rank = new Rank(slot);
this.stat = new Pool(slot);
this.#bits = new Pool(data); this.bits = this.#bits;
this.span = span = Math.min(span,m); // clip integers above range extent (inclusive)
this.clip = clip = Math.max(clip,0); // clip integers under range extent
this.high = high = Math.min(high,b); // skip integers more frequent than (exclusive)
this.freq = freq = Math.max(freq,0); // skip integers less frequent than
this.slot = slot; // ranked integer slots
this.last = slot - 1 ; // last item const
this.tmin = freq //?? 0; // keeps track of min in window
this.tmax = 0; // keeps track of max in window
this.prev = -1;
// WIP
this.insRate = 0;
this.upsRate = 0;
this.all = 0;
this.many = 0; // -> insertion rate feature
this.tops = 0; // -> insertion rate feature
this.temp = [];
}
invalid(input) {
input >>>= 1;
return (input ^ 0) !== input
}
minsum(uint, val = 1) {
let invalid = this.invalid
// range guard
if( uint < this.clip || uint > this.span || invalid(uint) || invalid(val)) return
var old = this.#bits[uint]; //let val = 1 + (this.#bits[uint]++) // => unweighted
val = old + val;
// count guard
if( val > this.high ) { return }
this.#bits[uint] = val;
// this.all++
let rank = this.rank , stat = this.stat;
if ( val>this.tmin && val > this.freq ) {
var slot = this.slot;
var last = this.last;
//let idx = rank.indexOf(uint); // -> slower
for (var idx = 0; idx < slot; ++idx) {
if(rank[idx] == uint) { break }
else if ( idx == last ) { idx = -1; break }
}
if (idx >= 0) {
// this.tops++
stat[idx] = val;
} else {
// this.many++
var low = this.tmin;
//var old = this.prev+1 // <-- FIFO = true
//var pos; // <-- FIFO = true
for (var ins = 0; ins < slot; ++ins) {
//if(stat[pos = (ins + old) % slot] <= low ) { this.prev = ins = pos ; break } // <-- FIFO = true
if(stat[ins] <= low ) { break } // <-- regular
}
rank[ins] = uint;
stat[ins] = val;
//if((this.tmin = lowest(stat)) < this.freq ) { this.tmin = this.freq } // => Math.max(lowest(stat),this.freq)
this.tmin = this.lowest(stat) // TO DO: autotuning in case freq settings == 0
}
if(val > this.tmax) this.tmax = val;
//this.insRate = this.many/this.all;
//this.upsRate = this.tops/this.all;
// this.temp.push([this.insRate,this.upsRate]);
}
//return this
}
locsum() {
// idea: update #bits location(s!) with position in rank array
// and switch back when uint leaves the ranking -> turned out slightly complex with little speedup
}
winsum(uint,val = 1) {
// range guard
if( !Number.isInteger(uint) || uint < this.clip || uint > this.span || !Number.isInteger(val)) return
var old = this.#bits[uint]; // val = 1 + (this.#bits[uint]++); // => unweighted
val = old + val;
// count guard
if( val > this.high ) { return }
this.#bits[uint] = val;
let rank = this.rank , stat = this.stat ;
if ( val>this.tmin && val > this.freq ) {
var slot = this.slot;
var idx, ins;
for (let i = 0; i < slot; ++i) {
if(idx >= 0 && ins >= 0 ) break
if(idx == undefined && rank[i] == uint) idx = i;
if(ins == undefined && stat[i] <= val) ins = i;
}
if(ins == undefined) return
if ( idx >= 0 ) {
if ( ins > idx ) return // TO DO: overwrite buffer when restarting count to prevent having to .fill(0)
rank.copyWithin(ins+1,ins,idx);
stat.copyWithin(ins+1,ins,idx);
rank[ins] = uint;
stat[ins] = val;
} else {
rank.copyWithin(ins+1,ins);
stat.copyWithin(ins+1,ins);
rank[ins] = uint;
stat[ins] = val;
this.tmin = stat[this.last] ?? 0 // min always last // Math.max(this.freq,stat[this.last])
// TO DO: autotuning in case freq settings == 0
}
this.tmax = stat[0] ?? 0 // max is always first
}
}
unique(...data) {
if (typeof data[0] == "object" && data[0].length) {
data = data[0]
}
let span = 8*Math.ceil(data.length * 0.125);
for (var i = 0; i < span -7; i = i + 8) {
this.add(data[i]);
this.add(data[i+1]);
this.add(data[i+2]);
this.add(data[i+3]);
this.add(data[i+4]);
this.add(data[i+5]);
this.add(data[i+6]);
this.add(data[i+7]);
}
return this
}
batch(...data) {
let vals, step;
if (
typeof data[0] == "object" && data[0].length &&
typeof data[1] == "object" && data[1].length && data[2] == undefined
) {
vals = data[1];
data = data[0];
step = vals.length;
} else if (typeof data[0] == "object" && data[0].length && data[1] == undefined) {
data = data[0];
}
let span = data.length;
if (vals) {
for (var i = 0; i < span; i = i + 1) {
let uint = data[i];
if (uint == undefined || uint < this.clip || uint > this.span) continue;
this.sum(uint, vals[i % step]);
}
} else {
for (var i = 0; i < span; i = i + 1) {
let uint = data[i];
if (uint == undefined || uint < this.clip || uint > this.span) continue;
this.sum(uint);
}
}
return this
}
clear(slot) {
this.#bits.fill(0);
if (slot === true) {
this.rank.fill(0);
this.stat.fill(0)
} else if (slot > 0) {
this.slot = Math.max(slot,64);
this.last = slot - 1;
this.rank = new this.default.Rank(slot);
this.stat = new this.default.Pool(slot);
}
this.tmin = this.freq;
this.tmax = 0;
}
resize(slot) {
if(slot > 0 && slot <= 64) {
let rank = new this.default.Rank(slot);
let stat = new this.default.Pool(slot);
let span = Math.min(this.slot,slot);
let prev = this.rank;
let last = this.stat;
for (let i = 0; i < span; ++i) {
rank[i] = prev;
stat[i] = last;
}
this.rank = rank;
this.stat = stat;
this.slot = slot;
} else {
throw new Error("Set window size between 0 an 64 inclusive.")
}
}
add(uint, val = 1) {
if ( uint < this.clip || uint > this.span || !Number.isInteger(uint) || !Number.isInteger(val)) return;
if ( val > this.high) return; // prevent overflow
this.bits[uint] = val;
}
get(uint) {
return this.#bits[uint]
}
has(uint) {
if (uint < this.clip || uint > this.span) return false
return !!this.#bits[uint]
}
put(uint, val = 1) {
// 'unsafe' add
if (uint < this.clip || uint > this.span) return //this
this.#bits[uint] = val
}
sum () {
// placeholder
}
keys(iter) {
let bits = this.#bits;
let span = iter ?? this.#bits.length;
let exit = new Uint32Array(this.span);
let last = 0;
for (let i = 0; i < span; ++i) {
let key = bits[i]
if (key) exit[last++] = i
}
return exit.subarray(0,last)
}
values(iter) {
let bits = this.#bits;
let span = iter ?? this.#bits.length;
let exit = new Uint16Array(this.span);
let last = 0;
for (let i = 0; i < span; ++i) {
let val = bits[i]
if (val) exit[last++] = val
}
return exit.subarray(0,last)
}
delete(uint) {
if (uint < this.clip || uint > this.span) return //this
this.#bits[uint] = 0
}
derank(uint) {
if (uint < this.clip || uint > this.span) return //this
this.#bits[uint] = 0;
this.tmin = 0;
let slot = this.slot;
let rank = this.rank;
let stat = this.stat;
for (var idx = -1; idx < slot; ++idx) {
if (rank[idx] == uint) {
rank[idx] = 0;
stat[idx] = 0;
break }
}
if(idx >= 0 && this.default.mode == 'winsum') {
let last = this.last;
rank.copyWithin(idx,idx+1);
stat.copyWithin(idx,idx+1);
rank[last] = 0;
stat[last] = 0;
this.tmin = stat[last-1];
}
}
lowest(arr,min = Infinity) {
let len = arr.length;
for (let i = 0; i < len; ++i) {
let val = arr[i]
if(val < min) min = val
}
return min
}
sorted(iter) {
let bits = this.#bits;
let span = iter ?? this.#bits.length;
let size = 0;
for (var i = 0; i < span; i = i+1) {
size = size + bits[i];
}
let sort = new this.default.Rank(size);
let last = 0;
for (var i = 0; i < span; i = i+1) {
let freq = bits[i];
if (freq===0) continue
for (let j = 0; j < freq; j = j+1) {
sort[last++] = i
}
}
return sort
}
entries(iter) {
let bits = this.#bits;
let span = iter ?? this.#bits.length;
let exit = new Array(this.span);
let last = 0;
for (let i = 0; i < span; ++i) {
let val = bits[i]
if (val > this.freq) exit[last++] = [i,val]
}
return exit.slice(0,last)
}
expects(int) {
switch(true) {
case int < (2** 8) : return [Uint8Array,1];
case int < (2**16) : return [Uint16Array,2];
case int < (2**32) : return [Uint32Array,4];
default : throw Error('Expected count out of range')
}
}
default() {
// placeholder
}
}
rewrite = (func, rgx, rep) => new Function('return function ' +func.toString().replace(rgx,rep)).call();
function getRightBit(n) {
return Math.log2(n & -n) + 1
}
function hash(x) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
return x;
}
QS = (await import('https://cdn.skypack.dev/@suptxt/quickset@0.4.6?min')).default
{
let t1 = performance.now()
let out = new QS({span:1, high:(2**32)-1,freq:0})
out.put(0,(2**32)-1)
out = out.entries()
return {
t: performance.now()-t1,
out
}
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
