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>

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

Tests:

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

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

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

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