Блог пользователя nhtrnm

Python queue-like data structure
Автор nhtrnm, история, 8 лет назад, По-английски

I recently decided to work with Python 3 and I have questions regarding queues. As far as I understand the queue in the queue library is adapted for multithreaded programs. I assume that that queue is not as efficient as the simple queue (if I am wrong please correct). Therefore, I found that there is a deque from collections library which resembles deque in C++. Am I right that that's what competitive Python programmers use (for example, BFS problems)?

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I program mostly in pypy and this is what i used for bfs.

Deque with popleft can easily replace queue and is fast for unbounded queue as it require no locking.


from collections import deque
 
def bfs(g, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(g[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])

Another Alternative is to use Queue module itself

import Queue # In python 3 it is 'queue'
q = Queue() # queue object created
# use q in your bfs code

Useful Link

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    deque is the right queue for algorithms. Don't use Queue it is for communication between threads.

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

You can read the source code for Python 3 queue module here.

As you can see from source, Queue class adds locks for put and get methods. If you just want a simple double ended queue, you should use deque from collections module. Even Queue uses deque internally.

You are right in assuming that Queue is not as efficient as deque and deque is what Python programmers use.

→ Ответить