字典中的递归查找

Question

我想做一种字典类，用于稀疏数据。我们的想法是，如果该键不在字典中找到一个较低的值最接近的键（我的字典的键始终为正整数，最低的存在始终为零）

这里是我的原型

class specialdict(dict): 
    def __getitem__(self, beg): 
     try: 
      return self[beg - 1] 
     except: 
      return dict.__getitem__(self, beg) 

a = specialdict([(10, True)]) 

print a[137] 

print a[500] 

而这个工作，但只到338

我猜它与递归的事，但我虽然蟒蛇递归数较高。我也需要查找速度非常快...

我是否会犯错，有没有更好的方法来做到这一点？

感谢

编辑：

一个例子：

如果我只具有键 “0”， “10” 和 “15”，并搜索键 “13”，余希望的GetItem功能给我相应的GetItem （10）

如果我想重点“100”应该得到的GetItem价值的价值（15））。

EDIT 2

没有特别的原因，我需要它是一本字典，或的GetItem功能是递归的。但我有这种感觉，这将是最快的方式。

编辑3

我试图提出@gilland所有3个解决方案@托马斯 - 洛采：

import bisect 

class SparseData(object): 

    def __init__(self, pairs=()): 
     if pairs: 
      indexes, values = zip(*pairs) 
      self.indexes = list(indexes) 
      self.values = list(values) 
     else: 
      self.indexes = [] 
      self.values = [] 


    def __setitem__(self, index, value): 
     i = bisect.bisect(self.indexes, index) 
     self.indexes.insert(i, index) 
     self.values.insert(i, value) 

    def __getitem__(self, index): 
     i = bisect.bisect(self.indexes, index) 
     if not i: 
      raise IndexError(i) 
     return self.values[i-1] 

class specialdict_rec(dict): 
    def __getitem__(self, beg): 
     try: 
      return dict.__getitem__(self, beg) 
     except KeyError: 
      return self[beg - 1] 

class specialdict_non_rec(dict): 
    def __getitem__(self, beg): 
     while beg >= 0: 
      try: 
       return dict.__getitem__(self, beg) 
      except KeyError: 
       beg -= 1 

这里的基准结果：

In [1]: a = [(1, '1'), (7, '7'), (100, '100')] 

In [2]: a1 = SparseData(a) 

In [3]: a2 = specialdict_rec(a) 

In [4]: a3 = specialdict_non_rec(a) 

In [5]: %timeit -n10000 a1[200] 
10000 loops, best of 3: 1.12 µs per loop 

In [6]: %timeit -n10000 a2[200] 
10000 loops, best of 3: 96 µs per loop 

In [7]: %timeit -n10000 a3[200] 
10000 loops, best of 3: 58.6 µs per loop 

所以这是真的递归不会改善任何事情，正如@吉尔所说，这是危险的。

但最后我要用的解决方案是来自@ thomas-lotze的解决方案。 非常感谢您的回答！

Answer 1

对于速度，使用the bisect module对一个工作（键，值）对列表而不是字典：

import bisect 

class SparseData(object): 

    def __init__(self, pairs=()): 
     if pairs: 
      indexes, values = zip(*pairs) 
      self.indexes = list(indexes) 
      self.values = list(values) 
     else: 
      self.indexes = [] 
      self.values = [] 

    def __setitem__(self, index, value): 
     i = bisect.bisect(self.indexes, index) 
     if self.indexes[i-1] == index: 
      self.values[i-1] = value 
     else: 
      self.indexes.insert(i, index) 
      self.values.insert(i, value) 

    def __getitem__(self, index): 
     i = bisect.bisect(self.indexes, index) 
     if not i: 
      raise IndexError(i) 
     return self.values[i-1] 

>>> x = SparseData([(1, '1'), (2, '2'), (4, '4')]) 

>>> x[0] 
Traceback (most recent call last): 
... 
IndexError: 0 

>>> x[3] 
'2' 
>>> x[4] 
'4' 

>>> x[27] = '27' 
>>> x[25] 
'4' 
>>> x[27] 
'27' 
>>> x[29] 
'27' 

Answer 2

这将实现您的狭隘目标（假设密钥为int s并且不会小于0），但像@JustinR在评论中说，对于更大的问题可能有更好的解决方案。

class specialdict(dict): 
    def __getitem__(self, beg): 
     while beg >= 0: 
      try: 
       return dict.__getitem__(self, beg) 
      except KeyError: 
       beg -= 1 

---

编辑

只是为了展示如何做同样的事情递归（因为OP问），但它是非常不推荐的。有递归限制。正如其他人所说，二分查找更高效。

class specialdict(dict): 
    def __getitem__(self, beg): 
     try: 
      return dict.__getitem__(self, beg) 
     except KeyError: 
      return self[beg - 1] 

---

EDIT 2

提高对@ ThomasLotze的答案，这里是如何包装bisect同时保持dict接口：

import bisect 

class SpecialDict(dict): 

    def __init__(self, *args, **kwargs): 
     dict.__init__(self, *args, **kwargs) 
     self._keys = sorted(self.keys()) # maintain a sorted list of keys 

    def __setitem__(self, key, value): 
     if key not in self: 
      bisect.insort(self._keys, key) 
     dict.__setitem__(self, key, value) 

    def __getitem__(self, key): 
     if key not in self: 
      try: 
       key = self._keys[bisect.bisect(self._keys, key) - 1] 
      except IndexError: 
       raise KeyError(key) 
     return dict.__getitem__(self, key)