python - OrderedDict 中第一个超过阈值的键

Question

假设我有一个 OrderedDict:

a = OrderedDict([(5, 'a'), (7, 'b'), (10, 'c')])

是否有一种有效的方法来获取键超过特定阈值的第一个值，而不循环遍历所有键？

示例:

>>> get_first(a, 6)
'a'
>>> get_first(a, 3)
None
>>> get_first(a, 8)
'b'

我想避免自己实现二分搜索。是否有有效的开箱即用的实现？

Answer 1

您不必自己实现二分搜索，您可以使用 bisect为了那个原因。但是，OrderedDict 没有排序，因此您不能对字典键使用二分搜索，除非您先对它们进行排序，而且这不会非常有效(事实上，仅循环键可能会更快)。

如果您维护一个排序的键列表，那么这可以工作，或者如果您使用排序的字典的实现。您可以使用内置的collections.OrderedDict，但是您必须自己维护排序，或者您可以使用一些btree实现，我认为有几种。

我只用过BTree ，它是用 C 编写的，速度非常快，但 API 有点迟钝。