r/learnjavascript • u/suprabha-supi • May 14 '21

Remove Duplicate Value from array

Post image
234 Upvotes

90% Upvoted

89 comments sorted by

20

u/slowthedataleak May 14 '21

Does this perform better than filter()?

4

u/suprabha-supi May 14 '21

It does not perform better than filter, shared one more way to remove duplicate values from an array

78

u/StoneCypher May 14 '21

no, dramatically worse.

this is actually a terrible approach, and a big part of the reason why you shouldn't learn javascript from memes by dev.to spammers on reddit

16

u/[deleted] May 14 '21

It's less performant, but not dramatic. Whether or not this is faster is an implementation detail in the runtime essentially. It is a lot more concise though, and hard to get wrong. 99/100 times i'd just import uniq / uniqBy from lodash anyway.

-26

u/StoneCypher May 14 '21

It's less performant, but not dramatic.

It's the construction and iteration of an entirely unnecessary unordered container

It's not clear how you'd make this "dramatically worse" that this isn't, other than to just make it wrong, or do something nonsensical

Yes, it's dramatic. It's large constant big o lg n twice plus small constant big o n lg n for literally no reason.

.

Whether or not this is faster is an implementation detail in the runtime essentially

this isn't even close to correct

.

It is a lot more concise

Not than the good answer

.

99/100 times i'd just import uniq / uniqBy from lodash anyway.

Wow, please don't give advice anymore

I've had to update my libraries 11 times this week because people like you imported lodash or underscore for no good reason, and they're full of bugs and security problems

It's so hard to just have decent testing or doc generation because of things like this :(

This is the mindset that left a serious chunk of the internet broken over padLeft

13

u/[deleted] May 14 '21

this isn't even close to correct

It's very correct, i welcome you prove otherwise.

Not than the good answer

Please provide the good answer then

Wow, please don't give advice anymoreI've had to update my libraries 11 times this week because people like you imported lodash or underscore for no good reason, and they're full of bugs and security problems

I don't think that's correct. If you honestly believe you write fewer bugs and more secure code than lodash, please provide some kind of proof, because you're likely wrong.

Yes, it's dramatic.

No it's not dramatic.

I did a jsbench in chrome test at various array sizes, 10, 100, 1000, 10_000, 100_000, ..., on three different approaches - Set, filter + indexOf, filter + object.

For small arrays filter + indexOf is the fastest. For very large arrays filter + object is fastest. For the middle Set / filter + object are not significantly different.

And of course the filter versions could be written with a loop and be faster.Overall though a pointless optimization unless perf testing your app reveals that you need it. Lodash takes size of array into account and chooses approach based on that, so you get the optimization for free.

-11

u/StoneCypher May 14 '21

Whether or not this is faster is an implementation detail in the runtime essentially

this isn't even close to correct

It's very correct, i welcome you prove otherwise.

What's there to disprove? You just said randomly "this is an implementation detail." You didn't make a technical claim.

This is like saying "node.js is angry which is an implementation detail" and when someone says that doesn't make sense saying "prove me wrong"

No, dear heart. You prove yourself right. Other people don't prove you wrong.

"An implementation detail" means that something is a decision for the underlying machine, that is out of the developer's hands.

You just said "the shape of the code that the developer chooses to write is not up to the developer."

That's absolute nonsense.

Every part of that code is hard-defined by the specification. None of it is an implementation detail.

That phrase has a meaning. You're hard wrong.

 

Please provide the good answer then

There's tons of them. I prefer one that you probably won't prefer, because this should be a tiny library function tested and put away in some module somewhere, and even though it's a one-liner nobody will ever see, you're crying out for "simplicity"

The function can't be well written; the name is ambiguous. You need to provide a stub that is clear about what is being done with holes, undefined, and symbols.

Holes are a problem because the various implementations mostly lose them. However, under most interpretations of the ECMA-262 concept of an lvalue, they need to be kept.

Symbols are a problem because the concept of uniqueness is a conceptual error around them in general. Two copies of the same symbol are not equal. equivalence is broken for them on purpose, and uniqueness is conceptually defined in terms of equivalence.

undefined is a problem

.

No it's not dramatic. [...] I did a jsbench

