Benchmark: includes sorted vs unsorted

includes sorted vs unsorted (version: 0)

Comparing performance of: unsorted array includes existing item vs sorted array includes existing item vs unsorted array includes unexisting item vs sorted array includes unexisting item vs unsorted set has existing item vs sorted set has existing item vs unsorted set has unexisting item vs sorted set has unexisting item

Created: 6 years ago by: Guest

Jump to the latest result

Script Preparation code:

const getRandomInteger = (min, max) => {
  const internalMin = Math.ceil(min)
  const internalMax = Math.floor(max)

  return Math.floor(Math.random() * (internalMax - internalMin)) + internalMin
}

const alphabet = ['A', 'a', 'B', 'b', 'C', 'c', 'D', 'd', 'E', 'e', 'F', 'f', 'G', 'g', 'H', 'h', 'I', 'i', 'J', 'j', 'K', 'k', 'L', 'l', 'M', 'm', 'N', 'n', 'O', 'o', 'P', 'p', 'Q', 'q', 'R', 'r', 'S', 's', 'T', 't', 'U', 'u', 'V', 'v', 'W', 'w', 'X', 'x', 'Y', 'y', 'Z', 'z']

const getRandomString = (length) =>
  Array.from({
    length
  }, () =>
    alphabet[getRandomInteger(0, alphabet.length)]).join('')

window.unsortedArray = Array.from({
  length: 50
}, () => getRandomString(getRandomInteger(5, 15)))
window.sortedArray = [...unsortedArray].sort()

window.unsortedSet = new Set([...unsortedArray])
window.sortedSet = new Set([...sortedArray])

window.existingItem = unsortedArray[getRandomInteger(0, unsortedArray.length)]
window.unexistingItem = getRandomString(25)

Tests:

unsorted array includes existing item
unsortedArray.includes(existingItem)
sorted array includes existing item
sortedArray.includes(existingItem)
unsorted array includes unexisting item
unsortedArray.includes(unexistingItem)
sorted array includes unexisting item
sortedArray.includes(unexistingItem)
unsorted set has existing item
unsortedSet.has(existingItem)
sorted set has existing item
sortedSet.has(existingItem)
unsorted set has unexisting item
unsortedSet.has(unexistingItem)
sorted set has unexisting item
sortedSet.has(unexistingItem)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
unsorted array includes existing item
sorted array includes existing item
unsorted array includes unexisting item
sorted array includes unexisting item
unsorted set has existing item
sorted set has existing item
unsorted set has unexisting item
sorted set has unexisting item

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

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

LLMs can make mistakes. Check important info.

I'll break down the provided benchmark definition and test cases, explaining what is tested, the pros and cons of each approach, and other considerations.

**Benchmark Definition**

The benchmark definition consists of two types of tests:

1. **Array Inclusion Tests**: These tests check if an element exists in a sorted or unsorted array.
2. **Set Inclusion Tests**: These tests check if an element exists in a sorted or unsorted set.

**Array Inclusion Tests**

These tests are similar, but with one key difference: the array is either sorted or unsorted. The tests are:

* `unsortedArray.includes(existingItem)`
* `sortedArray.includes(existingItem)`
* `unsortedArray.includes(unexistingItem)`
* `sortedArray.includes(unexistingItem)`

**Set Inclusion Tests**

These tests are similar to the array inclusion tests, but they use sets instead of arrays. The tests are:

* `unsortedSet.has(existingItem)`
* `sortedSet.has(existingItem)`
* `unsortedSet.has(unexistingItem)`
* `sortedSet.has(unexistingItem)`

**Pros and Cons of Each Approach**

1. **Arrays**:
	* Pros: Arrays can be more efficient for large datasets, as they are contiguous blocks of memory.
	* Cons: Sorting an array can take O(n log n) time in the worst case, which can impact performance.
2. **Sets**:
	* Pros: Sets have faster lookups (O(1)) and are generally more efficient for large datasets.
	* Cons: Sets may require additional memory to store the hash table used for lookup.

**Other Considerations**

1. **Cache Locality**: The proximity of elements in an array can lead to better cache locality, which can improve performance.
2. **Null Checks**: In some cases, null checks may be necessary before performing inclusion tests.
3. **Data Distribution**: The distribution of data within the arrays and sets can impact performance.

**Test Results**

The test results show that the set-based tests (e.g., `sortedSet.has(existingItem)`) tend to perform better than their array-based counterparts. This is likely due to the O(1) lookup time in sets, which provides a significant performance advantage over the O(n log n) sorting time for arrays.

However, it's essential to note that these results may not be representative of all use cases or data distributions. The actual performance difference between array and set-based tests will depend on the specific requirements of your application.

In conclusion, when deciding between array-based and set-based inclusion tests, consider the trade-offs between efficiency, memory usage, and caching locality. Set-based tests are generally more efficient for large datasets, but array-based tests may be preferred in cases where the dataset is small or cache locality is a concern.

Related benchmarks: