Benchmark: array vs hashmap

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() {
    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: 4 years ago)

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

Browser/OS: Chrome 78 on Mac OS X 10.14.5

View result in a separate tab

Test name	Executions per second
find by array	0.0 Ops/sec
find by hashmap	548360.5 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's break down the provided benchmark and explain what is being tested, compared, and the pros/cons of each approach.

**Benchmark Definition JSON**

The benchmark measures the performance of two data structures: an array and a hashmap (also known as a hash map or dictionary). The test case creates a large array with 2000 objects, each containing a random key and property value. The script then reduces this array to create a hashmap, where each key in the array is used as a key in the hashmap.

**Test Cases**

There are two test cases:

1. **Find by Array**: This test case calls the `findInArray` function with a randomly generated target key.
2. **Find by Hashmap**: This test case calls the `findInHashMap` function with a randomly generated target key.

**Performance Comparison**

The benchmark is designed to compare the performance of searching for an element in an array versus a hashmap.

**Options Compared**

*   Array Search: The `findInArray` function uses a binary search algorithm to find the target element in the array.
*   Hashmap Search: The `findInHashMap` function simply looks up the target key in the hashmap and returns the corresponding value if found, or undefined otherwise.

**Pros and Cons**

*   **Binary Search (Array Search)**:
    *   Pros:
        +   Suitable for ordered data structures like arrays.
        +   Can be more efficient than a linear search for large datasets with many duplicate elements.
    *   Cons:
        +   Requires the array to be sorted, which can be time-consuming for large datasets.
        +   May not perform well if the data is not uniformly distributed.

*   **Hashmap Search**:
    +   Pros:
        -   Generally faster and more efficient than linear search.
        -   Suitable for unordered or unsorted data structures like hashmaps.
    *   Cons:
        +   Requires O(1) average time complexity, but can be slower for certain edge cases (e.g., collisions).
        +   May not perform well if the hashmap is highly collision-prone.

**Library and Functionality**

The `findInArray` function uses a binary search algorithm implemented in the JavaScript built-in `Array.prototype.indexOf()` method or an external library like `binary-search.js`. The `bs` function (binary search) is used to find the target element, but this seems to be a custom implementation rather than using a standard library. Similarly, `findInHashMap` uses a simple lookup in the hashmap, which is implemented using JavaScript's built-in object.

**Special JS Feature or Syntax**

The benchmark does not use any special features or syntax that would require specific knowledge of JavaScript beyond basic syntax understanding.

**Other Alternatives**

If you were to create similar benchmarks for other data structures like linked lists or trees, you could consider the following:

*   Linked List Search: Implement a linear search or binary search algorithm on a singly-linked list.
*   Tree Search: Create a benchmark that tests the performance of searching for an element in a balanced binary search tree or an unbalanced tree.

Related benchmarks:

array vs hashmap (version: 0)

Comparing performance of: find by array vs find by hashmap

Created: 4 years ago by: Guest

Jump to the latest result

find by array

find by hashmap

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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