Benchmark: Compare set difference algorithms

HTML Preparation code:

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

​x
 
​
<script src='https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.5/lodash.min.js'></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/ramda/0.25.0/ramda.min.js"></script>

Script Preparation code:

function getRandomInt(max) {
  return Math.floor(Math.random() * max);
}

var itemsA = [];
var itemsB = [];
for (let i = 0; i < 1000; i++) {
  itemsA.push(getRandomInt(500));
  itemsB.push(getRandomInt(500));
}
itemsA.sort(function(a,b){ return a-b; });
itemsB.sort(function(a,b){ return a-b; });

function* sortedDifference(sortedIterableA, sortedIterableB) {
    let iteratorA = sortedIterableA[Symbol.iterator]();
    let iteratorB = sortedIterableB[Symbol.iterator]();
    let itemA = iteratorA.next();
    let itemB = iteratorB.next();
    while (!itemA.done) {
        if (itemB.done) {
            yield itemA.value;
            yield* iteratorA;
            return;
        }

        if (itemA.value < itemB.value) {
            yield itemA.value;
            itemA = iteratorA.next();
        } else {
            if (! (itemB.value < itemA.value)) {
                itemA = iteratorA.next();
            }
            itemB = iteratorB.next();
        }
    }
}

function difference(setA, setB) {
	let _difference = new Set(setA)
	for (let elem of setB) {
		_difference.delete(elem)
	}
	return Array.from(_difference).sort();
}

 
function getRandomInt(max) {  return Math.floor(Math.random() * max);}​var itemsA = [];var itemsB = [];for (let i = 0; i < 1000; i++) {  itemsA.push(getRandomInt(500));  itemsB.push(getRandomInt(500));}itemsA.sort(function(a,b){ return a-b; });itemsB.sort(function(a,b){ return a-b; });​function* sortedDifference(sortedIterableA, sortedIterableB) {    let iteratorA = sortedIterableA[Symbol.iterator]();    let iteratorB = sortedIterableB[Symbol.iterator]();    let itemA = iteratorA.next();    let itemB = iteratorB.next();    while (!itemA.done) {        if (itemB.done) {            yield itemA.value;            yield* iteratorA;            return;        }​        if (itemA.value < itemB.value) {            yield itemA.value;            itemA = iteratorA.next();        } else {            if (! (itemB.value < itemA.value)) {                itemA = iteratorA.next();            }            itemB = iteratorB.next();        }    }}​function difference(setA, setB) {    let _difference = new Set(setA)    for (let elem of setB) {        _difference.delete(elem)    }    return Array.from(_difference).sort();}​​

Tests:

Port from C++ STL
let itemsC = Array.from(sortedDifference(itemsA, itemsB));
let itemsC = Array.from(sortedDifference(itemsA, itemsB));
Difference algorithm from MDN Set page
let itemsC = difference(itemsA, itemsB);
let itemsC = difference(itemsA, itemsB);
Lodash _.difference
let itemsC = _.difference(itemsA, itemsB);
let itemsC = _.difference(itemsA, itemsB);
Ramda R.difference
let itemsC = R.difference(itemsA, itemsB);
let itemsC = R.difference(itemsA, itemsB);

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
Port from C++ STL
Difference algorithm from MDN Set page
Lodash _.difference
Ramda R.difference

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 3 years ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_14_6) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/14.1.2 Safari/605.1.15

Browser/OS: Safari 14 on Mac OS X 10.14.6

View result in a separate tab

Test name	Executions per second
Port from C++ STL	26032.7 Ops/sec
Difference algorithm from MDN Set page	5871.6 Ops/sec
Lodash _.difference	18179.0 Ops/sec
Ramda R.difference	3092.5 Ops/sec

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

Let's break down the benchmark and explain what's being tested.

Benchmark Definition

The benchmark is designed to compare three different approaches for finding the difference between two sorted arrays:

Port from C++ STL: This approach uses the sortedDifference function, which is a custom implementation of the algorithm used in the C++ Standard Template Library (STL).
Difference algorithm from MDN Set page: This approach uses the difference function provided by the Mozilla Developer Network (MDN) documentation for finding the difference between two sets.
Lodash _.difference: This approach uses the _difference function from the Lodash library, which is a popular utility library for JavaScript.
Ramda R.difference: This approach uses the R.difference function from the Ramda library, which is another popular functional programming library.

