Benchmark: Array duplicate removal for duplicates exceeding `N`-number

Tests:

original duplicate removal
// Remove duplicates that occur 3 or more times in an array // keeping unique values and those with less than 3 function removeMany(arr) { const newArr = Array.from(arr).sort() let count = 0; let result = [] newArr.forEach((value, index, ar) => { count += 1; // refactored afterwards from (ar[index + 1] !== value) if (ar.lastIndexOf(value) <= index && count <= 2) { for (var i = 0; i < arr.length; i++) { if (arr[i] === value) { result.push(arr[i]) } } count = 0 } else if (ar[index + 1] !== value) { count = 0; } }); // +1 is there anyway to return a result that mimicks the original order of `numbers`? return result; // [1, 2, 2, 3, 4, 4] } const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5]; console.log(removeMany(numbers));
2-pass approach
// Remove duplicates that occur 3 or more times in an array // keeping unique values and those with less than 3 function removeMany(arr) { let countMappings = arr.reduce(function(carry, item) { if (carry[item]!== undefined) { carry[item]++; } else { carry[item] = 1; } return carry; }, {}); return arr.reduce(function(final, item) { if (countMappings[item] <3) { final.push(item); } return final; }, []); } const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5]; console.log(removeMany(numbers));
filtering
function removeMany(numbers, max) { const numberMap = numbers.reduce((map, num) => { map[num] = map[num] ? map[num] + 1 : 1; return map; }, []); return numbers.filter(num => numberMap[num] < max); } const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5]; console.log(removeMany(numbers));

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
original duplicate removal
2-pass approach
filtering

Fastest: N/A

Slowest: N/A

Latest run results:

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

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

Browser/OS: Chrome 61 on Windows

View result in a separate tab

Test name	Executions per second
original duplicate removal	35122.6 Ops/sec
2-pass approach	37007.1 Ops/sec
filtering	59029.2 Ops/sec

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

LLMs can make mistakes. Check important info.

Let's dive into the world of JavaScript microbenchmarks and explore what's being tested in this benchmark.

**Benchmark Definition**

The benchmark is designed to measure the performance of removing duplicates from an array, where duplicates exceed a certain threshold (N). The goal is to keep unique values and those with less than N occurrences.

**Test Cases**

There are three test cases:

1. **Original Duplicate Removal**: This test case uses a brute-force approach, sorting the array and then iterating through it to remove duplicates.
2. **2-Pass Approach**: This test case uses two passes: first, it counts the occurrences of each element using a Map data structure; then, it filters out elements with more than N occurrences.
3. **Filtering**: This test case uses the `filter()` method to directly filter out elements with more than N occurrences.

**Options Compared**

These three approaches are compared in terms of their performance and efficiency.

* **Brute Force (Original Duplicate Removal)**: This approach has a time complexity of O(n log n) due to sorting, making it less efficient for large arrays.
* **2-Pass Approach**: This approach has a time complexity of O(n), as it involves two passes through the array. It uses more memory than the filtering approach but is generally faster.
* **Filtering (Original Duplicate Removal)**: This approach has a time complexity of O(n) and only requires a single pass through the array.

**Pros and Cons**

Here's a brief summary of each approach:

* **Brute Force (Original Duplicate Removal)**:
	+ Pros: easy to implement, no extra data structures required.
	+ Cons: slow due to sorting, high memory usage.
* **2-Pass Approach**:
	+ Pros: faster than brute force, uses less memory than filtering.
	+ Cons: requires two passes through the array, more complex implementation.
* **Filtering (Original Duplicate Removal)**:
	+ Pros: fast, efficient use of memory.
	+ Cons: may not be as clear or intuitive as other approaches.

**Other Considerations**

When choosing an approach, consider the trade-offs between performance, readability, and maintainability. If you prioritize speed above all else, the filtering approach might be the best choice. However, if you need to implement this functionality in a production environment, the 2-pass approach or brute force approach might be more suitable due to their ease of understanding.

**Libraries and Special Features**

* The **Map** data structure is used in the 2-Pass Approach to count occurrences of each element.
* There are no notable libraries or frameworks being utilized beyond the standard JavaScript features.
* No special JavaScript features or syntax are being leveraged beyond standard array operations.

Related benchmarks:

Array duplicate removal for duplicates exceeding `N`-number (version: 0)

https://codereview.stackexchange.com/q/175067/120114

Comparing performance of: original duplicate removal vs 2-pass approach vs filtering

Created: 7 years ago by: Guest

Jump to the latest result

original duplicate removal

2-pass approach

filtering

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