课程大纲 第 14 课,共 148 课 · 对决的规则
对决的规则

你的第一场对决:慢速磁盘

为什么重要 对“统计某个范围内的东西”的第一个答案,是去看每一样东西。这在数据很大、读取它要花钱或花时间之前都没问题。而在这里,它确实要花。

一个传感器以整秒时间戳记录事件,已经排好了序。日志存放在一块慢速、按量计费的磁盘上:你读取的每一个值都要收费。分析师们给你发来一批时间窗口,想知道每个窗口里有多少个事件。

在查任何资料之前先解题。当你通过时,你会并排看到一个 AI 助手最可能写出的答案,以及一位专家的路线。

数据

from creative.budget import Tape
tape = Tape([3, 7, 7, 12, 40])   # sorted timestamps, every read counted
queries = [(0, 8), (7, 13)]       # windows: start included, end excluded
# window_counts(tape, queries) -> [3, 3]
轮到你了

编写 window_counts(tape, queries)。tape 是一个由有序的整数时间戳组成的 Tape(允许重复)。queries 是一个由 (start, end) 对组成的列表。返回一个列表,对每个窗口给出有多少个时间戳 t 满足 start <= t < end。预算:在 100,000 个事件和 1,000 个窗口的情况下,你最多只能从 tape 中读取 60,000 个值。len(tape) 是免费的。

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

这个练习即将开放

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