r/learnjavascript • • May 14 '21

Remove Duplicate Value from array

Post image
234 Upvotes

89 comments sorted by

View all comments

Show parent comments

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

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)