课程大纲 第 136 课,共 148 课 · 打败你的幽灵
打败你的幽灵

不用排序:延迟报告

为什么重要 “先排序”能把许多问题变成简单的问题,所以它会变成一种自动的反应。有些数据的形状决定了排序是在绕远路。

一个服务记录每个请求花了多长时间,以整数毫秒为单位。请求在 10 秒时超时,所以每个值都在 0 到 10,000 之间。每分钟,一个任务会把大约 20,000 个值变成值班仪表盘上的数字:中位数、第 90 和第 99 百分位数,以及最坏的值。

最近秩百分位数:第 p 百分位数是满足“至少有 p% 的值小于或等于它”的最小值。有 20 个值时,第 90 百分位数就是第 18 小的那个。

数据

values = [120, 85, 3000, 95, 110, 90, 100, 105, 80, 130]
# latency_report(values) -> {"p50": 100, "p90": 130, "p99": 3000, "max": 3000}

在这道题里,排序是被禁止的,不管是手工排序还是用库排序。看看你对这些值了解些什么。

轮到你了

编写 latency_report(values)。values 是一个非空的整数列表,取值从 0 到 10,000(大约 20,000 个)。返回 {"p50", "p90", "p99", "max"}:最近秩的第 50、第 90 和第 99 百分位数(满足至少 p% 的值小于或等于它的最小值),以及最大值。不要修改这个列表。规则:不能排序:不能用 sorted()、.sort()、bisect.insort,也不能导入 heapq 或 statistics(它们会替你排序)。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。