nlargest vs sorted[:k]: Top-k Lab

Intro — what this post promises

Need the top-k of N values: is heapq.nlargest(k, …) faster than sorted(…, reverse=True)[:k]? This lab varies N and k on Linux localhost, and compares a hand-rolled size-k heap (heappush / heapreplace). Complements the broader sorted/heapq/bisect lab with a top-k focus.

Related links:

• sorted vs heapq vs bisect localhost lab
• Counter vs dict tally localhost lab
• attrgetter vs getattr localhost lab
• itemgetter vs lambda sort localhost lab
• frozenset vs set membership localhost lab
• bytes vs bytearray localhost lab
• itertools vs python loops localhost lab
• perf_counter vs time localhost lab

Lab honesty (1 Oct 2026 IST): Python 3.13.5. Wall times are p50 over 9 runs. Affiliates: 0. When k ≈ N, expect sorted to catch up — selection is not free at large k.

Verdict up front (N=100 000): k=10 nlargest ~2.28 ms vs sorted slice ~16.34 ms (~7.2×); k=1 000 ~4.1×; k=10 000 ~0.97× (sorted slightly ahead). Objects with key=: nlargest ~5.3× sorted.

Arms

Lab topology

N in {10000, 100000}; k in {10, 100, 1000, 10000}
metric: p50 wall; elem/s = N / p50

Script: lab-evidence/66-nlargest-vs-sorted-slice/results/run_lab.py.

Lead table — N=100 000 ints (p50 wall)

Objects (N=100 000, k=100)

Reading it

• Small k ⇒ nlargest wins big — avoids full O(N log N) sort (~7× at k=10).
• Large k ⇒ sorted catches up — at k=10 000 (10% of N) sorted was ~1.04× nlargest; hand heap even led.
• Hand size-k heap sits between them for small k; at huge k its O(N log k) constant lost to Timsort.
• nlargest is the readable default for “top 10 / top 100” dashboards.

N=10 000 sanity check

At smaller N the same pattern holds: k=10 nlargest was about 5× sorted slice; by k=1 000 the gap shrank to roughly 1.1×. Hand size-k heap beat nlargest once k got large relative to N (k=1 000 on N=10 k) — another reminder that constants and k/N ratio matter more than the brand name on the function.

Also note ascending sorted(data)[-k:] matched reverse-slice wall time in the N=100 k arms we sampled — the cost is the full sort, not the direction flag.

Pitfalls

1. sorted(...)[:k] out of habit for tiny k — pays a full sort.
2. k growing with N — re-benchmark; crossover exists.
3. Building a huge list then slicing — memory + time.
4. Streaming data — online size-k heap / nlargest over an iterator still applies.

When to pick what

Reproduce

python3 lab-evidence/66-nlargest-vs-sorted-slice/results/run_lab.py

Evidence: /workspace/lab-evidence/66-nlargest-vs-sorted-slice/results/.

Closing

Top-k is not always a sort. On this box N=100 k / k=10 nlargest beat sorted slice ~7.2×; by k=10 k they were within ~3%. Match the algorithm to how small k really is.