不用缓存:继承的折扣
为什么重要 “它在重复工作,所以把答案记下来”是编程中最强的习惯之一,不管是人还是 AI。有时候,这项工作根本就不需要重复。
一家商店的类别构成一棵树:Garden 在 Home 下面,Tools 在 Garden 下面,以此类推。一位市场经理可以给任意一个类别设置折扣,它会应用到它下面的所有东西上,除非一个更近的类别设置了自己的折扣。结账时会一次查询成千上万个类别的有效折扣。
数据
parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25} # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]对于沿着树反复往上走,显而易见的修复办法是缓存。在这道题里,缓存是被禁止的。去找一种从一开始就不会重复工作的办法。
编写 effective_discounts(parents, own, queries)。parents 把每个类别映射到它的父类别,对于顶层类别则映射到 None(可能有好几个,而且字典没有特定的顺序)。own 把某些类别映射到它们自己的折扣。对于 queries 中的每一个类别,返回从它自己开始、在它通往顶层的路径上最近的那个在 own 中有折扣的类别的折扣;如果都没有,就是 0。规则:不用缓存或备忘:不用 functools 的缓存装饰器,不用任何包含 "cache" 或 "memo" 的名字,也不要在查询要求时才算出答案并把它们保存起来(那是换了个名字的备忘)。先遍历整棵树,然后再读查询。预算:对于 3,000 个类别、最深几百层的树和 20,000 次查询,最多 500,000 步(steps())。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。