6 ms·
Python Multiple Assignment Is a Puzzle
- zebulanmcranahn 12y agodef findMissingPositive(A): A.sort() return min([x for x in range(A[0], A[-1]+1) if x not in A])
- jw2013 12y agoThe function you wrote: 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)). So firstMissingPositive([4,100]) should return 1, instead of 5. But the problem is not stated in the post, so let's assume you are implementing the first missing positive in range(A[0], A[-1] + 1) for sorted(A), your code does not handle corner case well. For example: a) your firstMissingPositive([100]) gives ValueError: min() arg is an empty sequence b) your firstMissingPositive([]) gives IndexError: list index out of range It is attempting to write three-liners that seems to solve the problem, but it is far more important to solve the problem in time and space efficient way. At least, it is important to handle the corner cases well.
- zebulanmcranahn 12y agodef 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 Two above return: print(firstMissingPositive([4,2,5,7,1])) # 3 print(firstMissingPositive([4,100])) # 1 print(firstMissingPositive([])) # [] print(firstMissingPositive([5])) # 1 I wasn't sure what [5] or [] were supposed to return so maybe I'm still wrong? Had never heard of this question before, thought I'd try it out. Thanks for the reply, very informative.
- yeukhon 12y agoHN is not really for code review, but why are you using try and except here??
- TheLoneWolfling 12y agoPython 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.
- zebulanmcranahn 12y agoThanks 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!
- TheLoneWolfling 12y agoYou really should change "except" to "except ValueError" there. Also, I suggest first converting A to a set. Just "A = set(A)" would work.
- ghshephard 12y agoWhile 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 x
- CraigJPerry 12y agoNice! Is there an advantage in using a set comprehension over set(a) or is it just a stylistic choice?
- ghshephard 12y agoNone 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. 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 loop
- _ZeD_ 12y agostyle
- michaelmior 12y agoWhile 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.
- gizmo 12y agoSet 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.
- todd8 12y agoI 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] versus >>> i = 0 >>> a = [0, 0] >>> a[i], i = 10, 1 >>> a [10, 0]
- tobinfricke 12y agoDoes 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.
- todd8 12y agoYes, 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: expr3, expr4 = expr1, expr2 Although evaluation order is handled differently by different programming languages, it seems that Python is behaving logically here. [1] https://docs.python.org/3.4/reference/expressions.html#evaluation-order https://docs.python.org/3.4/reference/expressions.html#evalu...
- Someone 12y agoI 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 expr3 = tmp3 expr4 = tmp4 or expr3 = expr1 expr4 = expr2 ? I guess it is the latter, but the text does not make that clear.
- zwegner 12y agoThe first--the latter isn't in order (expr3 is "evaluated" before expr2, which in this case means assignment).
- deleted 12y ago[deleted]
- kghose 12y agoA = [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' Trying to be more Pythonic: 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]
- abhinavk 12y agoBut the code is not competitive.
- ericfrederich 12y agoSorting is not O(N), at best it is O(NlogN)
- yoo-interested 12y agoThis reminded me of gotchas one can fall to when defining some Lisp macro from scratch. So I decided to test whether rotatef works exactly like Python's multiple assignment: (let ((A (vector 2 1))) (rotatef (elt A 0) (elt A (1- (elt A 0)))) A) It returns a changed vector as if indexes were saved. I am not sure which should be considered the right behavior.
- malisper 12y agoFrom 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). (setf expr2 expr1 expr4 expr3) (psetf expr3 expr1 expr4 expr2) [0] http://clhs.lisp.se/Body/m_rotate.htm http://clhs.lisp.se/Body/m_rotate.htm
- tom1024 12y agoPlease note, that the solution from the post has O(n) space complexity (you modify the input and this counts as using the extra memory).
- podlipensky 12y agoInteresting post regarding python, but the algo is incorrect, consider test case firstMissingPositive([100,101,103,104]) will return 1 instead of 102