queue versus list

[duncan smith]

On 20/03/2020 21:57, Barry wrote:
> 
> 
>> On 20 Mar 2020, at 00:42, duncan smith <duncan at invalid.invalid> wrote:
>>
>> Bingo. Performance is indistinguishable from that of the list. 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)
> 
> I did a performance test of list vs sequel as a fifo that had 10k elements in them.
> Then I timed insert elements at the tail and popping from the head.
> 
> Duque is 10x faster then list, rest run macOS python 3.8
> 
> Barry
> 
> 

Yes, I avoided the cost of popping elements from the head by just
iterating over the list. So the timings came out very similar. But the
deque allows me to remove those elements efficiently. It's also neat
because it lets me switch from what is basically a breadth first search
of a graph to a depth first search by simply changing popleft() to
popright(). Cheers.

Duncan