如果在Python字典中查找失败，则查找最接近的键对

Question

可以说我有一个Python字典，其中的键实际上是整数。我可以这样创建一个：

>>> d = dict([(1, 0), (7, 10), (28, 20)])
>>> d
{1: 0, 7: 10, 28: 20}

现在，我想查找如果找到了密钥，则返回其索引。这部分真的很容易，就像这样：

>>> key = 7
>>> d[key]
10

如果找不到密钥，那么我想返回密钥的绑定。例如：

>>> key = 6
>>> d[key]
Bound(1, 7)

由于6不作为键存在，因此我返回了它们之间的2个键。基本上不迭代整个字典，是否有可能这样做？如果不是，那么这个问题实际上并不需要回答。如果确实可行，请尽可能包含一些性能影响。谢谢。

Answer 1

Here is a solution using a function to access a normal dict (I used an OrderedDict as I have an older version of Python here now, you can use a normal dict if you have Python 3.6 or more, as they are ordered.)

We sort the dict by key, which lets us use bisect to find the surrounding keys quickly.

import bisect
from collections import OrderedDict

d = OrderedDict(sorted([(1, 0), (7, 10), (28, 20)])) # Could be a simple dict with Python 3.6+

class Bound:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __repr__(self):
        return 'Bound({}, {})'.format(self.a, self.b)

def closest(key, d):
    try:
        return d[key]
    except KeyError:
        keys = list(d.keys())
        ins_point = bisect.bisect(keys, key)
        return Bound(keys[ins_point-1] if ins_point >= 1 else None,
                     keys[ins_point] if ins_point < len(keys) else None)

closest(7, d)
# 10

closest(8, d)
# Bound(7, 28)

closest(30, d)
# Bound(28, None)

closest(-1, d)
# Bound(None, 1)

You can also subclass dict, updating the __missing__ method (code for Python >=3.6, assuming that dict is ordered:

import bisect

class Bound:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __repr__(self):
        return 'Bound({}, {})'.format(self.a, self.b)


class BoundDict(dict):
    def __missing__(self, key):
        keys = list(self.keys())
        ins_point = bisect.bisect(keys, key)
        return Bound(keys[ins_point-1] if ins_point >= 1 else None,
                     keys[ins_point] if ins_point < len(keys) else None)


d = BoundDict(sorted([(1, 0), (7, 10), (28, 20)])) 

print(d[7])
# 10

print(d[8])
# Bound(7, 28)

print(d[30])
# Bound(28, None)

print(d[-1])
# Bound(None, 1)