Implementing a circular data structure using lists (Python recipe) by Chris McDonough

ActiveState Code (http://code.activestate.com/recipes/52246/)

Performance issues? I like the recepie, but can you throw in some comments on performance? How expensive is a "turn" operation, and does it scale with the length of the list? Michael Chermside

Expense. I'm not sure, but...

From the Python FAQ:

6.16. How are lists implemented?

Despite what a Lisper might think, Python's lists are really variable-length arrays. The implementation uses a contiguous array of references to other objects, and keeps a pointer to this array (as well as its length) in a list head structure. This makes indexing a list (a[i]) an operation whose cost is independent of the size of the list or the value of the index.

When items are appended or inserted, the array of references is resized. Some cleverness is applied to improve the performance of appending items repeatedly; when the array must be grown, some extra space is allocated so the next few times don't require an actual resize.

I imagine most of the computational time is taken up for the append, when the list needs to be grown (if it actually does need to be grown). Chris McDonough

A faster version O(constant).

# here's a faster version:

import UserList

class Ring(UserList.UserList):
    def __init__(self, data = []):
        self.data = data
        self.offset=0

    def turn(self, n=1):
        self.offset = self.offset+n
        while self.offset<0:
                self.offset = self.offset + len(self.data)
            while self.offset>=len(self.data):
            self.offset = self.offset - len(self.data)

    def __getitem__(self, i):
        if abs(i)>=len(self.data):
            return self.data[i] # raise IndexError
        return self.data[(i-self.offset)%len(self.data)]

    def append(self, x):
        length = len(self.data)
        while self.offset>=length:
            self.offset = self.offset - length
        self.data[length-self.offset:length-self.offset] = [x]

    # needs slicing support ...
    # use list(ring) to see a list

Ken Seehof

For turn values well outside len(self.data). This doesn't come up much, but when you have a value for n in turn which is much larger than len(self.data), you may want to use the following rather than self.offset = self.offset + len(self.data). self.offset = divmod(self.offset, len(self.data))[1] as one division is a lot faster than several subtractions for a large offset.

Hold two contiguous copies of the list. I guess the implementation posted in the last comment got cut off at the <, which is interpreted by this cookbook editing system as an HTML tag.

Anyhow, seeing as the data stays the same after the Ring is created, you could keep two copies of references to the data in one much longer list. Then you only need store an offset within that data to do the turning. Slicing can be made to work without worrying about boundary conditions.

So, for the data

[1,2,3,4]

you hold a list like this:

[1,2,3,4,1,2,3]

Keep a pointer to the index the ring starts at. If you turn the ring to the index len(original_data), set the index back to zero. To get the data from the current position, just slice the list you have from the pointer to the pointer+len(original_data).