Benchmark: Inverted map lookup vs. dynamic map lookup

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'
};

// 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 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)); }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Inverted map lookup
Dynamic lookup

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.

**Benchmark Overview**

The provided benchmark measures the performance of two approaches to map lookups in JavaScript: Inverted Map Lookup and Dynamic Lookup. The test case uses a tiny array `testMap` that maps numbers to strings, and a separate `testMapInverted` object is created by inverting this mapping using an array reduce function.

**Options Compared**

The benchmark compares the performance of two approaches:

1. **Inverted Map Lookup**: This approach uses the `hasOwnProperty` method to check if a given number string exists as a key in the `testMapInverted` object.
2. **Dynamic Lookup**: This approach uses the `includes` method to check if a given number string exists among the values of the `testMap` object.

**Pros and Cons**

1. **Inverted Map Lookup**
	* Pros:
		+ Can be faster for small to medium-sized maps due to caching effects.
		+ More intuitive and easier to implement for some developers.
	* Cons:
		+ May not perform well for large maps or fast-growing maps.
		+ Requires additional memory to store the inverted map.
2. **Dynamic Lookup**
	* Pros:
		+ Scalable and efficient for large maps.
		+ Simple and straightforward implementation.
	* Cons:
		+ May incur a performance penalty due to the use of `includes` method, which iterates over all values in the array.

**Library Usage**

In the benchmark, the `Object.keys()` method is used to get an array of keys from the `testMap` object. This is a built-in JavaScript function that returns an array of strings containing the property names (keys) of an object.

No external libraries are required for this benchmark.

**Special JS Feature or Syntax**

None are mentioned in the provided code snippet.

**Considerations**

When choosing between Inverted Map Lookup and Dynamic Lookup, consider the size and growth rate of your map. If your map is small to medium-sized, Inverted Map Lookup might be a good choice due to caching effects. However, for large maps or fast-growing maps, Dynamic Lookup is likely to perform better.

**Other Alternatives**

If you're interested in exploring other map lookup approaches, here are some alternatives:

1. **Hash Table**: A more traditional approach using a hash table (object with key-value pairs) for fast lookups.
2. **Trie**: A data structure optimized for prefix matching and efficient string searching.
3. **Splay Tree**: An self-balancing binary search tree that can provide good performance for map lookups.

Keep in mind that each of these alternatives has its own trade-offs and considerations, and the choice ultimately depends on your specific use case and requirements.

Related benchmarks:

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

Comparing performance of: Inverted map lookup vs Dynamic lookup

Created: 5 years ago by: Guest

Jump to the latest result

Inverted map lookup

Dynamic lookup

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