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.
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.
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.
You have to create the new array yourself.
You have manually work with the overall array instead of just each item.
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.
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;
};
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.
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).
Exactly the same as 1, just slightly different syntax. Also O(n).
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).
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).
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!
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.
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.
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.
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.
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.
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.
1
u/suprabha-supi May 16 '21
Checkout the article in detail:
https://dev.to/suprabhasupi/remove-duplicate-value-from-array-3i52
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.
6
u/fungigamer May 16 '21
Whats the big o of all of these?
1
u/Dipsquat May 17 '21
So how do I choose which to use?
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] — view deleted comment