# rotate - Efficient way to shift a list in python

## first element (21)

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

```
>>> def shift(l, n):
... return l[n:] + l[:n]
...
>>> l = [1,2,3,4]
>>> shift(l,1)
[2, 3, 4, 1]
>>> shift(l,2)
[3, 4, 1, 2]
>>> shift(l,0)
[1, 2, 3, 4]
>>> shift(l,-1)
[4, 1, 2, 3]
```

Is there a better way?

## Answers

A `collections.deque`

is optimized for pulling and pushing on both ends. They even have a dedicated `rotate()`

method.

```
from collections import deque
items = deque([1, 2])
items.append(3) # deque == [1, 2, 3]
items.rotate(1) # The deque is now: [3, 1, 2]
items.rotate(-1) # Returns deque to original state: [1, 2, 3]
item = items.popleft() # deque == [2, 3]
```

The following method is O(n) in place with constant auxiliary memory:

```
def rotate(arr, shift):
pivot = shift % len(arr)
dst = 0
src = pivot
while (dst != src):
arr[dst], arr[src] = arr[src], arr[dst]
dst += 1
src += 1
if src == len(arr):
src = pivot
elif dst == pivot:
pivot = src
```

Note that in python, this approach is horribly inefficient compared to others as it can't take advantage of native implementations of any of the pieces.

For an immutable implementation, you could use something like this:

```
def shift(seq, n):
shifted_seq = []
for i in range(len(seq)):
shifted_seq.append(seq[(i-n) % len(seq)])
return shifted_seq
print shift([1, 2, 3, 4], 1)
```

I don't know if this is 'efficient', but it also works:

```
x = [1,2,3,4]
x.insert(0,x.pop())
```

EDIT: Hello again, I just found a big problem with this solution! Consider the following code:

```
class MyClass():
def __init__(self):
self.classlist = []
def shift_classlist(self): # right-shift-operation
self.classlist.insert(0, self.classlist.pop())
if __name__ == '__main__':
otherlist = [1,2,3]
x = MyClass()
# this is where kind of a magic link is created...
x.classlist = otherlist
for ii in xrange(2): # just to do it 2 times
print '\n\n\nbefore shift:'
print ' x.classlist =', x.classlist
print ' otherlist =', otherlist
x.shift_classlist()
print 'after shift:'
print ' x.classlist =', x.classlist
print ' otherlist =', otherlist, '<-- SHOULD NOT HAVE BIN CHANGED!'
```

The shift_classlist() method executes the same code as my x.insert(0,x.pop())-solution, otherlist is a list indipendent from the class. After passing the content of otherlist to the MyClass.classlist list, calling the shift_classlist() also changes the otherlist list:

CONSOLE OUTPUT:

```
before shift:
x.classlist = [1, 2, 3]
otherlist = [1, 2, 3]
after shift:
x.classlist = [3, 1, 2]
otherlist = [3, 1, 2] <-- SHOULD NOT HAVE BIN CHANGED!
before shift:
x.classlist = [3, 1, 2]
otherlist = [3, 1, 2]
after shift:
x.classlist = [2, 3, 1]
otherlist = [2, 3, 1] <-- SHOULD NOT HAVE BIN CHANGED!
```

I use Python 2.7. I don't know if thats a bug, but I think it's more likely that I missunderstood something here.

Does anyone of you know why this happens?

I have similar thing. For example, to shift by two...

```
def Shift(*args):
return args[len(args)-2:]+args[:len(args)-2]
```

Following function copies sent list to a templist, so that pop function does not affect the original list:

```
def shift(lst, n, toreverse=False):
templist = []
for i in lst: templist.append(i)
if toreverse:
for i in range(n): templist = [templist.pop()]+templist
else:
for i in range(n): templist = templist+[templist.pop(0)]
return templist
```

Testing:

```
lst = [1,2,3,4,5]
print("lst=", lst)
print("shift by 1:", shift(lst,1))
print("lst=", lst)
print("shift by 7:", shift(lst,7))
print("lst=", lst)
print("shift by 1 reverse:", shift(lst,1, True))
print("lst=", lst)
print("shift by 7 reverse:", shift(lst,7, True))
print("lst=", lst)
```

Output:

```
lst= [1, 2, 3, 4, 5]
shift by 1: [2, 3, 4, 5, 1]
lst= [1, 2, 3, 4, 5]
shift by 7: [3, 4, 5, 1, 2]
lst= [1, 2, 3, 4, 5]
shift by 1 reverse: [5, 1, 2, 3, 4]
lst= [1, 2, 3, 4, 5]
shift by 7 reverse: [4, 5, 1, 2, 3]
lst= [1, 2, 3, 4, 5]
```

