lesson 78 Collections & Itertools · intermediate

Queues and recent windows: deque

A deque is a list built for both ends: add on the right and take from the left for a fair queue, and give it a `maxlen` to keep only the newest few items.

You'll be able to

Run a first-in-first-out queue with append and popleft
Explain why list.pop(0) gets slow on long lists and popleft does not
Keep only the newest n items with deque(maxlen=n)

The idea

A support desk handles tickets in the order they arrive: new ones join the back, the agent takes the oldest from the front. That is a queue, first in, first out.

A list can do it with append and pop(0), but pop(0) has a hidden cost: every item behind the first one moves one place forward, so with a hundred thousand waiting tickets each pop(0) shifts a hundred thousand items. deque (from collections, said *deck*, short for *double-ended queue*) is built so that adding and removing at either end takes the same tiny time however long it is: append and popleft, and also appendleft and pop.

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · A support queue

from collections import deque

queue = deque(["T-101", "T-102"])
queue.append("T-103")
first = queue.popleft()
print("handling", first)
queue.appendleft("T-099")
print(queue)
print(len(queue), queue[0])

Taking from an empty queue is an error, so a loop that drains a queue checks it first: while queue: stops when it is empty.

example-2.py · Taking from an empty queue

from collections import deque

queue = deque(["T-101"])
print(queue.popleft())
print(queue.popleft())

The second job a deque does well is a window: keep only the newest few items. With maxlen, appending to a full deque silently drops the item at the other end. A rolling average of page-load times needs exactly that.

example-3.py · A rolling average of load times

from collections import deque

def rolling_average(times, window):
    recent = deque(maxlen=window)
    averages = []
    for ms in times:
        recent.append(ms)
        averages.append(sum(recent) / len(recent))
    return averages

print(rolling_average([210, 190, 260, 240], 2))

When to use it: queues of work (tickets, print jobs, pages to visit), and "the last N" (recent searches, a rolling average, undo history). Mistakes to avoid: pop() takes from the right, so using it instead of popleft() serves the newest item first; reading items in the middle of a long deque is slower than in a list, so a deque is not a general list replacement; and popping from an empty deque raises IndexError.

Review

deque adds and removes quickly at both ends: append + popleft is a fair queue.
list.pop(0) shifts every remaining item; popleft doesn't.
deque(maxlen=n) keeps the newest n items, dropping from the other end.
Next: itertools.groupby, which walks runs of equal neighbours in ordered data.

Practise this