fifo queue

Discussion in 'Python' started by drochom, Mar 18, 2007.

  1. drochom

    drochom Guest

    hi,

    how would u improve this code?

    class queue:
    def __init__(self, size=8):
    self.space = size
    self.data = [None]*self.space
    self.head = 0
    self.tail = 0
    self.len = 0
    def __len__(self): return self.len
    def push(self, x):
    if self.len==self.space:
    self.data.extend( self.data[:self.tail] )
    self.data.extend( [None]* (self.space-self.tail) )
    self.tail+=self.space
    self.space*=2
    self.data[self.tail]=x
    self.tail+=1
    if self.tail==self.space:
    self.tail=0
    self.len+=1
    def pop(self):
    if self.len:
    elem = self.data[self.head]
    self.head+=1
    if self.head==self.space:
    self.head=0
    return elem
    def top(self):
    if self.len==0:
    raise Exception, 'queue is empty'
    return self.data[self.head]

    thx in adv.
    drochom, Mar 18, 2007
    #1
    1. Advertising

  2. drochom

    Paul Rubin Guest

    Unless the queue is really large, just use the pop operation to get
    stuff off the top of the queue. That causes O(n) operations but it
    should be fast if n is small.

    class queue(list):
    push = append
    def pop(self):
    return list.pop(self,0)

    should do about what you wrote.
    Paul Rubin, Mar 18, 2007
    #2
    1. Advertising

  3. drochom schreef:
    > hi,
    >
    > how would u improve this code?
    >
    > class queue:
    > ...


    I think I'd use collections.deque [1] instead of using a ring buffer as
    you're doing (I think) and doing a lot of manual bookkeeping.

    [1] http://docs.python.org/lib/deque-objects.html



    --
    If I have been able to see further, it was only because I stood
    on the shoulders of giants. -- Isaac Newton

    Roel Schroeven
    Roel Schroeven, Mar 18, 2007
    #3
  4. Paul Rubin <http://> wrote:

    > Unless the queue is really large, just use the pop operation to get
    > stuff off the top of the queue. That causes O(n) operations but it
    > should be fast if n is small.
    >
    > class queue(list):
    > push = append
    > def pop(self):
    > return list.pop(self,0)
    >
    > should do about what you wrote.


    If it IS large, then:

    import collections
    class queue(collections.deque):
    push = collections.deque.append
    pop = collections.deque.popleft

    could be even better.


    Alex
    Alex Martelli, Mar 18, 2007
    #4
  5. drochom

    Tim Roberts Guest

    "drochom" <> wrote:
    >
    >how would u improve this code?


    I would add at least one comment...
    --
    Tim Roberts,
    Providenza & Boekelheide, Inc.
    Tim Roberts, Mar 20, 2007
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page