Benchmark: Intersection of multiple sorted arrays | All positive, Max number isn't large | Lodash _.intersection() vs Various custom optimized methods

Intersection of multiple sorted arrays | All positive, Max number isn't large | Lodash _.intersection() vs Various custom optimized methods (version: 6)

Comparing performance of: Lodash _.intersection() vs Custom optimized function 1 (Best for arbitrary numbers) vs Custom optimized function 2 vs Custom optimized function 3 (Best for reasonable max)

Created: one year ago by: Registered User

Jump to the latest result

HTML Preparation code:

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

Script Preparation code:

var arr1 = [];
var arr2 = [];
var arr3 = [];
var arr4 = [];

for (i = 0; i < 1000; i++) {
    arr1.push(getRandom());
    arr2.push(getRandom());
    arr3.push(getRandom());
    arr4.push(getRandom());

    arr1.sort();
    arr2.sort();
    arr3.sort();
    arr4.sort();
}

function getRandom() {
    const minimum = 1;
    const maximum = 1000;
    var randomnumber = Math.floor(Math.random() * (maximum - minimum + 1)) + minimum;
    return randomnumber;
}

Tests:

Lodash _.intersection()
const results = new Set(_.intersection(arr1, arr2, arr3, arr4));
Custom optimized function 1 (Best for arbitrary numbers)
function intersectMultipleArrays(...arrays) { if (arrays.length === 0) return new Set(); // Sort arrays by length to optimize operations arrays.sort((a, b) => a.length - b.length); // Start with the smallest array as the base intersection set let intersection = new Set(arrays[0]); // Iterate over the remaining arrays and filter the intersection for (let i = 1; i < arrays.length; i++) { intersection = new Set(arrays[i].filter(item => intersection.has(item))); // Early exit if intersection is empty if (intersection.size === 0) return new Set(); } // Return the final Set return intersection; } const results = intersectMultipleArrays(arr1, arr2, arr3, arr4);
Custom optimized function 2
const results = new Set( [arr1, arr2, arr3, arr4] .sort((a, b) => b.length - a.length) .reduce((a, b) => a.filter(aValue => b.includes(aValue))) );
Custom optimized function 3 (Best for reasonable max)
function intersectMultipleArraysRevised(...arrays) { let maximum = -1; for (let i = 0; i < arrays.length; i++) { for (let j = 0; j < arrays[i].length; j++) { const num = arrays[i][j]; if (num > maximum) { maximum = num; } } } const count = new Array(maximum + 1).fill(0); for (let i = 0; i < arrays.length; i++) { for (let j = 0; j < arrays[i].length; j++) { const num = arrays[i][j]; count[num]++; } } const result = new Set(); const arrLen = arrays.length; for (let i = 0; i <= maximum; i++) { if (count[i] === arrLen) { result.add(i); } } return result; } const results = intersectMultipleArraysRevised(arr1, arr2, arr3, arr4);

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Lodash _.intersection()
Custom optimized function 1 (Best for arbitrary numbers)
Custom optimized function 2
Custom optimized function 3 (Best for reasonable max)

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36

Browser/OS: Chrome 131 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
Lodash _.intersection()	11573.1 Ops/sec
Custom optimized function 1 (Best for arbitrary numbers)	15326.1 Ops/sec
Custom optimized function 2	6522.7 Ops/sec
Custom optimized function 3 (Best for reasonable max)	91182.9 Ops/sec

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

LLMs can make mistakes. Check important info.

Measuring the performance of different approaches for intersecting multiple sorted arrays is an interesting benchmark.

**What is being tested?**

The provided JSON represents four different test cases for finding the intersection of four sorted arrays using various methods:

1. **Lodash _.intersection()**: Using the `_.intersection()` function from Lodash, a popular JavaScript utility library.
2. **Custom optimized function 1 (Best for arbitrary numbers)**: A custom implementation that sorts the arrays by length in descending order and then iterates over them to find the intersection.
3. **Custom optimized function 2**: Another custom implementation that uses a similar approach to the first one, but with some minor optimizations.
4. **Custom optimized function 3 (Best for reasonable max)**: A third custom implementation that is optimized for finding intersections in arrays with relatively small maximum values.

**Options comparison**

The four test cases compare the performance of different approaches:

*   **Lodash _.intersection()**: Using a well-established and widely-used library.
    *   Pros:
        *   Easy to use and maintain
        *   Well-tested and optimized
    *   Cons:
        *   Additional dependency on Lodash
        *   Might be slower due to the overhead of the library
*   **Custom optimized function 1 (Best for arbitrary numbers)**: A custom implementation that sorts arrays by length in descending order.
    *   Pros:
        *   Optimized for large and small arrays
        *   No additional dependencies required
    *   Cons:
        *   More complex to implement and maintain
        *   Might require more memory due to the sorting step
*   **Custom optimized function 2**: A custom implementation similar to the first one but with minor optimizations.
    *   Pros:
        *   Easier to understand and maintain than the first custom implementation
        *   Still optimized for large and small arrays
    *   Cons:
        *   Might not be as efficient as the best possible approach
*   **Custom optimized function 3 (Best for reasonable max)**: A custom implementation that is optimized specifically for arrays with relatively small maximum values.
    *   Pros:
        *   Optimized for a specific use case
        *   Can potentially outperform the first two custom implementations in this scenario
    *   Cons:
        *   Not optimized for arbitrary numbers or extremely large arrays

**Browser results**

The latest benchmark results show that:

*   **Custom optimized function 3 (Best for reasonable max)** performs the best, with an average execution speed of approximately 7.6 executions per second.
*   **Custom optimized function 1 (Best for arbitrary numbers)** comes in second, with an average execution speed of around 5.8 executions per second.

This result suggests that optimizing for a specific use case can lead to significant performance improvements.

**Takeaways**

When working on intersecting multiple sorted arrays:

*   Consider using well-established libraries like Lodash, especially if you prioritize ease of use and maintainability.
*   For custom implementations, optimize for the most common scenarios (e.g., arbitrary numbers or reasonable max values).
*   Carefully consider trade-offs between complexity, performance, and maintainability when implementing custom solutions.

Related benchmarks: