last day (15 days later) » 

02:04
6
A: Finding the odd number out in an array

TurnAn easier (and more efficient) way of doing this is with a Counter object: from collections import Counter singlet = Counter(nums).most_common()[-1][0] The Counter object will create a dictionary-like object with the keys being the values in your list and the values being the number of time...

@MosesKoledoye My reading of the problem as stated by the OP was that all numbers would be duplicated except for one of which there would be a single instance.
@StefanPochmann Thanks, I missed a set of parentheses. Fixed now.
@Shannon Sorry, I had a typo. Fixed now. I used the term 'singlet' just to mean the value that only appears a single time. It isn't a technical term, it's an abuse of English in an attempt to be cute.
I think it would be good if you said how efficient it is.
@StefanPochmann Yes, you're right. Added. Thanks.
Looks good, though something interesting is missing: That the sorting is O(n).
@StefanPochmann Sorry, can you explain what you mean? I mentioned hte sorting is likely O(n log n). You think it would be O(n)? Or are you referring to some other sort that I missed?
02:04
Yes, that's the one I mean, and yes, it's O(n).
How can that be? Does the counter keep some meta information as it constructs the dict to make it faster than sorting an arbitrary list?
No, that's not it. But the sorting is done by value, and all but one value are 2. So you have at most two runs, which Timsort will recognize and merge in O(n).
Ah, that's interesting, that's new to me. Reading up on it, yes it makes sense it should be fast in this case. Despite that, though, timing this code:
[k for k, v in Counter(nums).items() if v == 1][0]

is consistently better performing that using `most_common()`. It seems like they should be the same, given what you're saying, since they both do a pass through all the dict items, no?
No, they can differ by a constant factor. Like one always being 1.5 times as fast as the other.
02:24
Yes, doing more empirical tests I see you're right (the factor in my case seems to always be 1.36).
Thanks for educating me around this!
What array sizes have you tested?
Various samples between 3 and 101.
Oops, I mean 3-201. :-)
Hmm, that's quite small. I usually try powers of 2 from 2^10 to 2^24 or so, i.e., up to millions of values.
Running...
02:50
Shouldn't take this long, how are you running it?
timeit.repeat(... repeat=3, number=10000)
Better use a smaller number than 10000 for the large arrays. When you're in the millions, number=1 is enough. The larger the array, the less often you have to do it.
03:12
For a linear time algorithm, I often make it so that the test time is roughly constant, by using increasing powers of 2 for the size and decreasing powers of 2 for the number. Like this: ideone.com/GsE5ZY
04:09
Yeah, that makes sense, certainly.
Anyway, I did see the factor slowly increase as the list size increased from about 1.3 to about 2 (at 2^16). It leveled off at 2.

last day (15 days later) »