Efficient rotation of a list in Python

While working on a Python application to do real time plotting of data, I needed a way to update the data. The data arrives over the serial line and can be received at quite a high rate. – easily a few thousand elements per second. The basic idea was to have the data stored in a list. When a new item arrives, the list must be shifted down one place and the new item placed at the end. Clearly, this should happen as quickly as possible.

For all sorts of other applications, I would just create a circular buffer and keep track of where the current head is. Each new item would just overwrite an old one and the pointer would move on. Unfortunately, the plotting library wants a simple list of data items. I looked at a couple of ways to do the shift and insert in Python. It soon becomes apparent that there are two ways to go about this for a generalised rotation. That is, a rotation where N items are removed from the head, the list is shifted down and added and then the N new data items are placed at the end.

Slicing

A Python function to rotate a list by n places might look like this:

this takes the last block of items and places them at the front of a new list and adds the first N items to that. Thus, if I have
data = [1, 2, 3, 4, 5, 6]
and call
data = shift_slice(data, 1)
the result will be
[2, 3, 4, 5, 6, 1]

For the plotter, I can then just overwrite the last element with the new data.

Slicing of lists in Python is and O(n) operation where n is the length of the list. That is to say, the time taken to run the function depends on the length of the list but not the number of places I want it rotated.

Popping and Appending

Another way to rotate a list by just one place is to pop the first element and then append it to the end of the list. For a rotate on N items this might be:

On the face of it, this should be a relatively expensive operation as the pop(0) action as also O(n) where n is the list length and all the elements are shifted down.

In practice, for small values of N, the pop and append method is much faster than slicing. Perhaps 20 times faster on a list of 10000 integers when N==1. Since the shift_pop() function repeats the operation N times, it should be clear that the actual time taken will increase linearly with the value of N.

For the plotter, where only a single item is added to the end of the list, I might have a function like

Hybrid rotate

It pays then, to consider your data and what you actually need when selecting a method for performing some action. For small N, it is faster (maybe much faster) to perform a pop and append. A general purpose function intended to rotate a list might examine the number of places the data is to be shifted and select a method that will give the best performance. This hybrid approach might look like this:

The chart below shows some results from timing 1000 iterations of the rotation of a 100,000 element list of integers by N places:

Your data may have different optimisation values but the principle is the same.