Re:Python Multiple Assignment Is a Puzzle
by ghshephard on Sunday July 27, 2014 @06:29AM
(#8092411)
Why would set creation (and the not x in b inner loop) take O(Nlog(N)) time? I would have thought it would have just required a hash-lookup for each element (O(1)?) being added (and then, a decision to either add the element or not.
Actual times definitely more than O(N) growth.
a10k = []
for x in range(10000):
a10k.append(randint(1,20000))
%timeit b10k = set(a10k)
10k elements = 364 microseconds/loop
100k elements = 5 milliseconds/loop
1mm elements = 170 milliseconds/loop
10mm elements = 2.4 seconds/loop.
100mm elements = 34.5 seconds/loop
I'm assuming a set is internally a balanced tree of some sort. So lookup and insertions are O(log N). So N insertions should be O(N log N).
Edit - nevermind. It's a hash table of course. So I'm wrong.
Re:Python Multiple Assignment Is a Puzzle
by michaelmior on Sunday July 27, 2014 @08:00AM
(#8092530)
Run this on Python 3 or use xrange instead of range on Python 2 and you get N space instead of 2N anyway :)
Also, the average case for set membership testing is O(1), so the average case runtime would actually be O(N).
I do like your solution better though, but mostly because it doesn't mutate the array passed to the function. A function called "firstMissingPositive" shouldn't modify state.