Python Multiple Assignment Is a Puzzle(jw2013.github.io)
jw2013.github.io
Python Multiple Assignment Is a Puzzle
http://jw2013.github.io/blog/2014/07/26/python-multiple-assignment-is-a-puzzle/
8 comments
From the standard[0], "In the form (rotatef place1 place2 ... placen), the values in place1 through placen are read and written. Values 2 through n and value 1 are then stored into place1 through placen. It is as if all the places form an end-around shift register that is rotated one place to the left, with the value of place1 being shifted around the end to placen." The key word being place Once (elt A 0) and (elt A (1- (elt A 0))) are evaluated rotatef keeps track of the places and the values at those locations. It then assigns the values to the places; it does not reevaluate the expressions.
There is also setf and psetf which in the examples I'm giving evaluate from lowest suffix to highest (same as todd8).
There is also setf and psetf which in the examples I'm giving evaluate from lowest suffix to highest (same as todd8).
(setf expr2 expr1
expr4 expr3)
(psetf expr3 expr1
expr4 expr2)
Please note, that the solution from the post has O(n) space complexity (you modify the input and this counts as using the extra memory).
Interesting post regarding python, but the algo is incorrect, consider test case firstMissingPositive([100,101,103,104]) will return 1 instead of 102
def findMissingPositive(A):
A.sort()
return min([x for x in range(A[0], A[-1]+1) if x not in A])
The function you wrote:
For example:
a) takes O(n*lgn) time; the method in post uses O(n) time
b) use extra memory; the method in post uses O(1) extra memory
c) have logical error: the problem asks to find the first missing positive (in range [1, infinity)).
For example:
a) your firstMissingPositive([100]) gives ValueError: min() arg is an empty sequence
b) your firstMissingPositive([]) gives IndexError: list index out of range
def firstMissingPositive(A):
try:
for x in range(1, max(A)+1):
if x not in A: return x
except: return A
def firstMissingPositive(A):
try: return next(x for x in range(1, max(A)+1) if x not in A)
except: return A
print(firstMissingPositive([4,2,5,7,1])) # 3
print(firstMissingPositive([4,100])) # 1
print(firstMissingPositive([])) # []
print(firstMissingPositive([5])) # 1
Thanks for the reply, very informative.
You really should change "except" to "except ValueError" there.
Also, I suggest first converting A to a set. Just "A = set(A)" would work.
Also, I suggest first converting A to a set. Just "A = set(A)" would work.
HN is not really for code review, but why are you using try and except here??
Python is designed for it, and it makes it cleaner, so why not?
EAFP: Easier to ask for forgiveness than permission
That being said, just a blanket except is a bad idea.
EAFP: Easier to ask for forgiveness than permission
That being said, just a blanket except is a bad idea.
Thanks for the ValueError tip. I added it as well as a TypeError just in case the input comes in as a string. My skills are beginner level at best, tips like yours help a lot!
While it may require an extra set, the following is a lot more pythonic, and also finds the first missing positive in the same two passes that your code did (which is actually O(2n), and honestly made my eyes bleed trying to follow.)
def missPos(a):
b={x for x in a}
for x in range(1,len(b)+2):
if not x in b:
return xJust wanted to add a more functional solution:
def miss_pos(a):
b = range(1, len(a)+2)
return min(set(b).difference(a))
I wonder why so much discussion about arbitrary rules of assignment when the solution to the problem can be written (and is more readable) without ever mentioning this complicated "assignment" feature.
Set creation takes O(N) space and O(N log(N)) time, and the inner loop condition (if not x in b) is also log(N). So it's slower in time and it requires more space. People usually don't distinguish between O(N) and O(2N), because actual performance is dependent on implementation choices and CPU cache locality and all that stuff isn't really part of algorithmic complexity analysis.
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.
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.
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.
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.
Edit - nevermind. It's a hash table of course. So I'm wrong.
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).
https://wiki.python.org/moin/TimeComplexity#set
Also, the average case for set membership testing is O(1), so the average case runtime would actually be O(N).
https://wiki.python.org/moin/TimeComplexity#set
The context for these coding-challenges is they are the type for algorithm competition or white-board coding interview.
Back then when I was still looking for job, I was asked this question by a startup. I gave out this hashset solution and was quickly asked if O(1) space solution was available and then asked to implemented it.
If the space restriction is not an issue, I would definitely go with the method you suggested. Way more succinct and easier to follow.
Back then when I was still looking for job, I was asked this question by a startup. I gave out this hashset solution and was quickly asked if O(1) space solution was available and then asked to implemented it.
If the space restriction is not an issue, I would definitely go with the method you suggested. Way more succinct and easier to follow.
O(n) = O(2n)
Nice!
Is there an advantage in using a set comprehension over set(a) or is it just a stylistic choice?
Is there an advantage in using a set comprehension over set(a) or is it just a stylistic choice?
None that I know of - As a novice python programmer, I just try and use comprehensions for everything so my eyes get used to the pattern.
The set function is somewhat faster.
The set function is somewhat faster.
a=[]
for x in range(10000):
a.append(randint(1,2000))
%timeit b=set(a)
1000 loops, best of 3: 373 µs per loop
%timeit b={x for x in a}
1000 loops, best of 3: 542 µs per loopstyle
While comprehensions are definitely standard Python, I would argue that if you're not actually changing any value (as is the case here, then just `set(a)`, being much simpler, is more Pythonic.
I think it's easier to see what is going on without the nested subscripting:
>>> i = 0
>>> a = [0, 0]
>>> i, a[i] = 1, 10
>>> a
[0, 10]
>>> i = 0
>>> a = [0, 0]
>>> a[i], i = 10, 1
>>> a
[10, 0]It's notable that in the same situation perl will do basically the same thing as python ... unless it detects a dependency (i.e. same variable referenced on both sides), in which case it constructs a temporary list, fills that from the RHS, then evaluates the LHS to get a list of lvalues, then assigns (roughly, I've not been in that part of the VM code for a bit).
i.e. from perl's POV, python's behaviour is an optimisation, which if over-applied introduces a bug ... but, y'know, DWIM vs. regularity etc., I'm just surprised that python's behaviour is sloppier than perl's here :)
i.e. from perl's POV, python's behaviour is an optimisation, which if over-applied introduces a bug ... but, y'know, DWIM vs. regularity etc., I'm just surprised that python's behaviour is sloppier than perl's here :)
Does the language specify that things will work this way, or is it undefined / implementation-dependent behavior?
To me, it smells like the result of a sloppy specification.
To me, it smells like the result of a sloppy specification.
Yes, this behavior is spelled out in detail in the Python Language Reference [1], in particular section 6.14 Evaluation Order. It explicitly states that the order of evaluation is left to right with the right hand side of assignments being executed before the left hand side. It further gives this example where expressions are evaluated in the order of their suffixes:
[1] https://docs.python.org/3.4/reference/expressions.html#evalu...
expr3, expr4 = expr1, expr2
[1] https://docs.python.org/3.4/reference/expressions.html#evalu...
I think that specification still can be improved. It is clear about order of evaluation, but not on the order of assignment.
Does it do tmp3 = expr1 tmp4 = expr2
Does it do tmp3 = expr1 tmp4 = expr2
expr3 = tmp3
expr4 = tmp4 expr3 = expr1
expr4 = expr2
The first--the latter isn't in order (expr3 is "evaluated" before expr2, which in this case means assignment).
That's precisely the place where I think the description can be improved. With complex assignments, there are two parts: compute the place to store a value, and store the value there. In my mental model, the latter is better called assignment than evaluation.
With Python's evaluation/assignment order, both parts of a complex assignment happen at once--which is the source of the weird behavior in the article (A[0] is assigned to before the subscript of A[A[0] - 1] is evaluated).
[deleted]
[deleted]
A = [1, 2, 4, 5, 7]
A_s = sorted(A)
b = A_s[0]
for a in A_s[1:]:
if a - b > 1:
print b + 1
break
else:
b = a
else:
print 'No missing element'
def test(l):
l_s = sorted(l)
print [l0 + 1 for l1, l0 in zip(l_s[1:], l_s[:-1]) if l1 - l0 > 1]Sorting is not O(N), at best it is O(NlogN)
But the code is not competitive.
It returns a changed vector as if indexes were saved.
I am not sure which should be considered the right behavior.