6

I am practicing doing programming competitions using python(actually pypy3). For a problem I need to use a queue - I only need to put at one end and pop from the other. From what I found in the documentation it seems I have two options queue.Queue and queue.deque. I first tried the problem using queue.Queue, but my solution exceeded the time limit. Then I switched to queue.deque and I passed the problem(though close to the limit).

From the documentation it seems both containers are thread safe(well at least for some operations for deque) while for my situation I will never use more than one thread. Is there a simple non-synchronized queue built-in in python?

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • Have you tried [`collections.deque`](https://docs.python.org/3/library/collections.html#deque-objects)? – PM 2Ring Feb 20 '16 at 13:25
  • @PM2Ring it seems this container is also synchronized: `Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.` – Ivaylo Strandjev Feb 20 '16 at 13:27
  • See http://stackoverflow.com/questions/717148/queue-queue-vs-collections-deque – PM 2Ring Feb 20 '16 at 13:30
  • @PM2Ring I see so the operations do not require locking. So it seems this structure may do the trick. The question you link to does not compare colllection.deque to queue.deque. How do they compare? What is the difference? – Ivaylo Strandjev Feb 20 '16 at 13:33
  • [One of the answers](http://stackoverflow.com/a/20330499/4014959) does a comparison between `collections.deque` and `Queue.Queue`; the former is more than twice as fast. – PM 2Ring Feb 20 '16 at 13:36
  • @PM2Ring I think I may be confused, I thought there are two different containers- queue.deque and collections.deque and I was asking for a comparison between them. – Ivaylo Strandjev Feb 20 '16 at 13:38
  • 1
    `queue.Queue` (aka `Queue.Queue` in Python 2) uses a `collections.deque` internally; if you don't need the special features of `queue.Queue` you should be using a plain `collections.deque`. – PM 2Ring Feb 20 '16 at 13:48
  • @PM2Ring please consider adding an answer to the question with what you've explained – Ivaylo Strandjev Feb 20 '16 at 14:00

2 Answers2

10

The deque certainly does not do synchronization; the documentation just states that the appends and pops are guaranteed to be thread-safe due to them being atomic. In CPython in particular there is no locking besides the Global Interpreter Lock. If you need a double-ended queue, or say FIFO, that is what you should use. If you need a LIFO stack, use a list. Internally the deque implementation uses a doubly-linked list of fixed-length blocks.

The queue.Queue uses a deque internally; in addition, it uses a mutex to guard those remaining operations that are not implemented atomically by deque.

Thus your problem is not the choice of deque, but quite probably some other aspect of your algorithm.

Antti Haapala -- Слава Україні
  • 129,958
  • 22
  • 279
  • 321
0

You can use two ordinary lists (as stacks) to simulate a queue.

class Queue:
    def __init__(self):
        self.l1 = []   # Add new items here
        self.l2 = []   # Remove items here

    # O(1) time - simple stack push
    def enqueue(self, x):
        self.l1.append(x)

    # O(1) when l2 is not empty
    # O(k) if l2 is empty, but k is bounded by the number
    # of preceding calls to enqueue. Abusing the notation a bit,
    # you can think of the average for each call in a series to be
    # (k*O(1) + O(k))/k = O(1)
    def dequeue():
        if not self.l2:
            self.l2 = self.l1[::-1] #  Copy and reverse
            self.l1 = []
        return self.l2.pop()
chepner
  • 497,756
  • 71
  • 530
  • 681