Two bins speedy solution for Non-unique Elements by veky - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Two bins solution in Speedy category for Non-unique Elements by veky

def checkio(sequence):
    bins = seen, nonunique = set(), set()
    for number in sequence: bins[number in seen].add(number)
    return [number for number in sequence if number in nonunique]

Sept. 24, 2015

Comments:

dalluca on March 8, 2016, 12:36 p.m.
I really like this solution!!

veky on March 8, 2016, 7:20 p.m.
You could have given it a few more thumbs, then. :-P :-)

Flying_Eye on May 11, 2016, 8:09 a.m.
It seems this is the fastest solution. The second fastest I could find is the solution with Counter. I wonder why is this solution so underrated. It should be on top.

veky on May 11, 2016, 11:38 a.m.
Probably because it was written much later. Don't trust voting too much, people usually just look at first few top solutions. :-/

DerekSharp on July 26, 2016, 10:53 p.m.
I ran some tests and this code is even faster than the best one I came up with. They seem very similar. Can you explain why yours is quite a bit faster?

veky on July 27, 2016, 8:29 a.m.
Branches are expensive: as in native code (where branch prediction can really mean a lot, as <a href="http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array/11227902#11227902">this legendary SO answer</a> shows), so in bytecode (since Python VM is stack-based, it has to do unnecessary pushes and pops for return values that are just Nones in your case; plus, of course, often branches in bytecode are almost literally translated to branches in machine code, and locality is even worse since those are <a href="http://www.slideshare.net/akaptur/a-1500-line-switch-statement-powers-your-python-allison-kaptur-con-2014">huge chasms</a> between branches). Attribute access is much faster, and item access even more (since you avoid hash computation and bucket chasing). Probably the slowest part in my inner loop is looking up the 'add' attribute over and over again. That could also be helped by factoring them out <pre class='brush: python'>adds = seen.add, nonunique.add for number in sequence: adds[number in seen](number) </pre> BUT! please don't obsess about performance microoptimizations. I know it's sexy and an attractive nuisance, but Python is not about it, Python is about explaining algorithms. Do obsess about algorithmic complexity if you wish, but until you write at least a thousand scripts, O(n) is good enough.

santagada on Sept. 19, 2016, 10:18 a.m.
Actually this is slower than this: <pre class='brush: python'>first = set() repeated = set() for e in data: if e in first: repeated.add(e) else: first.add(e) return [e for e in data if e in repeated] </pre> so although branch has cost, its much cheaper than looking up a variable and then getting an item in it. also there is no advantage in the multiple initialization or to have code on the same line of a for

veky on Sept. 20, 2016, 9:46 a.m.
This is weird. @DerekSharp <a href="https://py.checkio.org/mission/non-unique-elements/publications/DerekSharp/python-3/first/">here</a> does practically the same thing, and says it's slower than mine. I think one of you two is measuring wrong. :-) Anyway, what about <pre class='brush: python'>def checkio(sequence): bins = seen, nonunique = set(), set() adds = seen.add, nonunique.add for number in sequence: adds[number in seen](number) return [number for number in sequence if number in nonunique] </pre> ?

DerekSharp on Sept. 20, 2016, 10:54 p.m.
I just re ran both our codes vs santagada. I believe he is mistaken. His does not even appear to be faster than my code. I only timed 100 loops of pretty large code (100,000 entries) but the results were. VEKY - .377 sec DEREK - .551 sec SANTAGADA - .689 sec Veky's code is in fact almost twice as fast as Santagada's, and a little slower than mine. And Veky's new code from above appears to run as fast as his initial code. Sometimes a hair slower, sometimes a hair faster, but once again faster than me hehe. :p

veky on Sept. 21, 2016, 6:41 a.m.
<blockquote> And Veky’s new code from above appears to run as fast as his initial code. Sometimes a hair slower, sometimes a hair faster, but once again faster than me hehe. :p </blockquote> I assume you've tested that on 3.6b1? That would mean that cacheing of method lookups works nicely (I heard something about trying to put it in 3.6.)

