Search trees, van Emde Boas layout

by ntoshev

HTML

<script src="https://github.com/bestiejs/benchmark.js/raw/master/benchmark.js"></script>
<div id='log'/>

JavaScript

'use strict';
var logs=document.getElementById('log');
console.log= function(s){
var e=document.createElement('pre');
    e.innerHTML=s;
    logs.insertBefore(e);
}


function Tree(v, l, r){
    this.el=v;
    this.l=l;
    this.r=r;
}

function find(t, v){
    if (v==t.el) {
        return t;
    } else if (v<t.el) {
        return (t.l)?find(t.l, v):t;
    } else {
        return (t.r)?find(t.r, v):t;
    }
}

function GenerateRecTree(lo, hi, levels) {
    if (levels==0) return null;
    var mid = (hi+lo)/2;
    var ret =new Tree(mid, 
        GenerateDFTree(lo, mid, levels-1), 
        GenerateDFTree(mid, hi, levels-1));
    //console.log(mid);
    return ret;
}

var preallocated = Array(4*66536);
for (var i=0; i<preallocated.length; i++){
    preallocated[i]=new Tree(1.1, null, null);
}

function heapAlloc(){
    return new Tree(0, null, null);
}
function arrayAlloc(){ 
    return preallocated.shift();
}

function GenerateVEBTree(lo, hi, levels, allocator) {
}

console.log(JSON.stringify(GenerateDFTree(0, 256, 8))==
    JSON.stringify(GenerateVEBTree(0, 256, 8, heapAlloc)));

var RT = GenerateRecTree(0, 65536, 16);
var VEB1 = GenerateVEBTree(0, 65536, 16, heapAlloc);
var VEB2 = GenerateVEBTree(0, 65536, 16, arrayAlloc);
//these are exactly the same trees, just laid out in memory differently


function assert(b){
    if (!b) throw "Error in assertion";
}

assert(JSON.stringify(RT)==JSON.stringify(VEB1)); 
assert(JSON.stringify(RT)==JSON.stringify(VEB2));
assert(JSON.stringify(VEB1)==JSON.stringify(VEB2));

var suite = new Benchmark.Suite;
suite.add('depth first', function() {
    var num = Math.floor(Math.random()*65536)
    assert(find(RT, num)==num);
}).add('depth first, limited to 1/4 of the elements', function() {
    var num = Math.floor(Math.random()*16000)
    assert(find(RT, num)==num);
}).add('veb1', function() {
    var num = Math.floor(Math.random()*65536)
    assert(find(VEB1, num)==num);
}).add('veb2', function() {
    var num =...