-2

Suppose you have a list like this:

[1, 1, 2, 2, 1, 2, 2, 2]

What's the most efficient way to remove repeated data (not duplicates) so no element appears after itself? For this example, the result should be:

[1, 2, 1, 2]

For example, this could be solved with filter or a for loop remembering the last element. But is there something more elegant? Or which option is most efficient?

for loop:

const arr = [1, 1, 2, 2, 1, 2, 2, 2];
const result = [arr[0]];
let lastElement = arr[0];
for (let i = 1, n = arr.length; i < n; ++i) {
  if (arr[i] !== lastElement) {
    lastElement = arr[i];
    result.push(lastElement);
  }
}

filter:

const result = [1, 1, 2, 2, 1, 2, 2, 2].filter((element, index, arr) => element !== arr[index - 1]);
Improve this question
8
  • 1
    what is actually your way? Commented Apr 10, 2024 at 8:39
  • 2
    i didn't dv, but an attempt is necessary. what goes wrong? Commented Apr 10, 2024 at 9:02
  • 1
    Have been using this for a long time, never knew an attempt is necessary. I can add a solution I have written here, but I was mostly interested and how other people would solve this. I feel an attempt kinda biases answers, but I can provide one. However, I think maybe I just better delete the question. Answers to question like "what is the best way to remove duplicated" helped me the most, so I thought this is interesting. Commented Apr 10, 2024 at 9:04
  • 1
    Have a go at jsperf and see for yourself - otherwise it will be an opinion you are requesting and that is against the SO guidelines Commented Apr 10, 2024 at 9:13
  • 2
    @mplungjan: I don’t think the question of the best way to do things in programming always fits into the “opinion-based” category. There are lots of objective advantages that can’t always be anticipated ahead of time. Commented Apr 10, 2024 at 9:15

3 Answers 3

Reset to default
3

Just filter with comparing with the previous item:

const result = [1, 1, 2, 2, 1, 2, 2, 2].filter((item, idx, arr) => !idx || item !== arr[idx - 1]);
console.log(result);

If you want it fast with bigger number of items, you could pre-allocate the result array: 

const data = [1, 1, 2, 2, 1, 2, 2, 2];

  const result = Array(data.length);
  let j = 1;
  let lastElement = result[0] = data[0];
  for (let i = 1, n = data.length; i < n; ++i) {
    if (data[i] !== lastElement) {
      result[j++] = lastElement = data[i];
    }
  }
  result.length = j;
  console.log(result);

And a benchmark:

` Chrome/123
--------------------------------------------------------------------------------------------------------
>                                 n=8        |      n=80       |       n=800        |       n=8000      
Alexander for+preallocate     1.23x x10m 311 | ■ 1.00x x1m 125 | ■ 1.00x   x1m 1004 | ■ 1.00x x100k 1035
Thorben Croisé (OP)         ■ 1.00x x10m 253 | ■ 1.00x x1m 125 |   1.62x x100k  163 |   1.37x  x10k  142
mplungjan for loop            1.19x x10m 302 |   1.36x x1m 170 |   1.88x x100k  189 |   1.86x  x10k  192
Alexander                     1.01x x10m 255 |   1.18x x1m 147 |   2.12x x100k  213 |   2.69x  x10k  278
--------------------------------------------------------------------------------------------------------
https://github.com/silentmantra/benchmark `


const $chunk = [1, 1, 2, 2, 1, 2, 2, 2];
const $input = [];
const data = $input;

// @benchmark mplungjan for loop
const removeRepeated = (data) => {
  const result = [];
  for (let i = 0, len = data.length; i < len; i++) {
    if (i === 0 || data[i] !== data[i - 1]) {
      result.push(data[i]);
    }
  }
  return result;
};

removeRepeated(data);

// @benchmark Alexander
data.filter((item, idx, arr) => !idx || item !== arr[idx - 1]);

// @benchmark Alexander for+preallocate
{
  const result = Array(data.length);
  let j = 1;
  let lastElement = result[0] = data[0];
  for (let i = 1, n = data.length; i < n; ++i) {
    if (data[i] !== lastElement) {
      result[j++] = lastElement = data[i];
    }
  }
  result.length = j;
  result;
}

// @benchmark Thorben Croisé (OP)
{
  const result = [data[0]];
  let lastElement = data[0];
  for (let i = 1, n = data.length; i < n; ++i) {
    if (data[i] !== lastElement) {
      lastElement = data[i];
      result.push(lastElement);
    }
  }
  result;
}

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

Please try with 10000 elements too
@mplungjan i guess the difference between 10000 and 8000 would be minimal, it's not an order magnitude
@mplungjan nope, it's total item count, it's controlled by const $chunks = [1, 10, 100, 1000] (default, so not declared), if you add 10000 to $chunks, the last benchmark will be 80000 items. it's described in the docs. the element count is a number of chunks * $chunk.length
@mplungjan trincots inplace needs special treatment. i support $clone() function to clone data before a cycle, but not sure whether it works with both inplace and pure benchmarks. it's a difficult case (mix the both approaches). otherwise it doesn't make sense to run next cycles on already mutated array
@mplungjan i've pre-allocated the result, it's even faster))
|
2

Your code seems quite optimal. Just one remark: it will fail for an empty array as input, so I would suggest adding a guard for that.

If it is acceptable to perform the action inplace, mutating the input array instead of creating a new one, you can still get some time gain:

function removeRepetitionsInplace(arr) {
    if (arr.length < 2) return;
    let k = 0;
    let lastElement = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] !== lastElement) {
            lastElement = arr[++k] = arr[i];
        }
    }
    arr.length = k + 1;
}

See performance tests at https://jsperf.app/popose/3 (added test case to mplungjan's)

enter image description here

Improve this answer

6 Comments

And if you change for (let i=1, n=data.length; i<n;i++) you save a calculation jsperf.app/popose/4
mplugjan, I believe this type of optimisation is already performed by JS engines, so there is not really a repeated calculation. See For-loop performance: storing array length in a variable
Well, SOME of the perfs in that question seem to agree with me jsben.ch/y3SpC
Also I am PRETTY sure it will be a larger difference if looping over a DOM collection
Yes, I am PRETTY sure about that as well, certainly when it is a live collection. But we're discussing arrays here.
|
1

Reduce and filter are normally slower for large arrays than for loops

JSPerf on mine, Alexander's, Trinco't and OP's code: https://jsperf.app/popose/5

Your for loop is faster than mine (but not by much)

10000 elements

enter image description here

const removeRepeated = (data) => {
  const result = [];
  for (let i = 0, len = data.length; i < len; i++) {
    if (i === 0 || data[i] !== data[i - 1]) {
      result.push(data[i]);
    }
  }
  return result;
};

// Example usage
const data = [1, 1, 2, 2, 1, 2, 2, 2];
const result = removeRepeated(data);
console.log(result); // Expected output: [1, 2, 1, 2]

Improve this answer

1 Comment

i was wrong about jsperf, since you benchmarked with 10000 items, seems the same results, but i prefer my benchmark since i can inject it here)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.