不用排序:延迟报告
为什么重要 “先排序”能把许多问题变成简单的问题,所以它会变成一种自动的反应。有些数据的形状决定了排序是在绕远路。
一个服务记录每个请求花了多长时间,以整数毫秒为单位。请求在 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(它们会替你排序)。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。