list rotation experiments

shift.py

"""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)