Benchmark: array vs hashmap 2

Script Preparation code:

const array = [];

for (let i = 0; i < 2000; i++) {
    array.push({
        key: i,
        prop: Math.floor(Math.random() * 10000)
    })
}

const hashmap = array.reduce((mapper, next) => ({
    ...mapper,
    [next.key]: next
}), {});

function findInArray (key) {
    const index = bs(array, key, function(element, needle) {
        return element.key - needle;
    });
    return index > 0 ? array[index] : undefined;
}

function findInHashMap (key) {
    return hashmap[key] || undefined;
}

function bs(haystack, needle, comparator, low, high) {
    var mid, cmp;
  
    if(low === undefined)
      low = 0;
  
    else {
      low = low|0;
      if(low < 0 || low >= haystack.length)
        throw new RangeError("invalid lower bound");
    }
  
    if(high === undefined)
      high = haystack.length - 1;
  
    else {
      high = high|0;
      if(high < low || high >= haystack.length)
        throw new RangeError("invalid upper bound");
    }
  
    while(low <= high) {
      // The naive `low + high >>> 1` could fail for array lengths > 2**31
      // because `>>>` converts its operands to int32. `low + (high - low >>> 1)`
      // works for array lengths <= 2**32-1 which is also Javascript's max array
      // length.
      mid = low + ((high - low) >>> 1);
      cmp = +comparator(haystack[mid], needle, mid, haystack);
  
      // Too low.
      if(cmp < 0.0)
        low  = mid + 1;
  
      // Too high.
      else if(cmp > 0.0)
        high = mid - 1;
  
      // Key found.
      else
        return mid;
    }
  
    // Key not found.
    return ~low;
}

Tests:

find by array
const target = Math.floor(Math.random() * 2000); findInArray(target);
find by hashmap
const target = Math.floor(Math.random() * 2000); findInHashMap(target);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
find by array
find by hashmap

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/132.0.0.0 Safari/537.36

Browser/OS: Chrome 132 on Linux

View result in a separate tab

Test name	Executions per second
find by array	9958752.0 Ops/sec
find by hashmap	40062960.0 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's break down the provided benchmark and explain what is being tested, compared, and discussed.

**Benchmark Definition**

The benchmark consists of two parts:

1. **Script Preparation Code**: A JavaScript code that creates an array of 2000 objects with random properties and generates a hash map from the array using the `reduce()` method.
2. **Individual Test Cases**: Two test cases:
	* "find by array": The script calls the `findInArray()` function, passing a randomly generated target key as an argument.
	* "find by hashmap": The script calls the `findInHashMap()` function, passing the same randomly generated target key as an argument.

**What is being tested?**

The benchmark is testing the performance difference between two data structures: arrays and hash maps. Specifically, it's comparing the execution time of finding a specific element in each data structure using two different functions:

* `findInArray()`: Searches for an element in the array using a binary search algorithm (implemented using the `bs()` function).
* `findInHashMap()`: Directly accesses the value associated with the target key in the hash map.

**Options compared**

The benchmark is comparing the performance of two approaches:

1. **Array-based search**: Using the `findInArray()` function to search for an element in the array.
2. **Hash map-based search**: Using the `findInHashMap()` function to directly access the value associated with the target key in the hash map.

**Pros and Cons**

* **Array-based search:**
	+ Pros:
		- Simple implementation.
		- Can be used for searching large datasets.
	+ Cons:
		- Has a time complexity of O(n), which means it scales poorly for large datasets.
		- Requires a sorting or indexing mechanism (binary search) to achieve efficient search performance.
* **Hash map-based search:**
	+ Pros:
		- Fast lookup times, with an average time complexity of O(1).
		- Suitable for large datasets.
	+ Cons:
		- Requires extra memory to store the hash map.
		- Can be slower for very small datasets due to the overhead of creating and maintaining the hash map.

**Library and its purpose**

The `bs()` function is a custom implementation of the binary search algorithm, which is used in both test cases. It's not a standard library function, but rather a utility function defined within the benchmark script.

**Special JS feature or syntax**

There doesn't appear to be any special JavaScript features or syntax used in this benchmark beyond the standard language features.

**Other alternatives**

If you're considering alternative data structures for similar use cases, here are a few options:

* **Linked lists**: Can offer better performance than arrays for sequential access scenarios.
* **Tries**: Optimized for prefix matching and can be useful for certain string-based search use cases.
* **Balanced trees** (e.g., AVL trees or red-black trees): Provide efficient search, insertion, and deletion operations with an average time complexity of O(log n).

Keep in mind that the choice of data structure depends on the specific requirements and constraints of your application.

Related benchmarks:

array vs hashmap 2 (version: 0)

Comparing performance of: find by array vs find by hashmap

Created: 6 years ago by: Guest

Jump to the latest result

find by array

find by hashmap

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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