Benchmark: array vs hashmap vs array-polling

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 findInArrayByPolling (key) {
    for (let i = 0, len = array.length ; i < len; i++) {
        if (array[i].key === key) {
            return array[i]
        }
    }
}

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 binary search array
const target = Math.floor(Math.random() * 2000); findInArray(target);
find by array polling
const target = Math.floor(Math.random() * 2000); findInArrayByPolling(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 binary search array
find by array polling
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 (iPhone; CPU iPhone OS 18_4 like Mac OS X) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/18.4 Mobile/15E148 Safari/604.1

Browser/OS: Mobile Safari 18 on iOS 18.4

View result in a separate tab

Test name	Executions per second
find by binary search array	11735196.0 Ops/sec
find by array polling	1927880.8 Ops/sec
find by hashmap	224067872.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's being tested.

**Benchmark Overview**

The benchmark is designed to compare three different approaches for searching an array: binary search, array polling, and using a hashmap (a data structure that maps keys to values).

**Options Being Compared**

1. **Binary Search**: This approach uses a sorting algorithm (in this case, the `Array.prototype.sort()` method) to sort the array and then searches for a target value by finding its middle index and recursively narrowing down the search range.
2. **Array Polling**: This approach iterates through the entire array, checking each element's key until it finds a match with the target value.
3. **Hashmap**: This approach creates an object (the hashmap) from the array and uses the `Object.prototype.hasOwnProperty()` method to find the target value.

**Pros and Cons of Each Approach**

1. **Binary Search**:
	* Pros: Fastest for large datasets, O(log n) time complexity.
	* Cons: Requires sorting the array first, which can be slow for very large arrays.
2. **Array Polling**:
	* Pros: Simple to implement, doesn't require sorting the array.
	* Cons: Slow for large datasets, O(n) time complexity.
3. **Hashmap**:
	* Pros: Fast lookup times, O(1) average time complexity.
	* Cons: Requires creating an object from the array, which can be slow for very large arrays.

**Library and Syntax Used**

The benchmark uses the following libraries:

1. **Array.prototype.sort()**: a built-in JavaScript method that sorts the elements of an array in place.
2. **Object.prototype.hasOwnProperty()**: a built-in JavaScript property that checks if an object has a particular property as its own.

There are no special JavaScript features or syntax used in this benchmark.

**Other Alternatives**

Some other approaches for searching an array include:

1. **Linear Search**: Similar to array polling, but uses a more efficient algorithm.
2. **Ternary Search**: A hybrid approach that combines elements of binary search and linear search.
3. **Interpolation Search**: An optimized version of binary search for uniformly distributed data.

These alternatives may be worth considering in certain situations, but are not part of the current benchmark.

Related benchmarks:

array vs hashmap vs array-polling (version: 0)

Comparing performance of: find by binary search array vs find by array polling vs find by hashmap

Created: 6 years ago by: Registered User

Jump to the latest result

find by binary search array

find by array polling

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