Re: Python newbie needs constructive suggestions
Many thanks to those of you who responded to my question about anonymous functions with local variables, filling me in on e) do something else clever and Pythonic that I don't know about yet? by pointing out that I can use (among other good things) lambda with default arguments. That should suit my immediate needs well, since I don't need to maintain state (or avoid maintaning state); I may also look into closures (possibly anonymous ones?) and callable classes if I need to go beyond this. And, of course, if the code is complex enough, then one should give up the anonymous function and name it. Rest assured that I will _not_ be attempting to write "let" in Python and use it. It looks like Python may be every much as big an improvement over C++ as I had hoped. Dave Wonnacott -- http://mail.python.org/mailman/listinfo/python-list
Re: random shuffles
From: "danielx" <[EMAIL PROTECTED]> Date: 22 Jul 2006 01:43:30 -0700 Boris Borcic wrote: > does > > x.sort(cmp = lambda x,y : cmp(random.random(),0.5)) > > pick a random shuffle of x with uniform distribution ? ... Let e be the element which was in the first position to begin with. What are its chances of being there after being "sorted"? Well, in order for it to still be there, it would have to survive N rounds of selection. In each selection, it has 1/2 chance of surviving. That means its total chance of survival is 1/(2**N), which is much less than 1/N. QED! This proof makes sense to me if the sorting algorithm makes a random decision every time it swaps. Couldn't we easily get an n*log(n) shuffle by performing a _single_ mapping of each element in the collection to a pair made up of a random key and its value, and then sorting based on the keys and stripping them out? i.e., in O(n) time, turn "2 clubs", "2 diamonds", "2 hearts", "2 spades", "3 clubs" into something like [0.395, "2 clubs"], [0.158, "2 diamonds"], [0.432, "2 hearts"], [0.192, "2 spades"], [0.266, "3 clubs"] and then in O(n*log(n)) time, sort it into [0.158, "2 diamonds"], [0.192, "2 spades"], [0.266, "3 clubs"], [0.395, "2 clubs"], [0.432, "2 hearts"] and then strip out the keys again in O(n) time? Or perhaps this has been discussed already and I missed that part? I just joined the list... apologies if this is a repeat. You can accomplish this by doing what I will call "random selection". It would be like linear selection, except you wouldn't bother checking the head against every other element. When you want to figure out what to put at the head, just pick at random! I suspect this is what Python does in random.shuffle, since it is rather an easy to see it would result in something uniform (I swear I haven't looked at the source code for random.shuffle :P). But, after making the linear selection, don't you still need to use O(log(n)) time to find and remove the item from the collection? I don't know much about Python's internal data structures, but if there's an array in there, you need O(n) time to move up everything after the deleted item; if there's a list, you need O(n) time to find the element you picked at random; if there's a balanced tree, you could find it and delete it in O(log(n)) time... Help me review my undergraduate data structures here -- is there some way to pick each item _exactly_once_ in O(n) time? Dave Wonnacott -- http://mail.python.org/mailman/listinfo/python-list
Re: Python-list Digest, Vol 34, Issue 373
O.K., I'll publicly retract this for the whole list -- EVERYBODY PLEASE DISREGARD my thought about implementing an n*log(n) shuffle. I had hinted in my message that this was probably something that I should review from a data structures course, and of course there was a simple oversight in my message: you don't have to preserve the order of the collection from which you extract the element, so you can extract it in O(1) time by just swapping it, and easily get an O(n) shuffle algorithm (or, more easily, call random.shuffle()). Thanks for the polite tone with which many folks have pointed out my gross oversight. for i in range(1,100): print "I will not post to the Python list without thinking first" Now suitably embarrassed, Dave Wonnacott Date: 24 Jul 2006 06:24:48 -0700 From: "Ben Sizer" <[EMAIL PROTECTED]> Subject: Re: random shuffles To: python-list@python.org Ross Ridge wrote: > David G. Wonnacott wrote: > > Couldn't we easily get an n*log(n) shuffle... > > Why are you trying to get an O(n*log(n)) shuffle when an O(n) shuffle > algorithim is well known and implemented in Python as random.shuffle()? I think David is referring to this: "don't you still need to use O(log(n)) time to find and remove the item from the collection?" The answer for him is no: as far as I know, the Python list is a random-access structure, so looking up 2 items and swapping them runs in constant time. You perform that N times to shuffle the sequence, so it runs in O(N). -- Ben Sizer -- http://mail.python.org/mailman/listinfo/python-list
P.S. Re: Python newbie needs constructive suggestions
In response to my question, ``What is the idiomatically appropriate Python way to pass, as a "function-type parameter", code that is most clearly written with a local variable?'', a number of you made very helpful suggestions, including the use of a default argument; if one wanted to give a name to the constant one in my original example, map(lambda x: x+1, [5, 17, 49.5]) one would write map(lambda x, one=1: x+one, [5, 17, 49.5]) I've been using this happily in several cases, but just discovered that (of course), the variable "x" is not in scope until the expression in the lambda, so if one wanted to, say, have a variable that was 3*x, one could NOT write map(lambda x, threex=3*x: x+threex, [5, 17, 49.5]) [obviously there are easier ways to find 4*x, but I'm trying to keep close to my simplified example]. I'll need to show the code to beginners, so I don't want to get into the complexity of using the more advanced solutions that were suggested (closures or callable classes), so I'm going to bail out in such cases and just not use an anonymous function here. I'm not sure there's really a question here, other than the implicit "please let me know if there's yet another cool thing I can do here", but I thought I'd add this postscript to my earlier postings for the benefit of anyone following this thread. [I often see interesting threads in the archive but am left with an unresolved question "I wonder how that worked out"]. Dave Wonnacott -- http://mail.python.org/mailman/listinfo/python-list
