Benchmark: Intersection of multiple sorted arrays | Lodash _.intersection() vs Various custom optimized methods

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)

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

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)
Custom optimized function 2

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 7 months ago)

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

Browser/OS: Chrome 129 on Windows

View result in a separate tab

Test name	Executions per second
Lodash _.intersection()	5088.8 Ops/sec
Custom optimized function 1 (Best)	6959.0 Ops/sec
Custom optimized function 2	3813.1 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):

Measuring performance differences between various JavaScript approaches to solve the same problem is crucial for optimization and development efficiency.

Benchmark Overview

The provided benchmark compares three different methods to find the intersection of multiple sorted arrays:

Lodash _.intersection(): A built-in function from the popular utility library Lodash.
Custom optimized function 1 (Best): A custom implementation that sorts the arrays by length, starts with the smallest array as the base intersection set, and iterates over the remaining arrays filtering the intersection.
Custom optimized function 2: Another custom implementation that sorts the arrays by length and then uses the reduce() method to filter the intersection.

Options Compared

The three methods are compared in terms of their execution speed.

Pros and Cons of Each Approach

Lodash _.intersection():
- Pros: Fast, well-tested, and widely adopted.
- Cons: Not optimized for performance, may not be suitable for large datasets.
Custom optimized function 1 (Best):
- Pros: Optimized for performance, takes advantage of sorting by array length.
- Cons: Requires manual implementation and debugging.
Custom optimized function 2:
- Pros: Similar to the first custom approach but uses reduce() method.
- Cons: May be less efficient than the first custom approach due to overhead of reduce().

Library Usage

Lodash is a popular utility library that provides a wide range of functions for common tasks, including array manipulation. In this benchmark, Lodash _.intersection() is used as-is from the library.

Special JS Features or Syntax

None mentioned in the provided benchmark.

Other Considerations

The benchmark uses a randomization technique to create multiple sets of 1000 elements each.
The test case prepares both JavaScript code and HTML code for execution, including loading Lodash via CDN.
The benchmark measures the number of executions per second (ExecutionsPerSecond) as a metric.

Alternative Approaches

Other possible approaches to find the intersection of multiple sorted arrays include:

Using Array.prototype.filter() and manual iteration.
Employing data structures like heaps or balanced trees for efficient intersections.
Leveraging library functions from other frameworks, such as jQuery UI or Lodash alternatives.

While these alternative approaches might be viable, they are not directly compared in this benchmark.

LLMs can make mistakes. Check important info.

Measuring performance differences between various JavaScript approaches to solve the same problem is crucial for optimization and development efficiency.

**Benchmark Overview**

The provided benchmark compares three different methods to find the intersection of multiple sorted arrays:

1. Lodash _.intersection(): A built-in function from the popular utility library Lodash.
2. Custom optimized function 1 (Best): A custom implementation that sorts the arrays by length, starts with the smallest array as the base intersection set, and iterates over the remaining arrays filtering the intersection.
3. Custom optimized function 2: Another custom implementation that sorts the arrays by length and then uses the `reduce()` method to filter the intersection.

**Options Compared**

The three methods are compared in terms of their execution speed.

**Pros and Cons of Each Approach**

1. **Lodash _.intersection()**:
	* Pros: Fast, well-tested, and widely adopted.
	* Cons: Not optimized for performance, may not be suitable for large datasets.
2. **Custom optimized function 1 (Best)**:
	* Pros: Optimized for performance, takes advantage of sorting by array length.
	* Cons: Requires manual implementation and debugging.
3. **Custom optimized function 2**:
	* Pros: Similar to the first custom approach but uses `reduce()` method.
	* Cons: May be less efficient than the first custom approach due to overhead of `reduce()`.

**Library Usage**

Lodash is a popular utility library that provides a wide range of functions for common tasks, including array manipulation. In this benchmark, Lodash _.intersection() is used as-is from the library.

**Special JS Features or Syntax**

None mentioned in the provided benchmark.

**Other Considerations**

* The benchmark uses a randomization technique to create multiple sets of 1000 elements each.
* The test case prepares both JavaScript code and HTML code for execution, including loading Lodash via CDN.
* The benchmark measures the number of executions per second (ExecutionsPerSecond) as a metric.

**Alternative Approaches**

Other possible approaches to find the intersection of multiple sorted arrays include:

1. Using `Array.prototype.filter()` and manual iteration.
2. Employing data structures like heaps or balanced trees for efficient intersections.
3. Leveraging library functions from other frameworks, such as jQuery UI or Lodash alternatives.

While these alternative approaches might be viable, they are not directly compared in this benchmark.

Related benchmarks:

Intersection of multiple sorted arrays | Lodash _.intersection() vs Various custom optimized methods (version: 1)

Comparing performance of: Lodash _.intersection() vs Custom optimized function 1 (Best) vs Custom optimized function 2

Created: 7 months ago by: Registered User

Jump to the latest result

Lodash _.intersection()