Latency Percentiles by Nearest Rank
Problem
A dashboard reports request latency as percentiles rather than an average. Given a list of latency samples in milliseconds and a list of percentiles such as [50, 90, 99], return a dict from each percentile to its value using the nearest-rank method: sort the samples, and the p-th percentile is the sample at 1-based rank ceil(p × n / 100), where n is the number of samples. Use integer arithmetic for the rank. There are up to 1,000,000 samples.
Examples
Input: latencies = [12, 15, 11, 13, 240, 14, 12, 16, 13, 12], ps = [50, 90, 99]
Output: {50: 13, 90: 16, 99: 240}
Why: one slow request out of ten is invisible at p90 and is the whole story at p99Input: latencies = 1 to 100, ps = [50, 90, 99, 100]
Output: {50: 50, 90: 90, 99: 99, 100: 100}
Why: with 100 samples the p-th percentile is simply the p-th smallestInput: latencies = [7], ps = [50, 99]
Output: {50: 7, 99: 7}
Why: edge case, a single sample is every percentileHints
0 / 3
A percentile is a position in sorted order, so sort once and every percentile becomes a lookup.
The rank is ceil(p × n / 100). In integers that is (p × n + 99) // 100, which avoids floating-point surprises such as 0.29 × 100 not being exactly 29.
Ranks are 1-based and the list is 0-based, so read index rank - 1. Clamp the rank to at least 1 so a tiny percentile on a small list still returns the smallest sample.
Solution
Averages hide the slow tail that users actually feel, which is why dashboards track p50, p90 and p99, and the first example shows it: the mean of those ten samples is about 36 ms, a number no request came close to. Nearest rank is the simplest percentile definition that always returns a real sample: sort, compute the rank ceil(p × n / 100) with integer arithmetic, and read that position. Clamping the rank at 1 keeps very small percentiles valid on short lists. Sorting dominates, so time is O(n log n + q) for q percentiles, and space is O(n) for the sorted copy.
def percentiles(latencies, ps):
ranked = sorted(latencies)
n = len(ranked)
return {p: ranked[max(1, (p * n + 99) // 100) - 1] for p in ps} # ceil(p * n / 100), 1-based
print(percentiles([12, 15, 11, 13, 240, 14, 12, 16, 13, 12], [50, 90, 99])) # -> {50: 13, 90: 16, 99: 240}
print(percentiles(list(range(1, 101)), [50, 90, 99, 100])) # -> {50: 50, 90: 90, 99: 99, 100: 100}
print(percentiles([7], [50, 99])) # -> {50: 7, 99: 7}Stuck on the idea rather than the code? Observability Basics covers it.