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

​x
 
​
<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;
}

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

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

 
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

Experimental features:

Memory measurements supported only in Chrome.
For precise memory measurements Chrome must be launched with --enable-precise-memory-info flag.
More information: Monitoring JavaScript Memory

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

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:

Lodash _.intersection(): Using the _.intersection() function from Lodash, a popular JavaScript utility library.
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.
Custom optimized function 2: Another custom implementation that uses a similar approach to the first one, but with some minor optimizations.
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.

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: