Benchmark: Inverted map lookup vs. dynamic map lookup vs. Set

Script Preparation code:

const testMap = {
    test0: '000',
    test1: '001',
    test2: '002',
    test3: '003',
    test4: '004',
    test5: '005',
    test6: '006',
    test7: '007',
    test8: '008',
    test9: '009'
};

const setA = new Set([000, 001, 002, 003, 004, 005, 006, 007, 008, 009]);

// tiny in-place inverting function using array reduce
const testMapInverted = Object.keys(testMap).reduce((acc, val) => {
    acc[testMap[val]] = val;
    return acc;
}, {});

function numberStringInvertedMapLookup(numberString) {
    return testMapInverted.hasOwnProperty(numberString);
}

function numberStringDynamicLookup(numberString) {
    return Object.values(testMap).includes(numberString);
}

function numberStringSet(numberString) {
    return setA.has(numberString);
}

function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

Tests:

Inverted map lookup
for(let i = 0; i < 10000; ++i) { numberStringInvertedMapLookup('00' + getRandomInt(20)); }
Dynamic lookup
for(let i = 0; i < 10000; ++i) { numberStringDynamicLookup('00' + getRandomInt(20)); }
Set
for(let i = 0; i < 10000; ++i) { numberStringSet('00' + getRandomInt(20)); }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Inverted map lookup
Dynamic lookup
Set

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.

Let's dive into the world of JavaScript microbenchmarks and analyze what's being tested on MeasureThat.net.

**Benchmark Definition JSON**

The benchmark definition JSON represents a set of test cases designed to compare three different lookup approaches: Inverted Map Lookup, Dynamic Lookup, and Set. The script preparation code provides the necessary data structures (a map `testMap` and a set `setA`) and functions for each lookup approach (`numberStringInvertedMapLookup`, `numberStringDynamicLookup`, and `numberStringSet`). The html preparation code is empty.

**Options being compared**

The three options being compared are:

1. **Inverted Map Lookup**: This approach uses an object to store the inverted map, where the values from the original map become keys in a new object.
2. **Dynamic Lookup**: This approach uses the `hasOwnProperty` method on the `testMap` object to check if a value exists as a key.
3. **Set**: This approach uses the `has` method on the `setA` set to check if an element exists.

**Pros and Cons of each approach**

1. **Inverted Map Lookup**:
	* Pros: Fast lookups, especially for small datasets.
	* Cons: Requires extra memory allocation and copying data from the original map.
2. **Dynamic Lookup**:
	* Pros: Fast lookups, and no additional memory allocation is required.
	* Cons: May be slower than inverted map lookup due to method call overhead.
3. **Set**:
	* Pros: Fast lookups, and no additional memory allocation is required.
	* Cons: Requires a separate data structure (set) which may incur additional memory overhead.

**Library used**

The library used in this benchmark is none, as it only relies on built-in JavaScript features like `Object.keys()`, `reduce()`, `hasOwnProperty()`, `includes()`, and `Set`.

**Special JS feature or syntax**

None mentioned. However, the use of `getRandomInt()` function with a maximum value that depends on the iteration number (`i`) might be considered a subtle optimization technique.

**Benchmark preparation code explanation**

The script preparation code creates a map `testMap` with keys and values, and a set `setA` containing elements in a specific order. The functions for each lookup approach are defined using these data structures.

For example, the `numberStringInvertedMapLookup()` function uses the `hasOwnProperty` method on the inverted map to check if a value exists as a key. Similarly, the `numberStringDynamicLookup()` function uses the `includes()` method on the `testMap` object to check if a value exists as a key.

The benchmark loop iterates 10,000 times and calls each lookup function with a random string generated using `getRandomInt()`. The results are likely used to compare the performance of each approach.

**Other alternatives**

If we were to consider alternative approaches for this benchmark, some options might include:

1. **Hash Table**: A more modern data structure that provides faster lookups than traditional maps.
2. **Binary Search Tree**: A data structure that allows for efficient lookup, insertion, and deletion operations.
3. **Trie**: A prefix tree data structure that can be used for fast string matching and lookup.

However, these alternatives might introduce additional complexity or overhead, so it's essential to consider the trade-offs before deciding which approach to use in a real-world scenario.

Related benchmarks:

Inverted map lookup vs. dynamic map lookup vs. Set (version: 0)

Comparing performance of: Inverted map lookup vs Dynamic lookup vs Set

Created: 5 years ago by: Guest

Jump to the latest result

Inverted map lookup

Dynamic lookup

Set

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):