Welcome, guest | Sign In | My Account | Store | Cart

In some applications, it's advantageous to be able to define a circular data structure (a structure in which the last element is a pointer to the first). Python lists make it easy to make such a beast. A list is an ordered sequence of elements, so implementing a "ring" as a Python list is easy. "Turning" the ring consists of removing the last element from the list and placing it in the list's beginning slot. We can encapsulate this behavior in a class, which is shown below as the "Ring" class.

Python, 24 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24``` ```class Ring: def __init__(self, l): if not len(l): raise "ring must have at least one element" self._data = l def __repr__(self): return repr(self._data) def __len__(self): return len(self._data) def __getitem__(self, i): return self._data[i] def turn(self): last = self._data.pop(-1) self._data.insert(0, last) def first(self): return self._data[0] def last(self): return self._data[-1] ```

We'll use the Ring class in the interactive interpreter:

``````>>> l = [{1:1}, {2:2}, {3:3}]
``````

(we prime a list for use in the ring)

``````>>> r = Ring(l)
>>> r
[{1: 1}, {2: 2}, {3: 3}]
>>> r.first()
{1: 1}
>>> r.last()
{3: 3}
>>> r.turn()
``````

(we "turn" the ring)

``````>>> r
[{3: 3}, {1: 1}, {2: 2}]
``````

(note that the element that used to be in the "last" position ({3:3}) is now in the "first" position.

``````>>> r.turn()
>>> r
[{2: 2}, {3: 3}, {1: 1}]
``````

Michael Chermside 20 years, 8 months ago

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

Chris McDonough (author) 20 years, 8 months ago

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

Ken Seehof 20 years, 8 months ago

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

Joal Heagney 20 years, 2 months ago

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.

Steve Alexander 19 years, 10 months ago

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).

 Created by Chris McDonough on Tue, 13 Mar 2001 (PSF)

### Required Modules

• (none specified)