queue versus list

[Antoon Pardon]

Op 20/03/20 om 02:10 schreef Cameron Simpson:
> On 20Mar2020 00:37, duncan smith <duncan at invalid.invalid> wrote:
>
>> Thread
>> safety is unimportant (for my purposes), but the docs at
>> https://docs.python.org/2/library/collections.html#collections.deque
>> state "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". Looking at the output from the
>> profiler for my implementation with the queue it looks like a deque is
>> being used but there's various other stuff happening relating to thread
>> safety. Is the lesson from this that if all you're doing is appending
>> and popping, then use a deque (rather than a queue) even if you want
>> thread safety? (It makes quite a difference in performance for my use
>> case.) Cheers.
>
> A deque will change the ordering of the elements you process. Your 
> list loop behaves in FIFO order, as does the queue. A dequeue (you 
> you're doing a heappush and a heappop) will issue you the lowest 
> current element on each iteration. If you merely need to process all 
> the elements you're good. If the order matters you need to consider that.
>
> A deque, being thread safe, will be using a lock. There will be a 
> (quite small) overhead for that.


This doesn't seem correct. A deque is used to simulate a stack or a 
queue. It doesn't use heappush or heappop.

Antoon.