Benchmark: Array Intersection, big and small

HTML Preparation code:

<script src='https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.5/lodash.min.js'></script>

Script Preparation code:

var small = [...Array(100)].map(it => ~~(Math.random() * 1000));
var big = [...Array(1000)].map(it => ~~(Math.random() * 1000));

Tests:

big.filter(small.includes)
big.filter(x => small.includes(x))
small.filter(big.includes)
small.filter(x => big.includes(x))
Set intersection
[...new Set(big).intersection(new Set(small))]

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
big.filter(small.includes)
small.filter(big.includes)
Set intersection

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 27 days ago)

User agent: Mozilla/5.0 (iPhone; CPU iPhone OS 18_1_1 like Mac OS X) AppleWebKit/605.1.15 (KHTML, like Gecko) CriOS/131.0.6778.73 Mobile/15E148 Safari/604.1

Browser/OS: Chrome Mobile iOS 131 on iOS 18.1.1

View result in a separate tab

Test name	Executions per second
big.filter(small.includes)	16221.9 Ops/sec
small.filter(big.includes)	26554.5 Ops/sec
Set intersection	66366.3 Ops/sec

Autogenerated LLM Summary (model gpt-4o-mini, generated 27 days ago):

LLMs can make mistakes. Check important info.

The benchmark "Array Intersection, big and small" is designed to evaluate the performance of different approaches to finding the intersection of two arrays in JavaScript. The two arrays tested are `small`, consisting of 100 random integers between 0 and 999, and `big`, which contains 1000 such integers. The benchmark compares three different methods for finding the intersection of these arrays.

### Test Cases Overview

1. **big.filter(x => small.includes(x))**
   - **Description**: This approach uses the `filter` method on the `big` array. For each element `x` in `big`, it checks if `small` includes that element. If so, `x` is included in the output array.
   - **Performance**: This method has a time complexity of O(n * m), where `n` is the length of the `big` array and `m` is the length of the `small` array. This can become inefficient for larger datasets due to the repeated `includes` checks across the entirety of `small`.

2. **small.filter(x => big.includes(x))**
   - **Description**: This case is similar to the first but reverses the arrays. It filters the `small` array, checking for each element if it is included in `big`.
   - **Performance**: The performance characteristics are identical to the first method, also O(n * m). Here, however, since `small` is shorter, this method may perform better overall than the first for the specific case given.

3. **[...new Set(big).intersection(new Set(small))]**
   - **Description**: This approach makes use of the `Set` object, which stores unique values. Converting `big` and `small` arrays to sets eliminates duplicates. The method `intersection` is applied, assuming it is defined elsewhere, to identify common elements.
   - **Performance**: The expected time complexity for operations involving sets is generally more efficient for intersection tasks, running closer to O(n + m) for set creation plus the intersection operation. This efficiency typically makes it preferable when handling larger datasets with possible duplicates.

### Considerations

- **Pros & Cons**:
  - **Using Array Includes**:
    - Pros: Simple and easy to understand.
    - Cons: Performance degradation with larger datasets due to O(n * m) complexity.
  
  - **Using Set**:
    - Pros: More efficient due to faster lookups, especially when arrays contain duplicates. 
    - Cons: Higher memory usage due to the storage of unique values in a Set.

- **Library Usage**: 
  - The benchmark includes a reference to Lodash (though not directly used in benchmark tests shown). Lodash is a JavaScript utility library that provides functions for common programming tasks, including array manipulation and performance optimizations. While the current benchmark doesn't make use of Lodash functions, developers could leverage it for enhanced performance in more complex use cases.

### Other Alternatives

- **Sorting and Two-pointer Technique**: Sorting both arrays and using two pointers to find intersections can also be an efficient approach. This method has a time complexity of O(n log n + m log m), followed by O(n + m) for the traversal.

- **Using a HashMap**: Another alternative is to use a HashMap to store the elements of one array and then check against it while iterating through the second array. This also tends toward O(n + m) complexity but would involve additional memory.

- **Functional Programming Techniques**: Using libraries that focus on functional programming paradigms can offer cleaner syntax and potentially optimized performance, especially for larger datasets.

These considerations highlight the trade-offs between clarity, performance, and memory usage. The best choice often depends on the specific needs of the application, such as dataset size and performance requirements.

Related benchmarks:

Array Intersection, big and small (version: 1)

Comparing performance of: big.filter(small.includes) vs small.filter(big.includes) vs Set intersection

Created: 28 days ago by: Guest

Jump to the latest result

big.filter(small.includes)

small.filter(big.includes)

Set intersection

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model gpt-4o-mini, generated 27 days ago):