I see that you:

  • didn't give numbers

  • didn't show your test code

  • didn't share the share-able bench in case there were mistakes

  • didn't cover correctness topics

  • didn't specify whether your implementations gather the same results

  • said there were differences in speed but also argued against my saying there were differences in speed

  • said "the one in the middle isn't too far from one side" which is obviously going to be the case because the one side is the other good approach

  • compared several tiny sizes and referred to one of them as large

  • used a benchmarker that can't see micro-timing at all

  • ignored the o claim

Compelling stuff

Wanna show us this bench?

I benched it too and it turns out the solution I don't like took infinity hours and the solution I do like gave me a pony

 

For very large arrays

100k is not a very large array. Lawdy.

Node authors regularly deal with two or three orders of magnitude larger than this.

The US map on d3 has more than 50x this many SVG tags. SVG tags are not simple.

 

I don't think that's correct. If you honestly believe you write fewer bugs and more secure code than lodash, please provide some kind of proof, because you're likely wrong.

I didn't say anything like this.

What I did say is "don't involve a specific library that's had three criticals in the last two weeks to get away from a simple one-liner."

You know, the three one-liners you claim to test in a jsbench later?

It's very easy to avoid lodash in favor of the standard library.

I didn't say my code has fewer bugs. I said the standard library does.

I don't need to prove that. It's tautological. Anything written using the standard library, such as lodash, already includes every bug in the standard library.

Do I believe that chrome has fewer security bugs than lodash, which had three criticals in the last week?

Emphatically yes.

You want me to accept a benchmark you wrote in 15 minutes, but also you're skeptical that Chrome has fewer security bugs than lodash, one of the least secure libraries on NPM 😂

 

Overall though a pointless optimization

It's annoying when novices respond to "don't do it that way, it's bad for a bunch of reasons including correctness and performance" with "YoU'rE jUsT mAkInG uNnEcEsSaRy OpTiMiZaTiOnS"

Correctness is not an optimization

lodash does what I believe to be the wrongest things with uniqueness around holes, and around Symbols (I do agree with what it does around undefined)

I doubt you even thought to check

 

Lodash takes

Lodash has had three unrelated security vulnerabilities marked critical or worse in the last two weeks

I cannot take seriously the opinions of someone who keeps pushing for one-liners to be replaced with it, after they were told that once already

If you're arguing against maintenance, arguing for things with a history of grim security problems is arguing against yourself

12

u/[deleted] May 14 '21

Please be more concise, I have no interest in countering a proof by verbosity where you've introduced tons of new arguments that had nothing to do with the original post or discussion and contradict your own self many times.

-11

u/StoneCypher May 14 '21

A third time, I'm requesting that you provide the perf you claim to have written

You're the one who brought lodash up, not the original post or discussion

Now that I'm pointing out why adding lodash is a security problem, which is a hard fact but which you refuse to accept, you're babbling on about how everything has to be scoped to the original post or original discussion

Show us your perf that you're trying to stand on as evidence. I'm starting to think it isn't real, because I wrote one that got really different results

1

u/[deleted] May 14 '21 edited May 14 '21

Lodash's vulnerabilities only matter in relation to the code that you write that is allegedly better, since you are advocating to write it yourself rather than let someone else do so.

You yourself said that this is a tiny library function, a one liner, and that you could write just as concisely as [...new Set(arr)], and that it'll be dramatically more performant than the OP on an array with millions of items. But you refuse to do so for some reason. Can't be time since you have the time to repeatedly write large walls of text.

Furthermore I've looked through Lodash CVEs and I see none relating to function in question. The majority of them seem to be prototype pollution from functions that merge objects, which is outside of the scope of deduping an array. So it was a moot point to begin with designed to distract from the actual point.

Finally, since you allegedly have the ability to write code that is faster, safer, more maintainable, and more concise than lodash - why are you so selfish as to keep this code to yourself? Publish it and let the community benefit.

-3

u/StoneCypher May 14 '21

A fourth time, I'm requesting that you provide the perf you claim to have written

→ More replies (0)

4

u/[deleted] May 14 '21

This is the mindset that left a serious chunk of the internet broken over padLeft

This is also completely incorrect. People using packages was not the root cause of that problem. npm allowing packages to be removed at will was certainly a problem. people counting on npm to be always up was certainly a problem. javascript having a pathetic standard library was mainly to blame.

You weren't even right about a single thing in that massive wall of text which is pretty impressive.

1

u/StoneCypher May 14 '21

This is also completely incorrect. People using packages was not the root cause of that problem

