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:

1 2 |
<strong>def shift_slice</strong>(l,n): <strong>return </strong>l[n:] + l[:n] |

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:

1 2 3 4 5 |
def shift_pop(l,n): while n: n -= 1 l.append(l.pop(0)) return l |

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

1 2 3 4 |
def add_element(data,new_element): data.pop(0) data.append(new_element) return data |

## 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:

1 2 3 4 5 |
def shift(l,n): if (n < 20): return shift_pop(l,n) else : return shift_slice(l,n) |

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.

Hello Peter, how are you? Sorry for bother you, but i reset my pc, and i lost one of youR documentS that i was using for trying to fusing the encoder and the imu in my line follower, do you still have this document? https://micromouseonline.com/download/MINOS18-Peter-Harrison-Edumouse.pdf