python - 在字典中递归查找

Question

我想为稀疏数据做一种字典类。这个想法是，如果键不在字典中，找到最近的具有较低值的键(我的字典的键总是正整数，最低的总是零)

这是我的原型(prototype)

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

我想这与递归有关，但我认为 python 中的递归数量更高。我还需要非常快的查找...

我做错了什么，有更好的方法吗？

谢谢

编辑:

一个例子:

如果我只有键“0”、“10”和“15”，并搜索键“13”，我希望getitem 函数给我对应于< strong>获取项目(10)

如果我想要键“100”应该得到 getitem(15) 的值。

编辑 2

我需要它成为字典或递归的 getitem 函数没有特别的原因。但我觉得这是最快的方法。

编辑 3

我尝试了@gilland @thomas-lotze 提出的所有 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

所以递归确实没有改善任何东西，正如@gill 所说，这是危险的。

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

Answer 1

这将实现您的狭义目标(假设键是 int 并且不会小于 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]

---

编辑 2

改进@ThomasLotze 的回答，这里是如何包装 bisect 同时保持 dict 接口(interface):

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)