Card 06/ 09
Dequeuing From the Front of an Array
Removing the first element of an array shifts every other one, so each dequeue is O(n).
Removing the first element of an array makes every element behind it move one cell towards the front, so a queue that dequeues from the front of an array pays O(n) for each dequeue. This card covers the symptom, the calls that cause it in Python, Java and TypeScript, what it costs and the fix.
The symptom is a queue that gives the right answers and slows down as it grows. The trigger is a dequeue written as pop(0) on a Python list, remove(0) on a Java ArrayList or shift() on a TypeScript array, each of which returns the front element correctly. The mechanism is the array underneath. Its elements must stay in adjacent cells starting at index 0, so once the front one is removed, every element behind it is copied one cell forward.
Before the run: draining a queue of 1,000 jobs from the front of an array moves 499,500 elements. How many does draining 10,000 jobs move?
49,995,000: ten times the jobs, and about a hundred times the moves. Each removal moves every job behind it, so draining n jobs moves (n − 1) + (n − 2) + … + 0 = n(n − 1)/2 elements.
Python and Java cannot report what a removal moves, so their listings add up the elements behind the front before each removal, which is what it copies. In TypeScript the run counts directly, because the listing wraps the array in a Proxy, an object that runs a function each time a property of the array is set, and counts every element that shift writes. Its count matches the sum. Each listing drains the same jobs a second way, and the highlighted lines are the slow removal and its replacement.
Draining a queue from the front of an array, and without moving anything
from collections import deque
def drain_with_pop_zero(jobs: int) -> tuple[list[int], int]:
queue = list(range(jobs))
served: list[int] = []
moved = 0
while queue:
moved += len(queue) - 1
served.append(queue.pop(0))
return served, moved
def drain_with_popleft(jobs: int) -> list[int]:
queue = deque(range(jobs))
served: list[int] = []
while queue:
served.append(queue.popleft())
return served
for jobs in [1_000, 10_000]:
served, moved = drain_with_pop_zero(jobs)
print(f"{jobs} jobs: {moved} elements moved by pop(0)")
print(f"{jobs} jobs: popleft() serves the same order: {drain_with_popleft(jobs) == served}")1000 jobs: 499500 elements moved by pop(0)
1000 jobs: popleft() serves the same order: True
10000 jobs: 49995000 elements moved by pop(0)
10000 jobs: popleft() serves the same order: Trueimport java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
public class DequeueMoves {
record Drained(List<Integer> served, long moved) {}
static Drained drainWithRemoveZero(int jobs) {
List<Integer> queue = new ArrayList<>();
for (int job = 0; job < jobs; job++) {
queue.add(job);
}
List<Integer> served = new ArrayList<>();
long moved = 0;
while (!queue.isEmpty()) {
moved += queue.size() - 1;
served.add(queue.remove(0));
}
return new Drained(served, moved);
}
static List<Integer> drainWithPoll(int jobs) {
ArrayDeque<Integer> queue = new ArrayDeque<>();
for (int job = 0; job < jobs; job++) {
queue.offer(job);
}
List<Integer> served = new ArrayList<>();
while (!queue.isEmpty()) {
served.add(queue.poll());
}
return served;
}
public static void main(String[] args) {
for (int jobs : new int[] {1_000, 10_000}) {
Drained drained = drainWithRemoveZero(jobs);
System.out.println(jobs + " jobs: " + drained.moved() + " elements moved by remove(0)");
System.out.println(jobs + " jobs: poll() serves the same order: " + drainWithPoll(jobs).equals(drained.served()));
}
}
}1000 jobs: 499500 elements moved by remove(0)
1000 jobs: poll() serves the same order: true
10000 jobs: 49995000 elements moved by remove(0)
10000 jobs: poll() serves the same order: truefunction countingWrites(values: number[]): { items: number[]; writes: () => number } {
let writes = 0;
const items = new Proxy(values, {
set(target, property, value) {
if (property !== "length") {
writes += 1;
}
return Reflect.set(target, property, value);
},
});
return { items, writes: () => writes };
}
function jobList(jobs: number): number[] {
return Array.from({ length: jobs }, (_, job) => job);
}
function drainWithShift(jobs: number): { served: number[]; moved: number } {
const queue = countingWrites(jobList(jobs));
const served: number[] = [];
while (queue.items.length > 0) {
served.push(queue.items.shift() as number);
}
return { served, moved: queue.writes() };
}
function drainWithHead(jobs: number): { served: number[]; moved: number } {
const queue = countingWrites(jobList(jobs));
const served: number[] = [];
let head = 0;
while (head < queue.items.length) {
served.push(queue.items[head]);
head += 1;
}
return { served, moved: queue.writes() };
}
for (const jobs of [1_000, 10_000]) {
const shifted = drainWithShift(jobs);
const headed = drainWithHead(jobs);
const sameOrder = shifted.served.join(",") === headed.served.join(",");
console.log(`${jobs} jobs: ${shifted.moved} elements moved by shift()`);
console.log(`${jobs} jobs: a head index moves ${headed.moved} and serves the same order: ${sameOrder}`);
}1000 jobs: 499500 elements moved by shift()
1000 jobs: a head index moves 0 and serves the same order: true
10000 jobs: 49995000 elements moved by shift()
10000 jobs: a head index moves 0 and serves the same order: trueThe cost is quadratic. Draining a queue of n items this way moves n(n − 1)/2 elements, which is O(n²), for work that needs only O(n). At 10,000 jobs that is fifty million copies, and nothing fails to say so: the order is right, and only the time grows.
The remedy is a removal that moves nothing: popleft() on a collections.deque in Python, poll() on an ArrayDeque in Java, and in TypeScript an index to the front item that moves forward, which the run shows writing no elements at all. A stack never has this problem, because push and pop both work at the end of the array.
← → move through sections and cards