Is there non-synchronized queue in python

4
votes

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?

2
pythonpython-3.xqueue
Have you tried collections.deque? – PM 2Ring
@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
See stackoverflow.com/questions/717148/… – PM 2Ring
@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
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

2 Answers

8
votes

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.

0
votes

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()