Benchmark: HashBounds - MeasureThat.net

Script Preparation code:


function Grid(g, p, size,minc) {
    this.MIN = minc * -1;
    this.POWER = g;
    this.LEVEL = p;
    this.SIZE = size;
    this.DATA = {};
    this.LENGTH = 0;
    this.init()
}
Grid.prototype.init = function () {
    if (this.SIZE >= 65535) {
        throw "Maximum amount of buckets are 65535^2"
    } // Max limit is 65535 (16 bits) 
    // console.log(this.SIZE)
    for (var j = this.MIN; j <= this.SIZE; ++j) {
        var x = j << 16
        for (var i = this.MIN; i <= this.SIZE; ++i) {

            var key = this._getKey(x, i);
            // console.log(key)
            this.DATA[key] = new Map()

        }
    }

}
Grid.prototype._every = function (m, c) {
    var a = m.entries()
    var b;
    while (b = a.next().value) {
        if (!c(b[1], b[0])) return false;
    }
    return true;
}

Grid.prototype.getKey = function (x, y) {
    return {
        x: x >> this.POWER,
        y: y >> this.POWER
    }
}
Grid.prototype._getKey = function (x, y) {
    return x | y

}
Grid.prototype.checkBorders = function (x, y) {
    return !(x > this.SIZE || y > this.SIZE)

}
Grid.prototype.insert = function (node) {

    //   var a = this.getKey(node.bounds.width, node.bounds.height);
    // if (a.x + a.y >= 2 && this.LEVEL != 0) return false;
    this.LENGTH++;
    var x1 = node.bounds.x,
        y1 = node.bounds.y,
        x2 = node.bounds.x + node.bounds.width,
        y2 = node.bounds.y + node.bounds.height;

    var k1 = this.getKey(x1, y1)
    var k2 = this.getKey(x2, y2)
    node.hash.k1 = k1
    node.hash.k2 = k2
    node.hash.level = this.LEVEL
    var lenX = k2.x + 1,
        lenY = k2.y + 1;
    for (var j = k1.x; j < lenX; ++j) {
        var x = j << 16;
        for (var i = k1.y; i < lenY; ++i) {

            var ke = this._getKey(x, i);
            // console.log(ke)
            this.DATA[ke].set(node._HashID, node)
        }

    }
    return true;
}
Grid.prototype.delete = function (node) {
    var k1 = node.hash.k1
    var k2 = node.hash.k2
    this.LENGTH--;
    var lenX = k2.x + 1,
        lenY = k2.y + 1;
    for (var j = k1.x; j < lenX; ++j) {
        var x = j << 16;
        for (var i = k1.y; i < lenY; ++i) {


            var ke = this._getKey(x, i);

            this.DATA[ke].delete(node._HashID)
        }

    }
}
Grid.prototype.toArray = function (array, bounds) {
    if (this.LENGTH <= 0) return;

    var x1 = bounds.x,
        y1 = bounds.y,
        x2 = bounds.x + bounds.width,
        y2 = bounds.y + bounds.height,
        h = {};

    var k1 = this.getKey(x1, y1)
    var k2 = this.getKey(x2, y2)
    for (var j = k1.x; j <= k2.x; ++j) {
        var x = j << 16;
        for (var i = k1.y; i <= k2.y; ++i) {

            var ke = this._getKey(x, i);

            if (this.DATA[ke]) this.DATA[ke].forEach((node, i) => {

                if (h[i]) return;
                h[i] = true;
                array.push(node)
            })
        }

    }
}
Grid.prototype.every = function (bounds, call) {
    if (this.LENGTH <= 0) return true;
    var x1 = bounds.x,
        y1 = bounds.y,
        x2 = bounds.x + bounds.width,
        y2 = bounds.y + bounds.height,
        h = {};

    var k1 = this.getKey(x1, y1)
    var k2 = this.getKey(x2, y2)
    for (var j = k1.x; j <= k2.x; ++j) {
        var x = j << 16;
        for (var i = k1.y; i <= k2.y; ++i) {

            var ke = this._getKey(x, i);

            if (this.DATA[ke])
                if (!this._every(this.DATA[ke], (a, b) => {

                        if (h[b]) return true;
                        h[b] = true;
                        return call(a, b);
                    })) return false;
        }

    }
    return true;
}
Grid.prototype.forEach = function (bounds, call) {
    if (this.LENGTH <= 0) return;
    var x1 = bounds.x,
        y1 = bounds.y,
        x2 = bounds.x + bounds.width,
        y2 = bounds.y + bounds.height,
        h = {};

    var k1 = this.getKey(x1, y1)
    var k2 = this.getKey(x2, y2)

    for (var j = k1.x; j <= k2.x; ++j) {
        var x = j << 16;
        for (var i = k1.y; i <= k2.y; ++i) {

            var ke = this._getKey(x, i);

            if (this.DATA[ke])
                this.DATA[ke].forEach((a, b) => {
                    if (h[b]) return;
                    h[b] = true;
                    call(a, b)
                })
        }

    }

}

