efficient idiomatic queue?
Raymond Hettinger
othello at javanet.com
Tue Jan 15 08:08:47 EST 2002
"Alex Martelli" <aleax at aleax.it> wrote in message
news:a20q9p$ej5$1 at serv1.iunet.it...
> class fifo:
> def __init__(self):
> self.data = []
> self.first = 0
> def head(self):
> return self.data[self.first]
> def pop(self):
> self.first += 1
> if self.first > len(self.data)/2:
> self.data = self.data[self.first:]
> self.first = 0
> def append(self, value):
> self.data.append(value)
>
>
> Alex
>
The Python Cookbook has an algorithm for O(n) FIFO queues submitted by
Sébastien Keim.
His approach is interesting and brilliant,
See: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68436
After tightening the code a bit, it looks a like this:
class Fifo:
stored = [None]
stored[0] = stored
def append(self,data): # to inside
if len(self.stored) == 1:
return self.stored.append(data)
self.stored[0] = self.stored = [self.stored[0], data]
def pop(self): # from outside
whole = self.stored[0]
self.stored[0] = whole[0]
return whole[1]
Raymond Hettinger
More information about the Python-list
mailing list