I think you are looking for this:

```
a.insert(0, x)
```

Simplest way I can think of:

```
a.append(a.pop(0))
```

If you just want to iterate over these sets of elements rather than construct a separate data structure, consider using iterators to construct a generator expression:

```
def shift(l,n):
return itertools.islice(itertools.cycle(l),n,n+len(l))
>>> list(shift([1,2,3],1))
[2, 3, 1]
```

I also got interested in this and compared some of the suggested solutions with perfplot (a small project of mine).

It turns out that

```
for _ in range(n):
data.append(data.pop(0))
```

is *by far* the fastest method for small shifts `n`

.

For larger `n`

,

```
data[n:] + data[:n]
```

isn't bad.

Essentially, perfplot performs the shift for increasing large arrays and measures the time. Here are the results:

`shift = 1`

:

`shift = 100`

:

Code to reproduce the plot:

```
import numpy
import perfplot
import collections
shift = 100
def list_append(data):
return data[shift:] + data[:shift]
def shift_concatenate(data):
return numpy.concatenate([data[shift:], data[:shift]])
def roll(data):
return numpy.roll(data, -shift)
def collections_deque(data):
items = collections.deque(data)
items.rotate(-shift)
return items
def pop_append(data):
for _ in range(shift):
data.append(data.pop(0))
return data
perfplot.save(
"shift100.png",
setup=lambda n: numpy.random.rand(n).tolist(),
kernels=[list_append, roll, shift_concatenate, collections_deque, pop_append],
n_range=[2 ** k for k in range(7, 20)],
logx=True,
logy=True,
xlabel="len(data)",
)
```

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]
```

I think you've got the most efficient way

```
def shift(l,n):
n = n % len(l)
return l[-U:] + l[:-U]
```

for similar functionality as shift in other languages:

```
def shift(l):
x = l[0]
del(l[0])
return x
```

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.

Numpy can do this using the `roll`

command:

```
>>> import numpy
>>> a=numpy.arange(1,10) #Generate some data
>>> numpy.roll(a,1)
array([9, 1, 2, 3, 4, 5, 6, 7, 8])
>>> numpy.roll(a,-1)
array([2, 3, 4, 5, 6, 7, 8, 9, 1])
>>> numpy.roll(a,5)
array([5, 6, 7, 8, 9, 1, 2, 3, 4])
>>> numpy.roll(a,9)
array([1, 2, 3, 4, 5, 6, 7, 8, 9])
```

For a list `X = ['a', 'b', 'c', 'd', 'e', 'f']`

and a desired shift value of `shift`

**less than list length**, we can define the function `list_shift()`

as below

```
def list_shift(my_list, shift):
assert shift < len(my_list)
return my_list[shift:] + my_list[:shift]
```

Examples,

`list_shift(X,1)`

returns `['b', 'c', 'd', 'e', 'f', 'a']`

`list_shift(X,3)`

returns `['d', 'e', 'f', 'a', 'b', 'c']`

What is the use case? Often, we don't actually need a fully shifted array --we just need to access a handful of elements in the shifted array.

Getting Python slices is runtime O(k) where k is the slice, so a sliced rotation is runtime N. The deque rotation command is also O(k). Can we do better?

Consider an array that is extremely large (let's say, so large it would be computationally slow to slice it). An alternative solution would be to leave the original array alone and simply calculate the index of the item that would have existed in our desired index after a shift of some kind.

Accessing a shifted element thus becomes O(1).

```
def get_shifted_element(original_list, shift_to_left, index_in_shifted):
# back calculate the original index by reversing the left shift
idx_original = (index_in_shifted + shift_to_left) % len(original_list)
return original_list[idx_original]
my_list = [1, 2, 3, 4, 5]
print get_shifted_element(my_list, 1, 2) ----> outputs 4
print get_shifted_element(my_list, -2, 3) -----> outputs 2
```

What about just using `pop(0)`

?

`list.pop([i])`

Remove the item at the given position in the list, and return it. If no index is specified,

`a.pop()`

removes and returns the last item in the list. (The square brackets around the`i`

in the method signature denote that the parameter is optional, not that you should type square brackets at that position. You will see this notation frequently in the Python Library Reference.)

I take this cost model as a reference:

http://scripts.mit.edu/~6.006/fall07/wiki/index.php?title=Python_Cost_Model

Your method of slicing the list and concatenating two sub-lists are linear-time operations. I would suggest using pop, which is a constant-time operation, e.g.:

```
def shift(list, n):
for i in range(n)
temp = list.pop()
list.insert(0, temp)
```

Just some notes on timing:

If you're starting with a list, `l.append(l.pop(0))`

is the fastest method you can use. This can be shown with time complexity alone:

- deque.rotate is
**O(k)**(k=number of elements) - list to deque conversion is
**O(n)** - list.append and list.pop are both
**O(1)**

So if you are starting with `deque`

objects, you can `deque.rotate()`

at the cost of O(k). But, if the starting point is a list, the time complexity of using `deque.rotate()`

is O(n). `l.append(l.pop(0)`

is faster at O(1).

Just for the sake of illustration, here are some sample timings on 1M iterations:

Methods which require type conversion:

`deque.rotate`

with deque object:**0.12380790710449219 seconds**(fastest)`deque.rotate`

with type conversion:**6.853878974914551 seconds**`np.roll`

with nparray:**6.0491721630096436 seconds**`np.roll`

with type conversion:**27.558452129364014 seconds**

List methods mentioned here:

`l.append(l.pop(0))`

:**0.32483696937561035 seconds**(fastest)- "
`shiftInPlace`

":**4.819645881652832 seconds** - ...

Timing code used is below.

## collections.deque

Showing that creating deques from lists is O(n):

```
from collections import deque
import big_o
def create_deque_from_list(l):
return deque(l)
best, others = big_o.big_o(create_deque_from_list, lambda n: big_o.datagen.integers(n, -100, 100))
print best
# --> Linear: time = -2.6E-05 + 1.8E-08*n
```

If you need to create deque objects:

1M iterations @ 6.853878974914551 seconds

```
setup_deque_rotate_with_create_deque = """
from collections import deque
import random
l = [random.random() for i in range(1000)]
"""
test_deque_rotate_with_create_deque = """
dl = deque(l)
dl.rotate(-1)
"""
timeit.timeit(test_deque_rotate_with_create_deque, setup_deque_rotate_with_create_deque)
```

If you already have deque objects:

1M iterations @ 0.12380790710449219 seconds

```
setup_deque_rotate_alone = """
from collections import deque
import random
l = [random.random() for i in range(1000)]
dl = deque(l)
"""
test_deque_rotate_alone= """
dl.rotate(-1)
"""
timeit.timeit(test_deque_rotate_alone, setup_deque_rotate_alone)
```

## np.roll

If you need to create nparrays

1M iterations @ 27.558452129364014 seconds

```
setup_np_roll_with_create_npa = """
import numpy as np
import random
l = [random.random() for i in range(1000)]
"""
test_np_roll_with_create_npa = """
np.roll(l,-1) # implicit conversion of l to np.nparray
"""
```

If you already have nparrays:

1M iterations @ 6.0491721630096436 seconds

```
setup_np_roll_alone = """
import numpy as np
import random
l = [random.random() for i in range(1000)]
npa = np.array(l)
"""
test_roll_alone = """
np.roll(npa,-1)
"""
timeit.timeit(test_roll_alone, setup_np_roll_alone)
```

## "Shift in place"

Requires no type conversion

1M iterations @ 4.819645881652832 seconds

```
setup_shift_in_place="""
import random
l = [random.random() for i in range(1000)]
def shiftInPlace(l, n):
n = n % len(l)
head = l[:n]
l[:n] = []
l.extend(head)
return l
"""
test_shift_in_place="""
shiftInPlace(l,-1)
"""
timeit.timeit(test_shift_in_place, setup_shift_in_place)
```

## l.append(l.pop(0))

Requires no type conversion

1M iterations @ 0.32483696937561035

```
setup_append_pop="""
import random
l = [random.random() for i in range(1000)]
"""
test_append_pop="""
l.append(l.pop(0))
"""
timeit.timeit(test_append_pop, setup_append_pop)
```

# If performance is of concern:

It is mentioned in numerous answers that the built-in method of `list.index(item)`

method is an O(n) algorithm. It is fine if you need to perform this once. But if you need to access the indices of elements a number of times, it makes more sense to first create a dictionary (O(n)) of item-index pairs, and then access the index at O(1) every time you need it.

If you are sure that the items in your list are never repeated, you can easily:

```
myList = ["foo", "bar", "baz"]
# Create the dictionary
myDict = dict((e,i) for i,e in enumerate(myList))
# Lookup
myDict["bar"] # Returns 1
# myDict.get("blah") if you don't want an error to be raised if element not found.
```

If you may have duplicate elements, and need to return all of their indices:

```
from collections import defaultdict as dd
myList = ["foo", "bar", "bar", "baz", "foo"]
# Create the dictionary
myDict = dd(list)
for i,e in enumerate(myList):
myDict[e].append(i)
# Lookup
myDict["foo"] # Returns [0, 4]
```