What is the best queue implemetation in Python?

Discussion in 'Python' started by hg, Feb 22, 2007.

  1. hg

    hg Guest

    John Machin wrote:

    > On Feb 23, 11:12 am, "John" <> wrote:
    >> I want to write a code for Breadth First Traveral for Graph, which needs
    >> a queue to implement.
    >>
    >> I wonder that for such a powerful language as Python, whether there is a
    >> better and simpler implementation for a traditional FIFO queue?
    >>

    >
    > Better and simpler than *WHAT*?


    Sorry, but you do that all the time ... "ask the question as you know the
    answer, otherwise shut the f u ..."

    Can't you assume for a second that other people do not have your wonderful
    brain and still have to make it through 60+ years of life of learning ?

    hg
    hg, Feb 22, 2007
    #1
    1. Advertising

  2. hg

    hg Guest

    hg wrote:

    > f u


    "f o" of course
    hg, Feb 22, 2007
    #2
    1. Advertising

  3. hg

    John Guest

    I want to write a code for Breadth First Traveral for Graph, which needs a
    queue to implement.

    I wonder that for such a powerful language as Python, whether there is a
    better and simpler implementation for a traditional FIFO queue?


    Thanks!
    John, Feb 23, 2007
    #3
  4. hg

    John Machin Guest

    On Feb 23, 11:12 am, "John" <> wrote:
    > I want to write a code for Breadth First Traveral for Graph, which needs a
    > queue to implement.
    >
    > I wonder that for such a powerful language as Python, whether there is a
    > better and simpler implementation for a traditional FIFO queue?
    >


    Better and simpler than *WHAT*?
    John Machin, Feb 23, 2007
    #4
  5. hg

    John Guest

    Than C or PASCAL
    I mean, list or dictionary in Python are so powerful than the traditional
    array. Maybe I can make use of it?


    "John Machin" <> wrote in message
    news:...
    > On Feb 23, 11:12 am, "John" <> wrote:
    > > I want to write a code for Breadth First Traveral for Graph, which needs

    a
    > > queue to implement.
    > >
    > > I wonder that for such a powerful language as Python, whether there is a
    > > better and simpler implementation for a traditional FIFO queue?
    > >

    >
    > Better and simpler than *WHAT*?
    >
    >
    >
    >
    John, Feb 23, 2007
    #5
  6. hg

    John Machin Guest

    On Feb 23, 11:24 am, "John" <> wrote:
    > Than C or PASCAL
    > I mean, list or dictionary in Python are so powerful than the traditional
    > array. Maybe I can make use of it?


    Well, you could wite your own queue manager using Python lists,
    but ...

    You have this strange reluctance to look in the documentation. Have
    you tried Google? Try http://docs.python.org/lib/deque-objects.html

    Or perhaps you want/need the Queue module or the heapq module.

    *You* find them and *you* work out what is best for *your* needs.

    If you have a question that you could not answer yourself, then ask it
    here.

    HTH,
    John





    >
    > "John Machin" <> wrote in message
    >
    > news:...
    >
    > > On Feb 23, 11:12 am, "John" <> wrote:
    > > > I want to write a code for Breadth First Traveral for Graph, which needs

    > a
    > > > queue to implement.

    >
    > > > I wonder that for such a powerful language as Python, whether there is a
    > > > better and simpler implementation for a traditional FIFO queue?

    >
    > > Better and simpler than *WHAT*?
    John Machin, Feb 23, 2007
    #6
  7. hg

    Duncan Smith Guest

    John wrote:
    > I want to write a code for Breadth First Traveral for Graph, which needs a
    > queue to implement.
    >
    > I wonder that for such a powerful language as Python, whether there is a
    > better and simpler implementation for a traditional FIFO queue?
    >


    For a BFS I coded up a while back iterating over a list of nodes (and
    appending nodes to the list as dictated by the algorithm) did the job.

    Duncan
    Duncan Smith, Feb 23, 2007
    #7
  8. hg

    James Stroud Guest

    John Machin wrote:
    > On Feb 23, 11:24 am, "John" <> wrote:
    >
    >>Than C or PASCAL
    >>I mean, list or dictionary in Python are so powerful than the traditional
    >>array. Maybe I can make use of it?

    >
    >
    > Well, you could wite your own queue manager using Python lists,
    > but ...
    >
    > You have this strange reluctance to look in the documentation. Have
    > you tried Google? Try http://docs.python.org/lib/deque-objects.html
    >
    > Or perhaps you want/need the Queue module or the heapq module.
    >
    > *You* find them and *you* work out what is best for *your* needs.
    >
    > If you have a question that you could not answer yourself, then ask it
    > here.
    >
    > HTH,
    > John


    You could do yourself a favor and not answer. You would also be sparing
    the rest of us your rude tone.

    James
    James Stroud, Feb 23, 2007
    #8
  9. hg

    Guest

    John:
    > I want to write a code for Breadth First Traveral for Graph, which needs a
    > queue to implement.


    For that purpose I have used the good deque that you can find in
    collections in the standard library. It's very good for queues, and
    it's a bit faster than regular lists for stacks too.

    Bye,
    bearophile
    , Feb 23, 2007
    #9
  10. > For that purpose I have used the good deque that you can find in
    > collections in the standard library. It's very good for queues, and
    > it's a bit faster than regular lists for stacks too.


    you mean *much* faster (since a list is a reference array so pop(0) is
    O(n) operation)

    never use a list as queue if len(queue) > 10000

    === benchmark

    $ time ./deque_queue.py
    34359607296

    real 0m0.286s
    user 0m0.264s
    sys 0m0.016s

    $ time ./list_queue.py
    34359607296

    real 1m20.915s
    user 1m18.649s
    sys 0m0.396s


    === the sources

    --- deque_queue.py:
    #!/usr/bin/python2.5

    from collections import deque

    def f(n):
    sum = 0
    queue = deque()
    for i in range(n):
    queue.append(i)
    while queue:
    sum += queue.popleft()
    print sum

    if __name__=='__main__':
    f(1<<18)

    --- list_queue.py:
    #!/usr/bin/python2.5

    def f(n):
    sum = 0
    queue = list()
    for i in range(n):
    queue.append(i)
    while queue:
    sum += queue.pop(0)
    print sum

    if __name__=='__main__':
    f(1<<18)
    Szabolcs Nagy, Feb 23, 2007
    #10
  11. hg

    Guest

    On Feb 22, 12:40 pm, hg <> wrote:
    > John Machin wrote:
    > > On Feb 23, 11:12 am, "John" <> wrote:
    > >> I want to write a code for Breadth First Traveral for Graph, which needs
    > >> a queue to implement.

    >
    > >> I wonder that for such a powerful language as Python, whether there is a
    > >> better and simpler implementation for a traditional FIFO queue?

    >
    > > Better and simpler than *WHAT*?

    >
    > Sorry, but you do that all the time ... "ask the question as you know the
    > answer, otherwise shut the f u ..."
    >
    > Can't you assume for a second that other people do not have your wonderful
    > brain and still have to make it through 60+ years of life of learning ?
    >
    > hg




    Um... first off, you have to admit that a lot of what is posted
    on the internet in general and even on groups like this is rambling,
    poorly thought out, missing necessary context, and just generally a
    mess and hard to understand.

    So maybe a little peer pressure on folks to clean up their posts and
    try
    to express themselves clearly isn't such a bad thing.

    And finally, let's face it: if the internet ever does cease to be a
    place
    where you can see crotechety know-it-all programmers roasting clueless
    noobs,
    then, honestly, what is the point of owning a computer?
    , Feb 23, 2007
    #11
    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.
Similar Threads
  1. anupam

    CORDIC implemetation

    anupam, Dec 1, 2005, in forum: VHDL
    Replies:
    2
    Views:
    744
    anupam
    Dec 2, 2005
  2. pete kirkham
    Replies:
    0
    Views:
    3,420
    pete kirkham
    Jun 27, 2003
  3. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    668
    Russell Warren
    Jun 27, 2006
  4. News123
    Replies:
    0
    Views:
    671
    News123
    Jun 26, 2009
  5. Kris
    Replies:
    0
    Views:
    466
Loading...

Share This Page