Tries

JavaScript performance comparison

Test case created by x

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
C-style
function Trie(parent, prev, key, value) {
    if (key !== void 0)
        this.key = key;      // single-character key
    if (value !== void 0)
        this.value = value;  // user-defined value
    if (prev)
        prev.next = this;    // next sibling node
    else if (parent)
        parent.child = this; // first child node
}

// put a key/value pair in the trie
Trie.prototype.put = function(name, value) {
    var i = 0, t = this, len = name.length, prev, parent;
    down: while (t.child) {
        parent = t;
        t = t.child;
        // if first child didn't match, get next sibling
        while (t.key != name[i]) {
            if (!t.next) {
                prev = t;
                t = parent;
                break down;
            }
            t = t.next;
        }
        // key already exists, update the value
        if (++i > len) {
            t.value = value;
            return;
        }
    }
    // found any existing parts of the key, add the rest
    t = new this.constructor(t, prev, name[i]);
    while (++i <= len)
        t = new this.constructor(t, null, name[i]);
    t.name = name;
    t.value = value;
};

// get a value from the trie at the given key
Trie.prototype.get = function(name) {
    var i = 0, t = this.child, len = name.length;
    while (t) {
        if (t.key == name[i]) {
            if (i == len)
                return t.value;
            t = t.child;
            ++i;
        } else {
            t = t.next;
        }
    }
};

// --------

var dict = new Trie();

dict.put("true", "yes");
dict.put("truck", "vehicle");
dict.put("trowel", "dig");
dict.put("hat", "head");
dict.put("halt", "stop");
dict.put("ham", "pig");
dict.put("hammer", "nail");
dict.put("halt", "hold it");

console.log(dict)

console.log("true:", dict.get("true"));
console.log("truck:", dict.get("truck"));
console.log("trowel:", dict.get("trowel"));
console.log("hat:", dict.get("hat"));
console.log("halt:", dict.get("halt"));
console.log("ham:", dict.get("ham"));
console.log("hammer", dict.get("hammer"));

console.log(JSON.stringify(dict));
pending…
JS-style
function Trie(key) {
    this.key = key;
    this.value;
}

Trie.prototype.put = function (name, value) {

    var node = this,
        nameLength = name.length,
        i = 0,
        currentLetter;

    for (i = 0; i < nameLength; i++) {
        currentLetter = name[i];
        node = node[currentLetter] || (node[currentLetter] = new Trie(currentLetter));
    }

    node.value = value;
    node.name = name;

};

Trie.prototype.get = function (name) {

    var node = this,
        nameLength = name.length,
        i, node;

    for (i = 0; i < nameLength; i++) {
        if (!(node = node[name[i]])) break;
    }

    return (i === nameLength) ? node.value : 'not found';
};

// --------

var dict = new Trie();

dict.put("true", "yes");
dict.put("truck", "vehicle");
dict.put("trowel", "dig");
dict.put("hat", "head");
dict.put("halt", "stop");
dict.put("ham", "pig");
dict.put("hammer", "nail");
dict.put("halt", "hold it");

console.log(dict)

console.log("true:", dict.get("true"));
console.log("truck:", dict.get("truck"));
console.log("trowel:", dict.get("trowel"));
console.log("hat:", dict.get("hat"));
console.log("halt:", dict.get("halt"));
console.log("ham:", dict.get("ham"));
console.log("hammer", dict.get("hammer"));

console.log(JSON.stringify(dict));
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL.

0 Comments