r/learnjavascript • • May 16 '21

Multiple ways to remove duplicate value from an array

Post image
198 Upvotes

28 comments sorted by

43

u/haytherecharlie May 16 '21

If you're reading this, please remember that code performance matters.
These methods may look pretty, however the last two have exponential O(n²) time complexity - which doesn't scale well.

This problem can be solved using linear O(n) time and space.

5

u/muh2k4 May 16 '21

I also think the first two are more readable in my opinion

2

u/suprabha-supi May 16 '21

I mostly use Set and filter 😅

16

u/Cosmologicon May 16 '21

please remember that code performance matters

This is good advice.

Once you've learned that, you're ready for the next level of advice: performance doesn't always matter, and readability always matters. Avoid premature optimization, and go with whichever solution is most readable until you know it's an issue, just be aware of the performance implications.

It's perfectly fine to use O(n2) algorithms when less readable O(n) ones exist, if you know it's not an issue. I do it all the time. If you're validating a username that's been restricted to 16 characters, for instance, you don't need to worry about what happens when n = 10000.

Having said that, in this case the most readabale one is also fast, so it's win/win.

1

u/LordEmryys May 17 '21

Small correction: O(n2) is quadratic time complexity

8

u/jaredcheeda May 16 '21

A junior is not understanding how to use reduce.

A mid is knowing how to use reduce.

A senior is knowing never to use reduce.

5

u/delventhalz May 16 '21

Lol. Poor reduce. I loved it so much when I first started to get good with array methods.

6

u/FerJep May 16 '21

What's the problem with reduce? Is it bad?

5

u/delventhalz May 16 '21 edited May 16 '21

It’s not bad so much that it doesn’t really serve any purpose.

Broadly speaking, array methods are awesome because they are “declarative”. They clearly state what it is they do and abstract away a lot of the fiddly details. What does filter do? It filters an array. How do you build the new filtered array? You don’t. filter does that for you. Clear purpose. Super useful. Great way to simplify your code.

So what does reduce do. It “reduces” an array into an “accumulator” value . . . oooookay. The fact that it is so hard to explain isn’t a dealbreaker necessarily. Basically it means something like calculating a sum:

const sum = nums.reduce((sum, num) => sum + num);

The sum example shows reduce in the best possible light. Other examples tend to get really complicated, both in terms of the readability of the code and what the code is actually doing under the hood. Take a look at OP’s example.

  1. You have to create the new array yourself.

  2. You have manually work with the overall array instead of just each item.

  3. You create a new array every time you make a modification.

That’s. A lot. None of this is true for filter. Now imagine if we rewrote the reduce example with just a vanilla loop.

const uniq = (arr) => {
  const acc = [];

  for (cont curr of arr) {
    if (!acc.includes(curr)) {
      acc.push(curr);
    }
  }

  return acc;
};

Sure you can use reduce (along with other tricks like ... spread) to cram it all into one line, but is that actually any simpler or more clear than this manual approach? I would argue it’s a lateral move at best.

I will use reduce sometimes with primitive accumulators like in the sum example. But that’s actually a pretty rare scenario. And when it comes to objects/arrays, I either use a more appropriate array method (if available), or write it out manually in a helper function.

1

u/jaredcheeda May 17 '21

you should avoid abbreviating. ultimately your code is going to be uglified anyways, so there's really no benefit in reducing the number of characters. plus you can typically auto-complete with tab anyways.

Some people may misunderstand, or just auto-complete the words with their brain in weird ways. I'm sure this isn't your intention:

const uniqueness = (arrogance) => {
  const accordingly = [];

  for (const currency of arrogance) {
    if (!accordingly.includes(currency)) {
      accordingly.push(currency);
    }
  }

  return accordingly;
};

0

u/delventhalz May 17 '21

I generally agree about abbreviations, but I used acc and curr here to match OP's example, and uniq is a fairly common name for this function. It's not an abbreviation so much as jargon.

2

u/jaredcheeda May 17 '21

Here's a long discussion on why I, and many others with experience, find the usage of reduce to be something to avoid in almost all cases.

If there was a "no-reduce" linting rule, I'd be tempted to enable it.

6

u/fungigamer May 16 '21

Whats the big o of all of these?

12

u/delventhalz May 16 '21 edited May 16 '21
  1. You iterate through the array to create the Set, and then you iterate through the Set to create the new array. That's two loops, so 2n, but we only care about the exponent, so we call it O(n).

  2. Exactly the same as 1, just slightly different syntax. Also O(n).

  3. Every time you use indexOf you have to loop through the array. Since filter is itself looping through the array, you need to loop for each item in the array. That's a loop nested inside another loop. Classic O(n^2).

  4. First you have to loop for the includes. Then assuming you don't find the item, you have to loop in order to create the new array. Both of these are within the reduce loop, so that's (2n)^2. Once again we only care about the exponent though, so it is also O(n^2).

2

u/Cosmologicon May 16 '21

Technically, 1 and 2 are O(n e), 3 is O(n2 s), and 4 in O(n2 e), where O(e) is the time to compare two objects in the array as equal (==), and O(s) is the time to compare two objects as strictly equal (===).

For strings of length L, then O(e) = O(s) = O(L), but for other objects it's possible that O(s) < O(e).

I think it's at least important to not just assume all strings are length O(1) in big-O analysis, so I would say O(n L) and O(n2 L) in this case.

At least that's my understanding reading the docs. Correct me if I'm wrong!

4

u/delventhalz May 16 '21

I don't think you are incorrect, but this is more technical than I think most Big-O discussions need to get. I like Big-O particularly as a tool to generalize details. For the most part, I just want to sort algorithms into big buckets: fast, slow, very slow. It would take a very weird edge case for the speed difference between strict equality and loose equality to be at all noticeable.

1

u/Cosmologicon May 16 '21

Yeah I agree with that. That's a good perspective on it.

I do think it's important to include the O(L) term. Too many people think that it's O(1) to check whether a string of length L is within a hash set, because they've just memorized that "hash set means O(1)". I just included the equality part to say exactly where it was coming from.

2

u/delventhalz May 16 '21

Perhaps. That's still only going to make a difference in some edge cases. In this case, is it relevant that we may have to handle longer strings when comparing includes to indexOf to the Set constructor? Seems unlikely.

3

u/notAnotherJSDev May 16 '21

Insignificant for small (most) datasets

6

u/delventhalz May 16 '21

That is not how big o works.

-2

u/notAnotherJSDev May 16 '21

While that’s true, performance for something like this absolutely does not matter for small data sets.

8

u/delventhalz May 16 '21

The point of Big-O is to focus you away from the sort of minor optimizations that rarely offer much pay off. The difference between O(n^2) and O(n) is significant and will likely become noticeable pretty quickly.

But you are right that if you know your data set will only ever be a few dozen items long, you can get away with pretty much anything.

1

u/Dipsquat May 17 '21

So how do I choose which to use?

1

u/SoBoredAtWork May 17 '21

Use the first one. #2 is okay too, which ever you prefer. The rest are shit (slower, uglier).

1

u/Diamond-Husky-Poop May 17 '21

If I need an array that has no duplicates I am going to just create a new Set then convert that set to an array. Because a Set can not have duplicates.

Now if the question is taking an already made array and removing the duplicates.. uhh I am stuck.

1

u/-vikram- May 17 '21

After some extensive talks in code reviews the one thing that i have learnt is never to use reduce. They don't like it at all

0

u/[deleted] May 16 '21

[deleted]

2

u/Division2226 May 16 '21

Same way probably, maybe stringify the object first?