Efficient way to rotate a list in python

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]

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 also got interested in this and compared some of the suggested solutions with perfplot (a small project of mine).

It turns out that Kelly Bundy's suggestion

tmp = data[shift:]
tmp += data[:shift]

performs very well for all shifts.

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 list_append2(data):
    tmp = data[shift:]
    tmp += data[:shift]
    return tmp


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):
    data = data.copy()
    for _ in range(shift):
        data.append(data.pop(0))
    return data


b = perfplot.bench(
    setup=lambda n: numpy.random.rand(n).tolist(),
    kernels=[
        list_append,
        list_append2,
        roll,
        shift_concatenate,
        collections_deque,
        pop_append,
    ],
    n_range=[2 ** k for k in range(7, 20)],
    xlabel="len(data)",
)
b.show()
b.save("shift100.png")

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

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)

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.

def solution(A, K):
    if len(A) == 0:
        return A

    K = K % len(A)

    return A[-K:] + A[:-K]

# use case
A = [1, 2, 3, 4, 5, 6]
K = 3
print(solution(A, K))

For example, given

A = [3, 8, 9, 7, 6]
K = 3

the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given

A = [0, 0, 0]
K = 1

the function should return [0, 0, 0]

Given

A = [1, 2, 3, 4]
K = 4

the function should return [1, 2, 3, 4]

Jon Bentley in Programming Pearls (Column 2) describes an elegant and efficient algorithm for rotating an n-element vector x left by i positions:

Let's view the problem as transforming the array ab into the array ba, but let's also assume that we have a function that reverses the elements in a specified portion of the array. Starting with ab, we reverse a to get arb, reverse b to get arbr, and then reverse the whole thing to get (arbr)r, which is exactly ba. This results in the following code for rotation:

reverse(0, i-1)
reverse(i, n-1)
reverse(0, n-1)

This can be translated to Python as follows:

def rotate(x, i):
    i %= len(x)
    x[:i] = reversed(x[:i])
    x[i:] = reversed(x[i:])
    x[:] = reversed(x)
    return x

Demo:

>>> def rotate(x, i):
...     i %= len(x)
...     x[:i] = reversed(x[:i])
...     x[i:] = reversed(x[i:])
...     x[:] = reversed(x)
...     return x
... 
>>> rotate(list('abcdefgh'), 1)
['b', 'c', 'd', 'e', 'f', 'g', 'h', 'a']
>>> rotate(list('abcdefgh'), 3)
['d', 'e', 'f', 'g', 'h', 'a', 'b', 'c']
>>> rotate(list('abcdefgh'), 8)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> rotate(list('abcdefgh'), 9)
['b', 'c', 'd', 'e', 'f', 'g', 'h', 'a']

I was looking for in place solution to this problem. This solves the purpose in O(k).

def solution(self, list, k):
    r=len(list)-1
    i = 0
    while i<k:
        temp = list[0]
        list[0:r] = list[1:r+1]
        list[r] = temp
        i+=1
    return list

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 

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

I'm "old school" I define efficiency in lowest latency, processor time and memory usage, our nemesis are the bloated libraries. So there is exactly one right way:

    def rotatel(nums):
        back = nums.pop(0)
        nums.append(back)
        return nums

Below is an efficient algorithm that doesn't require the use of any additional data structure:

def rotate(nums: List[int], k: int):

    k = k%len(nums)
    l, r = 0, len(nums)-1
    while (l<r):
        nums[l], nums[r]= nums[r], nums[l]
        l,r=l+1,r-1
    
    l,r = 0, k-1
    while (l<r):
        nums[l], nums[r]=nums[r], nums[l]
        l,r=l+1,r-1
        
    l,r=k,len(nums)-1
    while (l<r):
        nums[l], nums[r]=nums[r], nums[l]
        l,r=l+1,r-1