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

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();
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();
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();

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

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: 6 months ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:143.0) Gecko/20100101 Firefox/143.0

Browser/OS: Firefox 143 on Windows

View result in a separate tab

Test name	Executions per second
Set With For Loop	3516.7 Ops/sec
Sort With For Loop	1933.7 Ops/sec
Sort With Reduce	1620.5 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 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:

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: 4 years ago by: Guest

Jump to the latest result

Set With For Loop

Sort With For Loop

Sort With Reduce

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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