Merzix on May 30, 2017, 11:13 a.m.
For my tests (best time for 10 attempts): * DEREK 1.125 sec * SANTAGADA 1.165 sec * VEKYold 0.863 sec * VEKYlast 1.201 sec * ilhanmercan 1.301 sec * my 0.575 sec (memory using x2)

Merzix on May 31, 2017, 8:16 a.m.
I forgot <a href="http://rextester.com/TBPP2311">test code</a>

Merzix on May 31, 2017, 9:02 a.m.
My mistake in tests of my func! <ul> <li>DEREK 0.67 sec</li> <li>SANTAGADA 0.68 sec</li> <li>VEKY_old 0.54 sec</li> <li>VEKY_last 0.73 sec</li> <li>ilhanmercan 0.76 sec</li> <li>my2 0.48 sec</li> <li>my3 0.74 sec (memory using x2)</li> </ul> Sorry about this. P.S. But VEKY`s one-line code is better then this (<a href="http://rextester.com/NSGU22582">test code</a>)

DiZ on Oct. 4, 2016, 8:40 a.m.
It has been quite a while you posted this solution, and I never saw it until now. No counter, no branch, I like it! :D

veky on Oct. 4, 2016, 9:06 a.m.
Well, sets are kinda saturated Counters (capped at 1). :-) And indexing a two-tuple by a bool is kinda branch. :-) Yes, visibility of new solutions is abysmal. At least people see my solutions because they are mine, but others don't have such luxury. :-o

DiZ on Oct. 4, 2016, 11:46 a.m.
Quite true, plus the fact I didn't come here so often (because you know... no new content). But at least, newcomers can study your solutions without waiting a long time, don't worry for others :')

veky on Oct. 5, 2016, 6:48 a.m.
There is a lot of new content. Not new missions, but new solutions by new users. :-)

pietroppeter on Dec. 3, 2016, 2:51 p.m.
It took me a while to understand the logic of the chained assignment of line 2. When I did and read on to line 3, I laughed like after a good punchline! Apart from being an excellent solution, it is a very nice illustration of mutability (of the set) vs immutability (of the tuple). You end up with something like a tuple on named objects that you can access separately. Does this technique have some kind of name?

veky on Dec. 3, 2016, 2:56 p.m.
<blockquote> Does this technique have some kind of name? </blockquote> Yes, it's called Object oriented programming. :-D Every attribute stands for itself, yet together they are also meaningful. :-)

dangyi1115 on Aug. 9, 2017, 2:40 a.m.
bins[number in seen].add(number) what a clever idea

veky on Aug. 9, 2017, 7:54 a.m.
You can also <pre class='brush: python'>(nonunique if number in seen else seen).add(number) </pre> if that's too clever for you. ;-)

ljpGBL on Sept. 22, 2018, 6 a.m.
This runs way much faster than mines... A stupid question from the newbie: how does this <pre class='brush: python'>bins[number in seen] </pre> works? ok, I found myself lollll

bsquare on Sept. 18, 2019, 9:15 a.m.
I like this way of defining index :)

mlahor on Oct. 24, 2019, 10:40 a.m.
So, I see bins[1] is the same as nonunique and bins[0] as seen. How exactly did we get to that? I see people mentioning a tuple but then wouldn't it be bins = (seen, nonunique) ? And the double assignment, can we really do it like this, I've never yet seen it like that...

veky on Oct. 24, 2019, 11:58 a.m.
Parentheses don't make a tuple, they are just for grouping (try `>>> 2, 5` in Python shell). And `=` has lower priority than `,`. You don't need to write those parentheses for the same reason you don't need to write them in `2 + (3*4)`. :-) I'm quite sure you've seen `x = y = 0`, haven't you? This is the same. You can name a single thing with multiple names in one command.

List but not the least

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!