Unsorting(randomizing) a sequence
Ian Clarke
I.Clarke at strs.co.uk
Wed Aug 18 15:33:55 CEST 1999
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.
Ian.
---
import random, array, time
def timing(f, n, a):
"""
A timing function borrowed from
http://www.python.org/doc/essays/list2str.html
"""
print f.__name__,
r = range(n)
t1 = time.clock()
for i in r:
f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
t2 = time.clock()
print round(t2-t1, 3)
def s1(list):
"""Dan Schmidt's solution - (mis)using sort"""
def randomize(a,b):
return random.choice([-1, 0, 1])
list.sort(randomize)
return
def s2(list):
"""Stephan Houben's solution"""
length = len(list)
for i in range(length):
j = random.randrange(i, length)
list[i], list[j] = list[j], list[i]
def s3(list):
"""Skip Montanaro's solution as fixed by Dan Schmidt"""
for i in range(len(list)-1, 0, -1):
choice = int(whrandom.randint(0,i))
list[choice], list[i] = list[i], list[choice]
def s4(list):
"""Magnus L Hetland's solution"""
result = []
for i in range(len(list)):
element = random.choice(list)
list.remove(element)
result.append(element)
return result
def s5(ar):
"""Ian Clarke's solution"""
for i in range(len(ar)-1,0,-1):
choice = int(whrandom.randint(0,i))
ar[choice], ar[i] = ar[i], ar[choice]
return ar
timing(s1, 10, range(200))
timing(s2, 10, range(200))
timing(s3, 10, range(200))
timing(s4, 10, range(200))
timing(s5, 10, array.array('b', range(200)))
More information about the Python-list
mailing list