public
Last active

list rotation experiments

  • Download Gist
shift.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
"""Toy code for
 
http://stackoverflow.com/questions/2150108/efficient-way-to-shift-a-list-in-python
 
Example results of timeAll on my system with Python 2.6.4:
 
{'shiftCopy': 50.579999999999984,
'shiftExtend': 3.4200000000000017,
'shiftInPlace': 3.4099999999999966,
'shifted': 95.409999999999997}
"""
 
def newList():
"""Make a list with around a hundred thousand strings."""
l = open("/usr/share/dict/words").readlines()
return l
 
def shiftInPlace(l, n):
"""Shift the list in place."""
n = n % len(l)
head = l[:n]
l[:n] = []
l.extend(head)
return l
def shiftExtend(l, n):
"""Shift the list in place, without a temp variable.
"""
n = n % len(l)
# No temp variable, but the list is of length
# l+n for a while.
l.extend(l[:n])
l[:n] = []
return l
 
def shifted(l, n):
"""Shift and return a new list."""
n = n % len(l)
return l[n:] + l[:n]
 
def shiftCopy(l, n):
"""Shift and return a new list,
using extend instead of add.
"""
# first make a copy of the list so we don't mutate
# our argument.
l = l[:]
# implementation below is same as shiftInPlace
n = n % len(l)
head = l[:n]
l[:n] = []
l.extend(head)
return l
 
ALL_FUNCS = [
shifted,
shiftExtend,
shiftInPlace,
shiftCopy
]
def testShift(f):
"""basic sanity check."""
l = range(10)
expected = [2, 3, 4, 5, 6, 7, 8, 9, 0, 1]
result = f(l, 2)
assert result == expected, "%s: %s" % (f.func_name,
result)
 
def testAll():
for func in ALL_FUNCS:
print func.func_name,
testShift(func)
print "OK"
 
def timedemo(f, count=10000, by=4):
l = newList()
import os
start = os.times()[0]
for i in xrange(count):
l = f(l, by)
end = os.times()[0]
return end - start
 
def timeAll():
results = {}
for func in ALL_FUNCS:
length = timedemo(func)
results[func.func_name] = length
return results
 
if __name__ == '__main__':
import pprint
results = timeAll()
pprint.pprint(results)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.