For each array item, make an o(lg n) probe into the new set at increasing by-size cost to determine whether to insert
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)
Convert the set to a list
Iterate the set's tree
Allocate and enjoin a ton of list items
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:
Allocate a new matching-sized container
Iterate the base array o(n) a single time, linearly, in order
For each element, el[i] = function(source[i])
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
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?
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?"
1
u/StoneCypher May 15 '21
you've quite badly misunderstood the costs
list(set(arr))means:Converting the array to a set
Iterate the array
For each array item, make an
o(lg n)probe into the new set at increasing by-size cost to determine whether to insertIn 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)Convert the set to a list
Iterate the set's tree
Allocate and enjoin a ton of list items
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 possibleCan you help me understand why you think filter is
o(n^2)over a direct iterable? That doesn't make any sense. It's:Allocate a new matching-sized container
Iterate the base array
o(n)a single time, linearly, in orderFor each element,
el[i] = function(source[i])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