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

为什么不直接缓存它?

为什么重要 让一个助手把某样东西变快,第一个答案常常就是“加一个缓存”。有时候这是对的。但问题常常有一条规则让它变成错的,而更快的路线是少做工作,而不是记住更多的工作。

缓存是用内存去换重复的工作。当同一个问题会多次回来、答案不会过期、而且有地方保存这些答案时,它才划算。拿走其中任何一个条件,缓存就会变成一种成本:它会无限制地增长、提供过时的数据,或者永远不会命中。

缓存:一个存放已经算好的答案的地方,保存起来以便同样的问题能在不做工作的情况下再次被回答。

不需要缓存的路线

  • 预先计算一次:一次遍历,恰好构建出那些问题所需要的东西,比如累计总额。
  • 利用你得到的顺序:有序的数据让双指针或二分查找能跳过它的大部分。
  • 流式处理:保持一个累计的摘要,永远不保存整个输入。
  • 给搜索设定界限:一旦剩下的东西都不可能胜过目前最好的答案,就立刻停下。

在这个模块里,数据以一个 Tape 的形式出现,它会统计你读取的每一个值,而有些题会限制你的函数在运行时能使用的内存。这个上限是用 Python 自带的 tracemalloc 测量的,它也能看到在内置函数内部做的复制:list(tape) 和 set(tape) 并不是免费的。

import tracemalloc
tracemalloc.start()
result = my_function(tape)
peak_bytes = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()

回顾 缓存需要重复、新鲜和空间。当一道题排除了其中一个时,就去找你能跳过的工作,而不是你能记住的工作。

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

这个练习即将开放

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