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

Script Preparation code:

var array = [];
var map = new Map();
var obj = {};

for (var i = 0; i < 50; i++){
  array.push(Math.floor(Math.random()* 100));
  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: one year ago)

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

Browser/OS: Chrome 103 on Linux

View result in a separate tab

Test name	Executions per second
Includes	9463395.0 Ops/sec
binary	4498052.0 Ops/sec
Map.has()	10006945.0 Ops/sec
Obj[]	10000874.0 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's break down the provided JSON and explain what's being tested, compared, and their pros and cons.

**Benchmark Definition**

The benchmark measures the performance of three different approaches to find an element in a sorted array:

1. `sorted.includes(5)`: This method uses a linear search algorithm, which checks each element in the array until it finds a match.
2. `binaryIndexOf.call(sorted, 5)`: This method uses a binary search algorithm, which divides the search space in half with each iteration.
3. `map.has(5)` and `obj[5]`: These methods use hash tables (Maps and objects, respectively) to store the elements of the array.

**Options being compared**

The benchmark compares the performance of these three approaches:

* **Linear Search (`includes`)**: A simple, but less efficient approach that checks each element in the array.
* **Binary Search (`binaryIndexOf`)**: A more efficient approach that divides the search space in half with each iteration.
* **Hash Table (`map.has()` and `obj[]`)**: Two alternative approaches that use hash tables to store and retrieve elements.

**Pros and Cons**

1. **Linear Search (`includes`)**:
	* Pros: Simple to implement, easy to understand.
	* Cons: Less efficient than other approaches, especially for large arrays.
2. **Binary Search (`binaryIndexOf`)**:
	* Pros: More efficient than linear search, especially for large arrays.
	* Cons: Requires a sorted array, can be complex to implement.
3. **Hash Table (`map.has()` and `obj[]`)**:
	* Pros: Fast lookups, easy to implement with modern JavaScript objects.
	* Cons: May have higher memory overhead due to the hash table.

**Library usage**

The benchmark uses the following libraries:

1. **Array.prototype.includes()**: A built-in method for checking if an element exists in an array.
2. `Map`: A built-in object for creating and storing key-value pairs.
3. `Object[]`: Not a standard JavaScript data structure, but rather an example of how to store elements in an object.

**Special JS features**

There are no special JavaScript features or syntax mentioned in the benchmark definition. The focus is on the underlying algorithms and data structures used by each approach.

**Other alternatives**

If you're looking for alternative approaches to find an element in a sorted array, consider:

1. **Ternary search**: A hybrid of binary and linear search that combines the benefits of both.
2. **Exponential search**: An algorithm that uses exponential growth to find an element in a sorted array.

These alternatives may offer improved performance or trade-offs for specific use cases, but they are less well-known than the approaches compared in this benchmark.

Related benchmarks:

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

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

Created: one year ago by: Guest

Jump to the latest result

Includes

binary

Map.has()

Obj[]

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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