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

把搜索限制在要紧的那 200 个地址里

为什么重要 “找出最好的那一个”听起来像是“看每一个”。常常有一个简单的界限会告诉你,列表中再往下的东西都不可能胜出,于是你就可以停下了。

一个订单可以从 50,000 个仓库中的任何一个发货。列表按到顾客的距离排序到达,最近的在前。运费是每公里 12 便士,每个仓库还会加上它自己的处理费,而处理费从不超过 5,000 便士。每一条仓库记录都位于一个很慢的库存服务后面,所以你读取的每一条记录都有成本。

(distance_km, fee, name)   # cost = distance_km * 12 + fee
轮到你了

编写 cheapest(tape)。tape 是一个非空的 Tape,由按 distance_km 升序排列的 (distance_km, fee, name) 记录组成。成本是 distance_km * 12 + fee,而每一笔处理费都在 0 到 5,000 之间。返回最便宜的那个仓库的 name;如果成本打平,就选更近的那个;如果这也打平,就选列表中更靠前的那个。预算:在 50,000 条记录中最多只能读取 2,000 条。len(tape) 是免费的。

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

这个练习即将开放

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