Benchmark: Find Smallest Number Not In An Array With Dynamic Max Value

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); const maxSetValue = array.reduce(Math.max); function findSet() { for (let i = 0; i < maxSetValue; i++) if (!set.has(i)) return i; return -1; } findSet();
Sort With For Loop
const sortedArray = array.slice().sort((a, b) => a - b); const maxSortValue = sortedArray[array.length - 1]; function findSort() { for (let i = 0; i < maxSortValue; 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

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

LLMs can make mistakes. Check important info.

Let's dive into the world of JavaScript microbenchmarks on MeasureThat.net.

**Benchmark Definition**

The provided JSON represents a benchmark for finding the smallest number not in an array with dynamic maximum value. The script preparation code generates an array of 10,000 random numbers and fills it with `undefined` values. This creates a unique scenario where the algorithm needs to find the smallest missing number within the range of the maximum value.

**Options Compared**

There are three approaches compared:

1. **Set With For Loop**: This approach uses a `Set` data structure to keep track of numbers in the array. The function iterates through the array's length, checking if each number is present in the set. If not, it returns that number.
2. **Sort With For Loop**: This approach sorts the array and then finds the smallest missing number by iterating through the sorted array's maximum value.
3. **Sort With Reduce**: This approach uses the `reduce` method to find the smallest missing number. It sorts the array and then iterates through it, updating an accumulator with the minimum difference between the current number and the previous number.

**Pros and Cons**

*   **Set With For Loop**: Pros:
    *   Uses a built-in data structure (Set) for efficient lookups.
    *   Simple to understand and implement.
    *
    *   Cons:
    *   Iterates through the array's length, which may be slower than other methods for large arrays.
*   **Sort With For Loop**: Pros:
    *   Efficiently finds the smallest missing number by leveraging the sorted array.
    *   Still simple to understand and implement.
*
    *   Cons:
    *   Requires sorting the array, which has a time complexity of O(n log n).
        This may be slower than other methods for large arrays.
*   **Sort With Reduce**: Pros:
    *   Efficiently finds the smallest missing number using the `reduce` method.
    *   Only requires a single pass through the sorted array.
*
    *   Cons:
    *   Less intuitive to understand and implement, especially for those without experience with reduce methods.

**Libraries and Special Features**

*   **Set**: A built-in JavaScript data structure used in the "Set With For Loop" approach. It provides efficient lookups and insertion operations.
*   No specific libraries are mentioned in the provided benchmark definition. However, some browsers (like Opera) may use additional libraries or features to enhance performance.

**Other Considerations**

When comparing these approaches, consider the following factors:

*   **Time Complexity**: The Set With For Loop has a time complexity of O(n), while the Sort With For Loop and Sort With Reduce have a time complexity of O(n log n). This means that for large arrays, the Sort With For Loop or Sort With Reduce approach may be slower.
*   **Memory Usage**: The Set With For Loop uses more memory since it needs to store all numbers in the set. In contrast, the other approaches only iterate through the array once.
*   **Code Readability and Maintainability**: While readability and maintainability are subjective, the "Set With For Loop" approach tends to be simpler and easier to understand.

**Alternative Approaches**

Other approaches you might consider for this benchmark include:

1.  Using bitwise operations (e.g., finding the smallest missing number by using bitwise AND and OR operators).
2.  Leveraging mathematical concepts like modular arithmetic or binary search.
3.  Employing more advanced data structures, such as a binary search tree or a hash table.

However, keep in mind that these alternative approaches might have different time complexities, memory usage, or code readability requirements compared to the provided benchmark definition.

In conclusion, this benchmark provides an interesting comparison of three approaches for finding the smallest missing number in an array with dynamic maximum value. Understanding the pros and cons of each approach will help you choose the most suitable method for your specific use case.

Latest run results:

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

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/94.0.4606.81 Safari/537.36 OPR/80.0.4170.61

Browser/OS: Opera 80 on Windows

View result in a separate tab

Test name	Executions per second
Set With For Loop	0.3 Ops/sec
Sort With For Loop	387.0 Ops/sec
Sort With Reduce	141.4 Ops/sec

Related benchmarks:

Find Smallest Number Not In An Array With Dynamic Max Value (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

Set With For Loop

Sort With For Loop

Sort With Reduce

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