Benchmark: Find Smallest Number Not In An Array

Script Preparation code:

var array = [];
array.length = 10000;
array.fill(undefined);
array = array.map(() => Math.floor(Math.random() * array.length));

AخA
 
var array = [];array.length = 10000;array.fill(undefined);array = array.map(() => Math.floor(Math.random() * array.length));

Tests:

Set With For Loop

const set = new Set(array);

function findSet() {
  for (let i = 0; i < array.length; i++) 
    if (!set.has(i)) return i;

  return -1;
}

findSet();

​x
 
const set = new Set(array);​function findSet() {  for (let i = 0; i < array.length; i++)     if (!set.has(i)) return i;​  return -1;}​findSet();

Sort With For Loop

const sortedArray = array.slice().sort((a, b) => a - b);

function findSort() {
	for (let i = 0; i < array.length; i++)
      if (!sortedArray.includes(i)) return i;
  
  return -1;
}

findSort();

 
const sortedArray = array.slice().sort((a, b) => a - b);​function findSort() {    for (let i = 0; i < array.length; i++)      if (!sortedArray.includes(i)) return i;    return -1;}​findSort();

Sort With Reduce

const sortedReduceArray = array.slice().sort((a, b) => a - b);

function findReduce() {
	return sortedReduceArray.reduce((acc, current) => (Math.abs(current - acc) > 1 ? Math.min : Math.max)(current, acc), 0) + 1;
}

findReduce();

 
const sortedReduceArray = array.slice().sort((a, b) => a - b);​function findReduce() {    return sortedReduceArray.reduce((acc, current) => (Math.abs(current - acc) > 1 ? Math.min : Math.max)(current, acc), 0) + 1;}​findReduce();

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Experimental features:

Memory measurements supported only in Chrome.
For precise memory measurements Chrome must be launched with --enable-precise-memory-info flag.
More information: Monitoring JavaScript Memory

Test case name	Result
Set With For Loop
Sort With For Loop
Sort With Reduce

Fastest: N/A

Slowest: N/A

Latest run results:

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

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

Browser/OS: Chrome 111 on Linux

View result in a separate tab

Test name	Executions per second
Set With For Loop	4812.8 Ops/sec
Sort With For Loop	642.0 Ops/sec
Sort With Reduce	329.5 Ops/sec

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

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

Benchmark Purpose

The main goal of this benchmark is to find the smallest number not present in an array. This problem can be useful for various scenarios, such as detecting missing values or finding the smallest gap in a sequence.

Test Cases

There are three test cases:

Set With For Loop: This approach uses a Set data structure to store the indices of the array and then iterates through the original array using a for loop to find the first index not present in the set.
Sort With For Loop: In this approach, the entire array is sorted using the Array.prototype.sort() method and then iterates through the sorted array using a for loop to find the first index not present in the sorted array.
Sort With Reduce: This approach uses the Array.prototype.reduce() method to find the smallest number by iterating through the sorted array and comparing each element with its predecessor.

Comparison

The three approaches are compared based on their performance metrics, such as the time taken to execute the test case (measured in executions per second).

Pros/Cons of Each Approach:

Set With For Loop:
- Pros:
  - Simple and easy to understand.
  - Only requires iteration through the original array.
- Cons:
  - May be slower due to the overhead of creating a set and performing lookups.
Sort With For Loop:
- Pros:
  - Can be faster than Set With For Loop, especially for larger arrays.
- Cons:
  - Requires sorting the entire array, which can be slow for large inputs.
Sort With Reduce:
- Pros:
  - Similar to Sort With For Loop but with reduced overhead (no explicit loop).
- Cons:
  - May require more memory due to the use of a temporary accumulator variable.

Libraries and Special Features:

No external libraries are used in this benchmark.
The Array.prototype.sort() method is used, which is a built-in JavaScript function.
The Array.prototype.reduce() method is also used, which is another built-in JavaScript function.
There is no use of special JavaScript features like async/await or generators.

Alternative Approaches:

Other approaches to find the smallest missing number in an array include:

Binary Search: Use binary search algorithm to find the smallest missing number, especially for large arrays.
Hash Table: Use a hash table data structure to store indices of the array and then iterate through the original array to find the first index not present in the hash table.
Mathematical Formula: Derive a mathematical formula to calculate the smallest missing number directly from the properties of the array.

These alternative approaches may offer improved performance or efficiency for specific use cases, but they are not explored in this benchmark setup.

LLMs can make mistakes. Check important info.

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

**Benchmark Purpose**

**Test Cases**

There are three test cases:

1. **Set With For Loop**: This approach uses a `Set` data structure to store the indices of the array and then iterates through the original array using a for loop to find the first index not present in the set.
2. **Sort With For Loop**: In this approach, the entire array is sorted using the `Array.prototype.sort()` method and then iterates through the sorted array using a for loop to find the first index not present in the sorted array.
3. **Sort With Reduce**: This approach uses the `Array.prototype.reduce()` method to find the smallest number by iterating through the sorted array and comparing each element with its predecessor.

**Comparison**

The three approaches are compared based on their performance metrics, such as the time taken to execute the test case (measured in executions per second).

**Pros/Cons of Each Approach:**

1. **Set With For Loop**:
	* Pros:
		+ Simple and easy to understand.
		+ Only requires iteration through the original array.
	* Cons:
		+ May be slower due to the overhead of creating a set and performing lookups.
2. **Sort With For Loop**:
	* Pros:
		+ Can be faster than Set With For Loop, especially for larger arrays.
	* Cons:
		+ Requires sorting the entire array, which can be slow for large inputs.
3. **Sort With Reduce**:
	* Pros:
		+ Similar to Sort With For Loop but with reduced overhead (no explicit loop).
	* Cons:
		+ May require more memory due to the use of a temporary accumulator variable.

**Libraries and Special Features:**

* No external libraries are used in this benchmark.
* The `Array.prototype.sort()` method is used, which is a built-in JavaScript function.
* The `Array.prototype.reduce()` method is also used, which is another built-in JavaScript function.
* There is no use of special JavaScript features like async/await or generators.

**Alternative Approaches:**

Other approaches to find the smallest missing number in an array include:

1. **Binary Search**: Use binary search algorithm to find the smallest missing number, especially for large arrays.
2. **Hash Table**: Use a hash table data structure to store indices of the array and then iterate through the original array to find the first index not present in the hash table.
3. **Mathematical Formula**: Derive a mathematical formula to calculate the smallest missing number directly from the properties of the array.

These alternative approaches may offer improved performance or efficiency for specific use cases, but they are not explored in this benchmark setup.

Related benchmarks:

Find Smallest Number Not In An Array (version: 0)

Comparing performance of: Set With For Loop vs Sort With For Loop vs Sort With Reduce

Created: 3 years ago by: Guest

Jump to the latest result