Options Compared

The benchmark compares the performance of these four approaches on two sorted arrays (itemsA and itemsB) generated randomly. The test measures the number of executions per second for each approach.

Pros and Cons of Each Approach

Port from C++ STL: This approach is likely to be the fastest since it uses a optimized algorithm implemented in C++. However, implementing the algorithm from scratch can be error-prone.
Difference algorithm from MDN Set page: This approach is simple and straightforward, but may not be as efficient as the other two approaches.
Lodash _.difference: This approach is convenient to use since it's a part of a popular utility library. However, using an external library can introduce overhead.
Ramda R.difference: Similar to Lodash, this approach is convenient to use but may have some overhead due to the functional programming style.

Other Considerations

The benchmark assumes that the input arrays are already sorted, which may not be the case in all scenarios.
The use of Set data structure in the MDN implementation and Lodash library may introduce performance overhead compared to a custom implementation using iterators.
Ramda's functional programming style may make the code more concise but also more difficult to optimize.

Library and Syntax

Lodash: A popular utility library for JavaScript that provides a lot of functionality out of the box. _difference is one of its functions.
Ramda: Another popular functional programming library for JavaScript that provides a different set of tools than Lodash.
No special JavaScript features or syntax are mentioned in this benchmark.

Alternatives

Other alternatives to consider when finding the difference between two sorted arrays include:

Using a custom implementation with iterators, as shown in the C++ STL example.
Using a streaming algorithm that processes the input arrays one element at a time.
Using a parallel processing approach to speed up the computation.

LLMs can make mistakes. Check important info.

Let's break down the benchmark and explain what's being tested.

**Benchmark Definition**

The benchmark is designed to compare three different approaches for finding the difference between two sorted arrays:

1. **Port from C++ STL**: This approach uses the `sortedDifference` function, which is a custom implementation of the algorithm used in the C++ Standard Template Library (STL).
2. **Difference algorithm from MDN Set page**: This approach uses the `difference` function provided by the Mozilla Developer Network (MDN) documentation for finding the difference between two sets.
3. **Lodash _.difference**: This approach uses the `_difference` function from the Lodash library, which is a popular utility library for JavaScript.
4. **Ramda R.difference**: This approach uses the `R.difference` function from the Ramda library, which is another popular functional programming library.

**Options Compared**

The benchmark compares the performance of these four approaches on two sorted arrays (`itemsA` and `itemsB`) generated randomly. The test measures the number of executions per second for each approach.

**Pros and Cons of Each Approach**

1. **Port from C++ STL**: This approach is likely to be the fastest since it uses a optimized algorithm implemented in C++. However, implementing the algorithm from scratch can be error-prone.
2. **Difference algorithm from MDN Set page**: This approach is simple and straightforward, but may not be as efficient as the other two approaches.
3. **Lodash _.difference**: This approach is convenient to use since it's a part of a popular utility library. However, using an external library can introduce overhead.
4. **Ramda R.difference**: Similar to Lodash, this approach is convenient to use but may have some overhead due to the functional programming style.

**Other Considerations**

* The benchmark assumes that the input arrays are already sorted, which may not be the case in all scenarios.
* The use of `Set` data structure in the MDN implementation and Lodash library may introduce performance overhead compared to a custom implementation using iterators.
* Ramda's functional programming style may make the code more concise but also more difficult to optimize.

**Library and Syntax**

* **Lodash**: A popular utility library for JavaScript that provides a lot of functionality out of the box. `_difference` is one of its functions.
* **Ramda**: Another popular functional programming library for JavaScript that provides a different set of tools than Lodash.
* No special JavaScript features or syntax are mentioned in this benchmark.

**Alternatives**

Other alternatives to consider when finding the difference between two sorted arrays include:

* Using a custom implementation with iterators, as shown in the C++ STL example.
* Using a streaming algorithm that processes the input arrays one element at a time.
* Using a parallel processing approach to speed up the computation.

Related benchmarks:

Compare set difference algorithms (version: 0)

Compare difference algorithms for sorted arrays

Comparing performance of: Port from C++ STL vs Difference algorithm from MDN Set page vs Lodash _.difference vs Ramda R.difference

Created: 3 years ago by: Registered User

Jump to the latest result

Port from C++ STL

Difference algorithm from MDN Set page

Lodash _.difference

Ramda R.difference

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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