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

​x
 
// Remove duplicates that occur 3 or more times in an array// keeping unique values and those with less than 3function 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));

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

 
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

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

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:

Original Duplicate Removal: This test case uses a brute-force approach, sorting the array and then iterating through it to remove duplicates.
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.
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.

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**

**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**

**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