It was literally 100% of the problem. It's a subtraction and a .repeat

 

npm allowing packages to be removed at will was certainly a problem.

This is required both by security common sense basics and by copyright law.

 

javascript having a pathetic standard library was mainly to blame.

It's not Javascript's fault that you don't know how to do this

By the way, Javascript does have this in the standard library directly, it's just called .padStart

Yes, that was already in Javascript before the package you're trying to make excuses for was added

Yes, they could have used a shim or a sham

 

You weren't even right about a single thing in that massive wall of text which is pretty impressive.

Sure thing, Jim

Sorry you don't like evidence or questions you can't answer

 

Can we see your mystery perf that you claimed to write? It's not getting the same results I did, and I'd like to see why

2

u/[deleted] May 15 '21 edited Aug 31 '25

[removed] — view removed comment

1

u/StoneCypher May 15 '21

you've quite badly misunderstood the costs

list(set(arr)) means:

  1. Converting the array to a set

    1. Iterate the array

    2. For each array item, make an o(lg n) probe into the new set at increasing by-size cost to determine whether to insert

    3. In most languages, including python (not defined in JS but including both popular JSVMs,) you may need a red-black rebalance after insert, which is also amort o(lg n)

  2. Convert the set to a list

    1. Iterate the set's tree

    2. Allocate and enjoin a ton of list items

  3. Present the list

No, filter isn't o(n^2) in python, or indeed in any language that can't optimize some of the work out (like maybe Haskell could but I doubt it,) and it's not clear why you think that it is. Python doesn't define the complexity of filter, but I've never seen it be anything other than linear over arrays in any language in my entire life (with the notable exception of Visual Basic, which uses the word "array" for something that isn't actually an array.)

You can't actually do the uniqueness thing faster than o(lg lg n), and getting it down that far takes a fairly large amount of knowledge about the data. How did you think you were getting a presence test in linear time? That isn't possible

Can you help me understand why you think filter is o(n^2) over a direct iterable? That doesn't make any sense. It's:

  1. Allocate a new matching-sized container

  2. Iterate the base array o(n) a single time, linearly, in order

    1. For each element, el[i] = function(source[i])

  3. Present the container

Where does the second order n come from? It's o(up-to-n) + o(n), one for the allocate, one for the traversal

1

u/[deleted] May 15 '21 edited Aug 31 '25

[removed] — view removed comment

0

u/StoneCypher May 15 '21

wow you're really going to try to line by line?

The "n not in deduped" is a linear search of deduped.

this is the second n

 

and getting it down that far takes a fairly large amount of knowledge about the data. How did you think you were getting a presence test in linear time? That isn't possible

Please check out the Hash Map chapter of Introduction to Algorithms by CLRS.

Yeah, that just moves the cost from test to insert

Look, if you're going to talk down to people this way, don't ask for explanations from them

 

⁠Present the container

O(n)

😂 no, returning a pointer isn't o(n)

 

What details are you hiding in function?

You're trying to make commentary about container conversion costs by pretending that there's a conversion function?

i'm sorry, but this really isn't worth my time

0

u/[deleted] May 15 '21

[removed] — view removed comment

0

u/StoneCypher May 15 '21

This isn't worth my time.

You're ignoring clearly spelled out mistakes already given to you.

 

What should be worth your time is researching hash maps.

Nobody asked for your advice.

I realize you're trying to win, but there's no fight here. You asked me to explain myself, I did, you tried to argue, and I walked away.

Imagine telling someone returning a container was o(n), not admitting the mistake when it's pointed out, and continuing to try to give someone else a reading list 😂

"No but when you said converting containers, did you mean printing them on screen?"

🤣

Good day.

→ More replies (0)

2

u/amoliski May 14 '21

It's only terrible if you care about performance. If you do the operation a single time in response to a user clicking a button, who cares if it takes 0.01s longer to complete?

It's a bit more readable than the faster filter method, and that by itself has some value.

1

u/Nonethewiserer May 15 '21

Also shouldn't include all the extra emojis. 2 would suffice. Or, you know, no emojis.

2

u/47milliondollars May 14 '21

Would filter even work? Or do you have to use reduce to check if the value exists yet in an accumulator?

7

u/space_scarab May 14 '21 
arr.filter((el, index) => {
    return arr.indexOf(el) === index;
});

11

u/47milliondollars May 14 '21

