Sliding maximum: naive, deque and panes

Measure your machineNeeds Python with NumPy

Problem

A sliding maximum asks for the largest of the last w values at every step. Recomputing it each step costs w comparisons per value. A monotonic deque keeps only the values that could still become the maximum, in decreasing order: each value enters once and leaves once, so the cost is amortised O(1) per value whatever w is. Panes split the stream into chunks of w/10, compute each chunk's maximum once, and combine the 10 pane maxima per output: more work than the deque, but each pane is independent, so the work splits across threads or machines.

Implement the sliding maximum three ways: naive (max over the last w values each step), the monotonic deque from Ordering structures, and panes. For w = 10,000 and 10 million values, measure time. Feed the deque a decreasing sequence and an increasing one to see best and worst shapes of its staircase.

The naive version is timed on its first 20,000 values only (the full run would take hours); the pane version is vectorised with NumPy, the other two are plain Python.

The question. How much faster is the deque than the naive version, how close do panes come, and does the input shape change the deque's cost?

Predict

With a window of w = 10,000, how many times faster is the monotonic deque than recomputing the maximum over the window?

Under 30×30 to 300×300 to 3,000×About w (3,000× or more)

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

sliding-maximum-naive-deque-and-panes.py65 linesDownload

View the code

sliding-maximum-naive-deque-and-panes.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Sliding maximum: naive, monotonic deque, and panes.

The maximum of the last w values at every step over n values, three ways:
max() over the window, a monotonic deque, and panes (maxima of w/10-value
chunks, 10 combined per output). Then the deque on decreasing and increasing
input, its worst and best shapes.
"""
import argparse, json, random, time
from collections import deque
import numpy as np

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--values", type=int, default=10_000_000, help="Values in the stream.")
p.add_argument("--window", type=int, default=10_000, help="Window w.")
p.add_argument("--naive-values", type=int, default=20_000, help="Values the naive version processes (it is w times slower).")
p.add_argument("--seed", type=int, default=0, help="Random seed.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()
rng = np.random.default_rng(args.seed)
w = args.window
xs = rng.random(args.values).tolist()

def naive(v):
    return [max(v[i - w + 1: i + 1]) for i in range(w - 1, len(v))]

def deq(v):
    d, out = deque(), []
    for i, x in enumerate(v):
        while d and v[d[-1]] <= x: d.pop()
        d.append(i)
        if d[0] <= i - w: d.popleft()
        if i >= w - 1: out.append(v[d[0]])
    return out

def panes(v):
    pw = w // 10
    pm = [max(v[i:i + pw]) for i in range(0, len(v) - pw + 1, pw)]           # each pane aggregated once
    return [max(pm[j - 9: j + 1]) for j in range(9, len(pm))]                 # 10 pane maxima per output (outputs at pane edges)

def timed(fn, v):
    t = time.perf_counter(); out = fn(v); return time.perf_counter() - t, out

rows = []
tn, outn = timed(naive, xs[: args.naive_values + w])
per_n = tn / len(outn)
td, outd = timed(deq, xs); tp, _ = timed(panes, xs)
assert outn == outd[: len(outn)]
for name, per in (("naive max over the window", per_n), ("monotonic deque", td / len(outd)), ("panes of w/10", tp / (len(outd)))):
    rows.append({"method": name, "ns_per_value": per * 1e9}); print(f"{name:<28} {per * 1e9:10.1f} ns per value")
shapes = []
for shape, v in (("decreasing", list(range(args.values // 10, 0, -1))), ("increasing", list(range(args.values // 10)))):
    t, _ = timed(deq, v); shapes.append({"input": shape, "ns_per_value": t / len(v) * 1e9})
    print(f"deque on {shape} input: {t / len(v) * 1e9:.1f} ns per value")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"methods": rows, "shapes": shapes, "summary": [{"naive_over_deque": rows[0]["ns_per_value"] / rows[1]["ns_per_value"],
                   "panes_over_deque": rows[2]["ns_per_value"] / rows[1]["ns_per_value"]}]}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.

Terminal

uv run sliding-maximum-naive-deque-and-panes.py
uv run sliding-maximum-naive-deque-and-panes.py --help     # every knob

Knobs
Knob · default	What it changes
--values10,000,000	Values in the stream.
--window10,000	Window w.
--naive-values20,000	Values the naive version processes (it is w times slower).
--seed0	Random seed.

Our run

Sliding maximum, w = 10,000

Sliding maximum, w = 10,000
Method	ns per value
naive max over the window	86.4K
monotonic deque	189
panes of w/10	8.98

The deque on two input shapes

The deque on two input shapes
Input	ns per value
decreasing	152
increasing	152

Reference runApple M2 · 8 cores · 8 GB

Output · uv run sliding-maximum-naive-deque-and-panes.py

naive max over the window       86383.4 ns per value
monotonic deque                   189.5 ns per value
panes of w/10                       9.0 ns per value
deque on decreasing input: 152.0 ns per value
deque on increasing input: 152.3 ns per value

macOS 26.6.2 · Python 3.13.3 · numpy 2.5.4 · run 2026-10-20

What we found

The naive maximum cost 86.4K ns per value and the deque 189: 456× faster, short of w = 10,000 because Python's built-in max over a slice runs in C while the deque runs in the interpreter. The pane version came out fastest of all, at 8.98 ns per value, because NumPy computed the pane maxima in vectorised C; that contradicts "the deque is fastest in one thread", but only because the two ran in different languages. On decreasing and increasing input the deque cost the same (152 and 152 ns): the staircase is long in one case and a single step in the other, yet every value is still pushed and popped once.

Read it

The deque's amortised bound is what makes a sliding window affordable at any width: its cost per value does not depend on w. Panes trade a constant factor of work for independence, which is what a distributed engine needs: a pane's maximum can be computed where the data lives and combined later, and the same panes serve every window that overlaps them.

When comparing algorithms, compare them in the same runtime. Here the language boundary moved the result by more than the algorithms differ.