Unsorting(randomizing) a sequence
Guido van Rossum
guido at cnri.reston.va.us
Thu Aug 19 14:35:15 EDT 1999
Ian Clarke <I.Clarke at strs.co.uk> writes:
> I did some timing tests using the code I have attached below, here are
> the results (in seconds) for sorting a list of 200 items 10 times:
>
> Dan Schmidt's solution (using sort): 14.98
> Stephan Houben's solution : 2.82
> Skip Montanaro's solution : 2.736
> (as modified by Dan schmidt)
> Magnus L Hetland's solution : 0.032
> Skip's solution but with arrays : 3.182
>
> As you can see I thought that using arrays may provide an efficiency
> speed-up for Skip's algorithm, but apparently not. Oh, I haven't really
> checked this code too carefully, so feel free to redo the tests if you
> find any bugs in the code.
>
> Magnus L Hetland's solution wins hands down.
The two-orders-of-magnitude-faster result should have made you look
twice. There's a bug: s4(list) modifies its argument (empyting it) so
you did only one run, plus 9 runs of an empty list! Corrected, I get
these timings (on a slightly faster machine, it seems):
s1 12.1
s2 2.31
s3 2.63
s4 2.68
s5 2.82
Here's the fixed s4():
def s4(list):
"""Magnus L Hetland's solution"""
result = []
list = list[:]
for i in range(len(list)):
element = random.choice(list)
list.remove(element)
result.append(element)
return result
But the winner is Tim Peters' entry, already in the CVS tree. Its
time is 1.34 seconds:
def shuffle(x, random=random, int=int):
"""x, random=random.random -> shuffle list x in place; return None.
Optional arg random is a 0-argument function returning a random
float in [0.0, 1.0); by default, the standard random.random.
Note that for even rather small len(x), the total number of
permutations of x is larger than the period of most random number
generators; this implies that "most" permutations of a long
sequence can never be generated.
"""
for i in xrange(len(x)-1, 0, -1):
# pick an element in x[:i+1] with which to exchange x[i]
j = int(random() * (i+1))
x[i], x[j] = x[j], x[i]
--Guido van Rossum (home page: http://www.python.org/~guido/)
More information about the Python-list
mailing list