python - 将一系列整数映射到单个整数

Question

我有一个函数，它接收一个整数作为输入，并根据该输入所在的范围，为其分配一个难度值。我知道这可以使用 if else 循环来完成。我想知道是否有更有效/更清洁的方法来做到这一点。

我试着做这样的事情

TIME_RATING_KEY ={
    range(0,46):1,
    range(46,91):2,
    range(91,136):3,
    range(136,201):4,
    range(201,10800):5,
}

但发现我们可以使用范围作为字典中的键(对吧？)。那么有没有更好的方法来做到这一点？

Answer 1

你可以实现一个 interval tree .这种数据结构能够返回与给定输入点相交的所有区间。在您的情况下，间隔不会重叠，因此它们总是会返回 1 个间隔。

居中区间树在 O(log n + m) 时间内运行，其中 m 是返回的区间数(在您的情况下为 1)。所以这会将复杂度从 O(n) 降低到 O(log n)。

这些区间树的思路是这样的:

• 你考虑包含所有区间的区间
• 取该区间的中心并将给定区间划分为在该点之前结束的区间、包含该点的区间和在该点之后开始的区间。
• 为在中心之前结束的区间和在中心之后开始的区间递归构造同一类树
• 保留两个排序序列中包含中心点的区间。一个按起点排序，一个按终点排序

搜索时根据中心点向左或向右移动。当您发现重叠时，您可以对要检查的排序序列使用二进制搜索(这不仅允许查找包含给定点的间隔，还允许查找与给定间隔相交或包含给定间隔的间隔)。

修改数据结构以返回特定值而不是找到的区间是微不足道的。

---

这就是说，从上下文来看，我认为您实际上不需要降低此查找的效率，您可能应该使用更简单、更易读的解决方案，因为它更易于维护并且出错的机会更少。

然而，阅读有关 mroe 高效数据结构的内容在未来可能会有用。