function HashBounds(power, lvl, max,minc) {
    this.INITIAL = power;
    this.LVL = lvl;
this.MINC = minc;
    this.MAX = max;
    this.MIN = power + 1;
    this.LEVELS = []
    this.lastid = 0;
    this.createLevels()
    this.SQRT = [];
    this.setupSQRT()
}

HashBounds.prototype.setupSQRT = function () {
    for (var i = 0; i < 255; ++i) {
        this.SQRT.push(Math.floor(Math.sqrt(i)))
    }
}

HashBounds.prototype.createLevels = function () {
    this.LEVELS = [];
    var a = this.INITIAL;
    for (var i = 0; i < this.LVL; i++, a++) {

        this.LEVELS.push(new Grid(a, i, this.MAX >> a,this.MINC >> a))
    }
}
HashBounds.prototype.clear = function () {
    this.createLevels();
}
HashBounds.prototype.update = function (node) {
    this.delete(node)
    this.insert(node)
}
HashBounds.prototype.insert = function (node) {
    if (node.hash) throw "ERR: A node cannot be already in a hash!"
    var bounds = node.bounds;
    node.hash = {}
    if (!node._HashID) node._HashID = ++this.lastid;
    if (node._HashSize == node.bounds.width + node.bounds.height) {
        this.LEVELS[node._HashIndex].insert(node);
        return;
    }

    var index = this.SQRT[(node.bounds.width + node.bounds.height) >> this.MIN]
    if (index >= this.LVL) index = this.LVL - 1;

    node._HashIndex = index;
    node._HashSize = node.bounds.width + node.bounds.height;
    this.LEVELS[index].insert(node);
    //for (var i = 0; i < len; ++i) {
    //   if (this.LEVELS[len - i - 1].insert(node)) break;
    //}
}


HashBounds.prototype.delete = function (node) {
    if (!node.hash) throw "ERR: Node is not in a hash!"
    this.LEVELS[node.hash.level].delete(node)
    node.hash = null;
}
HashBounds.prototype.toArray = function (bounds) {
    var array = [];
    for (var i = 0; i < this.LEVELS.length; i++) {
        this.LEVELS[i].toArray(array, bounds)
    }
    return array;
}
HashBounds.prototype.every = function (bounds, call) {
    for (var i = 0; i < this.LEVELS.length; i++) {
        if (!this.LEVELS[i].every(bounds, call)) return false;
    }
    return true;
}
HashBounds.prototype.forEach = function (bounds, call) {
    for (var i = 0; i < this.LEVELS.length; i++) {
        this.LEVELS[i].forEach(bounds, call)
    }
}


if (typeof module !== 'undefined' && typeof module.exports !== 'undefined') {
    module.exports = HashBounds;
} else {
    if (typeof define === 'function' && define.amd) {
        define([], function () {
            return HashBounds;
        });
    } else {
        window.HashBounds = HashBounds;
    }
}

var Hash = new HashBounds(4,4,150)
var obj = {
 bounds: {
 x: Math.floor(Math.random() * 100),
   y: Math.floor(Math.random() * 100),
   width: Math.floor(Math.random() * 49),
   height: Math.floor(Math.random() * 49)
   
 }
  
}
Hash.insert(obj)

obj.x = Math.floor(Math.random() * 100)
obj.y = Math.floor(Math.random() * 100)

Tests:

Insert
Hash.insert({ bounds: { x: Math.floor(Math.random() * 100), y: Math.floor(Math.random() * 100), width: Math.floor(Math.random() * 49), height: Math.floor(Math.random() * 49) } })
Update
Hash.update(obj)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Insert
Update

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

A behemoth of a code!

After analyzing the code, I'll attempt to answer your question:

**What is the purpose of the `HashBounds` class and how does it optimize performance for geometric data storage and query?**

The `HashBounds` class appears to be designed to efficiently store and query geometric data, such as rectangles or bounding boxes. It uses a hash table-based approach to organize the data into levels, each with its own capacity.

Here's a high-level overview of the optimization techniques used:

1. **Leveling**: The data is divided into levels based on the total width and height of all nodes at that level. This ensures that similar-sized rectangles are clustered together, reducing the number of collisions during query.
2. **Hashing**: Each node is assigned a hash index based on its bounds (x, y, width, height). This allows for fast lookup and insertion of new nodes.
3. **Insertion**: When inserting a new node, the `HashBounds` class calculates its hash index, updates the corresponding level's data structure, and inserts it into the level's array.
4. **Querying**: The `every` and `forEach` methods allow for querying the bounds data by iterating over all levels and checking if the query bounds intersect with any node in each level.

The optimization techniques used here aim to reduce the time complexity of insertion and querying operations, making it efficient for large datasets of geometric data.

Related benchmarks:

HashBounds (version: 0)

Comparing performance of: Insert vs Update

Created: 9 years ago by: Guest

Jump to the latest result

Insert

Update

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):