[SOLVED] How to use collections.deque most effectively (popleft vs. appendleft)

How to use collections.deque most effectively (popleft vs. appendleft)

I have been learning queues as I study data structures in Python and wanted to ask a question regarding its use.

I suppose there are two ways append/pop from a queue. First way would be to use deque.append() and deque.popleft(). Another way would be to use deque.appendleft() and deque.pop(). Is there a performance difference between the two? If not, which one is used more often from your experience? Do you recommend one over another for some other reason?

From my point of view, they essentially do the same thing as they both implement first-in-first-out. Your input would be much appreciated!

Solution

According to the docs:

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.

So there is no asymptotic difference between the two options; either way, your "enqueue" and "poll" operations are both done in constant time. This is to be expected, since the whole point of a deque (double-ended queue) is to have efficient add and remove operations on both sides.

Empirical results using timeit confirm there is basically no difference:

from collections import deque

def append_popleft():
    d = deque()
    for i in range(10000):
        d.append(i)
    for j in range(10000):
        d.popleft()

def appendleft_pop():
    d = deque()
    for i in range(10000):
        d.appendleft(i)
    for j in range(10000):
        d.pop()

import timeit
t = timeit.timeit(append_popleft, number=10000)
print('append / popleft:', t)
t = timeit.timeit(appendleft_pop, number=10000)
print('appendleft / pop:', t)

Output:

append / popleft: 12.000681700999849
appendleft / pop: 11.937629571999423