Oh holy shit, never thought about this. Looks like the indexOf is finding the first match, and so the filter drops anything of the same value that isn't at the first detected index? Pretty neat.

10

u/[deleted] May 14 '21 edited May 14 '21 
arr.filter((el, index) => arr.indexOf(el) === index);

Works too!

(but worth saying that shorthand isn't always the most readable and shouldn't be your default approach!)

3

u/[deleted] May 15 '21

Honestly that shorthand is way easier to parse - for me at least

2

u/StoneCypher May 14 '21

is there any difference there other than switching to an arrow?

0

u/[deleted] May 14 '21

[deleted]

1

u/grooomps May 15 '21

So a function without a fat arrow doesn't have explicit return?

-5

u/StoneCypher May 14 '21

Thanks, I didn't ask what an arrow was.

What I asked was "is that the only change you made"

Notably, you shouldn't have that "auto-corrected," because arrows and standard functions differ in how they bind this. That should be hand-corrected. In many cases in practice, this will damage transitional-style classes.

7

u/47milliondollars May 14 '21

Dude, way to be a jerk to someone who kindly took the time to respond to that question (why would they think you were asking if they made any other changes when you're looking right at the 1-3 lines of code?). Also, their response was perfectly accurate for this code example we are looking at, the context of "this" is totally irrelevant here.

-3

u/StoneCypher May 14 '21

(why would they think you were asking if they made any other changes when you're looking right at the 1-3 lines of code?).

The point of the original question was to ask why this person is holding up a non-change as a change. I was trying to make sure I wasn't overlooking something else more substantive.

 

Also, their response was perfectly accurate for this code example we are looking at, the context of "this" is totally irrelevant here.

Yes, I'm ... kind of relying on that.

Literally the only difference between the two pieces of code is something that is totally irrelevant here.

It's like taking out the newlines and "proposing it as an alternative." Literally.

4

u/amoliski May 14 '21

Doesn't hurt to show both forms so if someone isn't familiar with them they can see they are similar.

→ More replies (0)

1

u/space_scarab May 14 '21

ah, yes, cleaner. thanks!

3

u/learning_account_01 May 14 '21

Man. I wish i can think like this. How do you do ? I was stuck at this smilar knida problem (find if array contains duplicate value or not and just return true or false.) and it never clicked me.

4

u/StoneCypher May 14 '21

Man. I wish i can think like this. How do you do

it's the accepted answer from the first result on googling "javascript unique"

https://stackoverflow.com/a/14438954/763127

it's pretty standard in the javascript community

4

u/learning_account_01 May 14 '21

Oh that shows how noob I am. I have lot to learn indeed. Thanks.

3

u/amoliski May 14 '21

Even without SO giving you that answer, it just takes practice and repetition to figure these things out on your own.

If you use indexOf enough times, you eventually learn (and reinforce in your brain) that indexOf returns the first match.

If you use filter enough, the mechanics become second nature.

Once you have both ideas cemented through practice, the connections just start to happen for you.

2

u/47milliondollars May 14 '21

Don't worry fren, a huge part of coding is googling stuff, you're not expected to think up this shit on your own :)

2

u/learning_account_01 May 14 '21

you're not expected to think up this shit on your own

Well thank god otherwise I can't even dare to dream of becoming a programmer some day.

1

u/Parkreiner May 15 '21

One comment and a question.

First, this approach will not work for non-primitive values. If you're dealing with an array of arrays or an array of objects or even an array of functions, it'll just compare their references. So if the array has two objects that have the same contents but were declared separately, you'll still get values that look like duplicates. That might be just fine for some applications, but if it's not, you'll have to do a deeper comparison.

Second, is this actually better? This isn't just rhetorical; I'm actually asking. Filtering is O(n), but so is indexOf, so since the indexOf call is inside the filter, the whole operation is O(n2). Meanwhile, generating a set is also O(n), as is destructing it into an array. But since they're done back-to-back and not inside each other, it's O(2n). I know that the highest factor doesn't always tell the whole story, but are there times when the set approach would perform better?

0

u/[deleted] May 14 '21

[deleted]

2

u/[deleted] May 14 '21 edited May 14 '21

emojis.concat(emojis);

this doesn't modify the original array and you aren't saving the result...

You should also use different files to run each algo just so it's isolated and the second one isn't benefiting from JIT optimization from the first.

Another thing, you don't want to include the time to generate the array in your measurement since you're really interested in the deduping.

I did it with the modifications suggested and Set version is much faster than indexOf as the array gets larger, which isn't surprising.

Here's output for the 10_000 loop

~/perf
❯ node -v
v15.14.0

~/perf
❯ time node indexOf.js
Took 3.4395 milliseconds to generate:
node indexOf.js  1.14s user 0.89s system 110% cpu 1.849 total

~/perf
❯ time node indexOf.js
Took 3.4735 milliseconds to generate:
node indexOf.js  1.15s user 0.91s system 110% cpu 1.862 total

~/perf
❯ time node indexOf.js
Took 3.4432 milliseconds to generate:
node indexOf.js  1.15s user 0.92s system 111% cpu 1.857 total

~/perf
❯ time node set.js
Took 0.9747 milliseconds to generate:
node set.js  1.18s user 0.90s system 111% cpu 1.869 total

~/perf
❯ time node set.js
Took 0.8821 milliseconds to generate:
node set.js  1.20s user 0.91s system 111% cpu 1.890 total

~/perf
❯ time node set.js
Took 0.9954 milliseconds to generate:
node set.js  1.20s user 0.90s system 111% cpu 1.886 total

1

u/StoneCypher May 14 '21

ten thousand is far too small of a sample. you're more measuring context switches than anything

please bump that up to at least 1 million. at your current setup that'll still take less than 3 seconds to run.

i wouldn't trust a sample at 1 million either

2

u/devbrk May 14 '21

So how really does it work? I mean I assume that we can’t use it in an interview.

2

u/suprabha-supi May 14 '21

What I have seen, interviews always ask multiple ways.

In those we have different ways:

  1. Using Set

  2. Array.from

  3. filter

  4. reduce

  5. forEach

1

u/suprabha-supi May 14 '21

I have added few ways which we can use to remove duplicate values from an array:

https://blog.suprabha.me/57-remove-duplicate-from-array

3

u/Budget_Instruction49 May 14 '21

'Set ' a state ? or its just set ?

2

u/slowthedataleak May 14 '21

Not sure that I understand your question but what's happening here is the array is being duplicated into a Set type.

5

u/[deleted] May 14 '21

Not sure that I understand your question

probably brain poisoned by trying to learn React and JS at the same time.

4

u/StoneCypher May 14 '21

He's asking whether the word "set" is being used to mean assign or whether it's being used to refer to the container type

He's from India, and English isn't his first language. Homophones can be confusing

2

u/[deleted] May 14 '21

Not sure why you got downvoted but then again this is reddit

2

u/Budget_Instruction49 May 15 '21

oh. are you a hacker ? or reddit shows my location ? or you read my comments ? i am scared

2

u/StoneCypher May 15 '21

What? You said so

You're scared because someone read your comments? ಠ_ಠ

2

u/Budget_Instruction49 May 15 '21

chill mate. "i am scared" is a famous meme. i was joking. maybe visit r/memes too

2

u/StoneCypher May 15 '21

"i am scared" is a famous meme.

your delivery is not great

2

u/Budget_Instruction49 May 15 '21

wait a minute ... who are you ?

1

u/StoneCypher May 15 '21

the bored guy who is going to stop responding because these are not:

  1. memes

  2. funny

2

u/Budget_Instruction49 May 15 '21

is it possible to learn this power ?

3

u/[deleted] May 15 '21

Everyone arguing in the comments about performance and I'm just here like "damn this presentation is obnoxious".

Seriously - array of emojis, super bright background colors, obnoxious self-promotion. Jesus.

Regardless of the performance or accuracy, this is just gross.

1

u/Parkreiner May 15 '21

I mean, I think emojis can be fun, and bold colors are fine (though the blue-yellow gradient is really ugly and doesn't have enough color stops), but yeah, the image was clearly made more for self-promotion than to be informative. The first thing that's going to draw your attention is the green circle right in the middle of the image, rather than the code itself.

2

u/godsknowledge May 14 '21

I had to use that at work recently. Fetched data from a list in SharePoint and put them into an array. Since they array contained duplicates, I only had to create a Map to get rid of the duplicates.

Parsed it into JSON and voila, you can easily integrate it into other applications like Nintex Forms.

1

u/CornPop747 May 15 '21

Please don't do this in an interview ;)

1

u/karanisverma May 14 '21

Very well explained 👍🏻