Benchmark: Trie vs native map

Script Preparation code:

var Trie = class Trie {
  constructor() {
    this.root = { children: {} };
    this.size = 0;
  }

  add(key, value) {
    let node = this.root;
    for (let i = 0; i < key.length; ++i) {
      if (!node.children[key[i]]) node.children[key[i]] = { children: {} };
      node = node.children[key[i]];
    }
    node.value = value;
    this.size += 1;
    return value;
  }

  get(key) {
    let node = this.root;
    for (let i = 0; i < key.length; ++i) {
      if (!node.children[key[i]]) return undefined;
      node = node.children[key[i]];
    }
    return node.value;
  }

  remove(key) {
    this._remove(this.root, key, 0);
  }

  _remove(node, key, index) {
    if (!node) return undefined;

    if (index === key.length) {
      delete node.value;
      this.size -= 1;
    } else {
      const c = key[index];
      const child = this._remove(node.children[c], key, index + 1);
      if (child) node.children[c] = child;
      else delete node.children[c];
    }

    if (Object.keys(node.children).length === 0 && node.value === undefined)
      return undefined;
    return node;
  }
}

function pseudoRandom() {
  pseudoRandom.value = (pseudoRandom.value ** 2 + 3 * pseudoRandom.value + 1) % 26
  return pseudoRandom.value
}

pseudoRandom.value = 0

function createRandomString(length) {
  let s = ''
  for (let i = 0; i < length; ++i) {
    s += String.fromCharCode('a'.charCodeAt(0) + pseudoRandom())
  }
  return s
}

const N = 10000
const L = 1000
const strs = new Array(N)
for (let n = 0; n < N; ++n) strs[n] = createRandomString(L)

var ObjectWrapper = class ObjectWrapper {
  constructor() { this.data = {} }
  
  add(key, value) {
    this.data[key] = value
  }
  
  remove(key, value) {
    delete this.data[key]
  }
  
  get(key) {
    return this.data[key]
  }
}

function test(ds) {
  for (const s of strs) {
    ds.add(s, s)
  }
  for (const s of strs) {
    ds.get(s)
  }
  for (const s of strs) {
    ds.remove(s)
  }
}

Tests:

Trie
test(new Trie())
Native Object
test(new ObjectWrapper())

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Trie
Native Object

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 10 months ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/137.0.0.0 Safari/537.36

Browser/OS: Chrome 137 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
Trie	7.2 Ops/sec
Native Object	5782.0 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's dive into the world of MeasureThat.net and explore what's being tested in this benchmark.

**Benchmark Definition**

The benchmark compares two approaches: a custom Trie data structure implemented in JavaScript and a native Map object (built-in to modern browsers).

**Trie vs Native Map**

A Trie is a prefix tree data structure commonly used for efficient string matching, autocomplete, and retrieval of strings. The custom Trie implementation provided is quite basic, with methods for adding, retrieving, and removing nodes.

The native Map object, on the other hand, provides an object-like interface for storing key-value pairs and allows for fast lookups using the `get()` method.

**Options Compared**

Two options are being compared:

1. **Custom Trie**: The custom implementation of a Trie data structure in JavaScript.
2. **Native Map**: The built-in Map object in modern browsers, which provides an efficient way to store and retrieve key-value pairs.

**Pros and Cons**

**Custom Trie:**

Pros:

* Allows for fine-grained control over the data structure's implementation.
* Can be optimized for specific use cases or requirements.

Cons:

* Requires more code and manual management of node creation and traversal.
* May not perform as well as a native Map in terms of speed and efficiency.

**Native Map:**

Pros:

* Built-in to modern browsers, eliminating the need to implement and maintain a custom data structure.
* Provides fast and efficient lookups using the `get()` method.

Cons:

* Limited control over the underlying implementation.
* May not be suitable for specific use cases or requirements that require custom behavior.

**Other Considerations**

The benchmark also uses some additional libraries and features, such as:

* The `pseudoRandom` function, which generates pseudo-random numbers. Its purpose is unclear without more context.
* The `createRandomString` function, which generates random strings of a specified length.
* The `ObjectWrapper` class, which provides a simple way to store and retrieve key-value pairs using an object-like interface.

However, these libraries are not directly related to the comparison between the custom Trie and native Map approaches.

**Alternatives**

If you were to implement your own Trie data structure from scratch without using a native Map, you could consider using other alternatives such as:

* Using a binary search tree (BST) instead of a Trie.
* Implementing a hash table-based approach for fast lookups.
* Utilizing a graph data structure to represent the Trie.

Keep in mind that each of these alternatives would require significant changes to the implementation and may not offer the same performance benefits as the native Map.

Related benchmarks:

Trie vs native map (version: 0)

I know this is really useless comparison

Comparing performance of: Trie vs Native Object

Created: 4 years ago by: Registered User

Jump to the latest result

Trie

Native Object

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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