Efficient way to shift a list in python

Question

What is the most efficient way to shift a list in python? Right now I have something like this:

>>> shift = lambda l, n: l[n:]+l[:n]
>>> l = [1,2,3]
>>> shift(l,1)
[2, 3, 1]
>>> shift(l,2)
[3, 1, 2]
>>> shift(l,0)
[1, 2, 3]

Is there a better way?

Answer 1

A collection.deque is optimized for pulling and pushing on both ends. They even have a dedicated rotate() method.

Answer 2

If efficiency is your goal, (cycles? memory?) you may be better off looking at the array module: http://docs.python.org/library/array.html

Arrays do not have the overhead of lists.

As far as pure lists go though, what you have is about as good as you can hope to do.

Answer 3

It depends on what you want to have happen when you do this:

>>> shift([1,2,3], 14)

You might want to change your:

def shift(seq, n):
    return seq[n:]+seq[:n]

to:

def shift(seq, n):
    n = n % len(seq)
    return seq[n:] + seq[:n]

Answer 4

Possibly a ringbuffer is more suitable. It is not a list, although it is likely that it can behave enough like a list for your purposes.

The problem is that the efficiency of a shift on a list is O(n), which becomes significant for large enough lists.

Shifting in a ringbuffer is simply updating the head location which is O(1)

Answer 5

This also depends on if you want to shift the list in place (mutating it), or if you want the function to return a new list. Because, according to my tests, something like this is at least twenty times faster than your implementation that adds two lists:

def shiftInPlace(l, n):
    n = n % len(l)
    head = l[:n]
    l[:n] = []
    l.extend(head)
    return l

In fact, even adding a l = l[:] to the top of that to operate on a copy of the list passed in is still twice as fast.

Various implementations with some timing at http://gist.github.com/288272