Benchmark: Include vs Binary search in sorted array vs Map.has() vs Object[] large ver.

Script Preparation code:

var array = [];
var map = new Map();
var obj = {};

for (var i = 0; i < 500000; i++){
  array.push(Math.random());
  map.set(i,true);
  obj[i]=true;
}
var sorted = array.sort()

function binaryIndexOf(searchElement) {

 
    var minIndex = 0;
    var maxIndex = this.length - 1;
    var currentIndex;
    var currentElement;
 
    while (minIndex <= maxIndex) {
        currentIndex = (minIndex + maxIndex) / 2 | 0;
        currentElement = this[currentIndex];
 
        if (currentElement < searchElement) {
            minIndex = currentIndex + 1;
        }
        else if (currentElement > searchElement) {
            maxIndex = currentIndex - 1;
        }
        else {
            return currentIndex;
        }
    }
 
    return -1;
}

Tests:

Includes
sorted.includes(5)
binary
binaryIndexOf.call(sorted, 5)
Map.has()
map.has(5);
Obj[]
obj[5]

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Includes
binary
Map.has()
Obj[]

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 2 years ago)

User agent: Mozilla/5.0 (Linux; Android 10; K) AppleWebKit/537.36 (KHTML, like Gecko) SamsungBrowser/24.0 Chrome/117.0.0.0 Mobile Safari/537.36

Browser/OS: Chrome Mobile 117 on Android

View result in a separate tab

Test name	Executions per second
Includes	40418.0 Ops/sec
binary	2862436.5 Ops/sec
Map.has()	6719135.5 Ops/sec
Obj[]	6677289.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 what's being tested in this benchmark.

**Benchmark Overview**

The benchmark is designed to compare the performance of different ways to search for an element in an array or object. The test cases are:

1. `sorted.includes(5)`: Searching for an element in a sorted array using the `includes` method.
2. `binaryIndexOf.call(sorted, 5)`: Searching for an element in a sorted array using a binary search algorithm (similar to Python's `bisect` module).
3. `map.has(5)`: Searching for an element in a Map object using the `has` method.
4. `obj[5]`: Searching for an element in an object using square bracket notation.

**Options Compared**

We have four options being compared:

1. **Includes**: The built-in `includes` method on sorted arrays.
2. **Binary Search**: A custom binary search algorithm implemented as a function (`binaryIndexOf.call(sorted, 5)`).
3. **Map.has()**: The `has` method on Map objects.
4. **Object Square Bracket Notation**: Searching for an element in an object using square bracket notation (`obj[5]`).

**Pros and Cons**

1. **Includes**:
	* Pros: Simple to implement, widely supported by browsers.
	* Cons: Can be slow for large arrays, as it needs to scan the entire array.
2. **Binary Search**:
	* Pros: Efficient for large datasets, as it uses a divide-and-conquer approach.
	* Cons: Requires manual implementation of the algorithm, which can be error-prone.
3. **Map.has()**:
	* Pros: Fast and efficient, especially for modern browsers that support Map objects.
	* Cons: May not be supported by older browsers or environments that don't have Map objects.
4. **Object Square Bracket Notation**:
	* Pros: Simple to implement, widely supported by browsers.
	* Cons: Can be slower than other methods, as it needs to create a new object and iterate over its properties.

**Library and Syntax**

1. The `includes` method is built into JavaScript and is used on sorted arrays.
2. The `binaryIndexOf` function is implemented using a custom binary search algorithm. This feature was introduced in ECMAScript 2015 (ES6) and allows for more efficient searching of sorted arrays.
3. Map objects are supported by modern browsers, but the `has` method is not part of the standard JavaScript API. It's a modern addition that allows for fast lookup of values in Map objects.

**Test Case Considerations**

1. The test cases use a large array (500,000 elements) to simulate real-world scenarios.
2. The array is sorted before each test case to ensure that the search algorithms are being compared fairly.
3. The `binaryIndexOf` function uses the `call` method to bind the `sorted` array as the context for the binary search algorithm.

**Alternatives**

Other alternatives for searching in arrays or objects include:

1. Using a data structure like a balanced binary tree or a heap, which can provide efficient searching and insertion capabilities.
2. Implementing a custom sorting algorithm that takes into account the specific use case or requirements of the application.
3. Using a library or framework that provides optimized search functionality, such as Google's Closure Library.

Overall, this benchmark provides a comprehensive comparison of different search algorithms for arrays and objects in JavaScript, highlighting their pros and cons, and providing insights for developers to optimize their code for performance.

Related benchmarks:

Include vs Binary search in sorted array vs Map.has() vs Object[] large ver. (version: 0)

Comparing performance of: Includes vs binary vs Map.has() vs Obj[]

Created: 2 years ago by: Guest

Jump to the latest result

Includes

binary

Map.has()

Obj[]

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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