课程大纲 第 54 课,共 148 课 · 不用缓存的速度
不用缓存的速度

预先计算一次

为什么重要 “两点之间 X 的总和”是报表代码中最常见的问题之一。通过把范围加起来逐个回答很慢;为每一个点保存一个总额又可能太大。在这两者之间有一条路线。

一家商店在一个按量计费的存储上保存着 60,000 天的销售额,以一个 Tape 的形式交给你。财务部门一次发来一批 50 个问题:“从第 a 天到第 b 天的总销售额”。你运行在一个空闲内存非常少的小型工作进程上。

累计总额(前缀和):一个位置之前所有东西的总和。一个窗口的总额,就是它结束处的累计总额减去它开始处的累计总额。

sales = [5, 1, 4, 2, 8]
# running totals before each position: 0, 5, 6, 10, 12, 20
# window (1, 4) = 12 - 5 = 7
轮到你了

编写 range_totals(tape, queries)。tape 是一个由每日销售额(整数)组成的 Tape。queries 是一个由满足 0 <= start <= end <= len(tape) 的 (start, end) 对组成的列表。返回一个列表,按给出的顺序,给出每个查询的 tape[start:end] 的总额。预算:最多只能读 tape 一遍(60,000 天和 50 个查询,就是 60,100 次读取),并且在你的函数运行时最多使用 100,000 字节的工作内存(用 tracemalloc 测量;为每一天保存一个累计总额,甚至只是一个由 60,000 个值组成的普通列表,都远远超过 100,000 字节)。这些问题都是一起到达的,在你读取数据之前。

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

这个练习即将开放

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