代码之家  ›  专栏  ›  技术社区  ›  darkhorse

在Python字典中查找失败时查找最接近的键对

  •  1
  • darkhorse  · 技术社区  · 6 年前

    假设我有一个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)
    

    这样的事情不需要迭代整个字典就可以完成吗? 如果没有,那么这个问题就不需要回答了。如果这确实可行,请尽可能包括一些性能影响。谢谢。

    0 回复  |  直到 6 年前
        1
  •  5
  •   Thierry Lathuille    6 年前

    下面是一个使用函数访问普通dict的解决方案(我使用 OrderedDict 因为我这里有一个旧版本的Python,您可以使用一个普通的 dict

    bisect

    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)
    

    你也可以子类化 迪克特 ,更新 __missing__ 迪克特 订购:

    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)
    
        2
  •  2
  •   sanyassh Khushboo Tahir    6 年前

    自定义dict类的解决方案:

    import bisect
    import collections
    
    
    class Bound:
        def __init__(self, left, right):
            self.left = left
            self.right = right
    
        def __repr__(self):
            return 'Bound({}, {})'.format(self.left, self.right)
    
    
    class MyDict(collections.defaultdict):
        def __init__(self, *args, **kwargs):
            super().__init__()
            dict.__init__(self, *args, **kwargs)
            self.lst = sorted(key for key in self)
    
        def __setitem__(self, key, value):
            if key not in self:
                bisect.insort_left(self.lst, key)
            super().__setitem__(key, value)
    
        def __delitem__(self, key):
            self.lst.remove(key)
            super().__delitem__(key)
    
        def __missing__(self, key):
            right_index = bisect.bisect(self.lst, key)
            left_index = right_index - 1
            right = self.lst[right_index] if right_index != len(self.lst) else None
            left = self.lst[left_index] if left_index != -1 else None
            return Bound(left, right)
    
    
    d = MyDict([(1, 0), (7, 10), (28, 20)])
    print(d[-3]) # Bound(None, 1)
    print(d[6]) # Bound(1, 7)
    print(d[7]) # 10
    print(d[33]) # Bound(28, None)
    del d[7]
    print(d[6]) # Bound(1, 28)
    
        3
  •  0
  •   Flávio Filho    6 年前
    def bound(x, d):
    
      if x in d:
        return x
      else:
    
        for i in sorted(d):
          if x > i:
            l = i
    
        for j in sorted(d, reverse=True):
          if j > x:
            h = j
    
        return(l,h)
    
    
    d = dict([(1, 0), (7, 10), (28, 20), (4,5), (2,5), (15,10)])
    
    bound(17,d)