Python字典 - 有没有二分查找键的方法？

Question

我想写一个容器类，它的功能像字典（实际上是从字典派生的）。这个结构的键将是日期。

当我用一个键（也就是日期）去获取这个类中的值时，如果这个日期不存在，就会返回一个比这个日期早的最近的日期对应的值。

下面的数据可以帮助更好地理解这个概念：

Date (key)      Value
2001/01/01      123
2001/01/02       42
2001/01/03      100
2001/01/04      314
2001/01/07      312
2001/01/09      321

比如说，如果我想获取键（日期）'2001/01/05'对应的值，我应该得到'2001/01/04'下存储的值，因为这个键在'2001/01/05'应该存在的位置之前。

为了实现这个功能，我需要能够进行搜索（最好是二分查找，而不是简单地一个一个遍历字典里的每个键）。我查找了Python字典中的二分查找键查找，但没有找到有用的信息。

总之，我想写一个包含这种行为的类。

这是我目前的进展（不多）：

#
class NearestNeighborDict(dict):
#
"""
#
a dictionary which returns value of nearest neighbor 
if specified key not found
#
"""

def __init__(self, items={}):
    dict.__init__(self, items)


def get_item(self, key):
    # returns the item stored with the key (if key exists)
    # else it returns the item stored with the key

Answer 1

我会扩展一个 dict（字典），并重写 __getitem__ 和 __setitem__ 这两个方法，以便存储一个有序的键列表。

from bisect import bisect

class NearestNeighborDict(dict):
    def __init__(self):
        dict.__init__(self)
        self._keylist = []

    def __getitem__(self, x):
        if x in self:
            return dict.__getitem__(self, x)

        index = bisect(self._keylist, x)
        if index == len(self._keylist):
            raise KeyError('No next date')

        return dict.__getitem__(self, self._keylist[index])

    def __setitem__(self, x, value):
        if x not in self:
            index = bisect(self._keylist, x)
            self._keylist.insert(index, value)

        dict.__setitem__(self, x, value)

确实，从 MutableMapping 继承会更好，但原理是一样的，上面的代码也可以很容易地进行调整。

Answer 2

sortedcontainers模块提供了一种叫做SortedDict的类型，它可以保持键的顺序是排好序的，并且支持在这些键上进行快速查找。这个模块是纯Python写的，而且有着接近C语言速度的实现，并且经过了100%的测试覆盖和长时间的压力测试。

举个例子：

from sortedcontainers import SortedDict

sd = SortedDict((date, value) for date, value in data)

# Bisect for the index of the desired key.
index = sd.bisect('2001/01/05')

# Lookup the real key at that index.
key = sd.iloc[index]

# Retrieve the value associated with that key.
value = sd[key]

因为SortedDict支持快速索引，所以你可以很方便地查看你所需键的前后内容。SortedDict还是一个可变映射，这样它在你的类型系统中也能很好地工作。

Answer 3

你其实不太想直接去继承 dict，因为你无法真正重用它的功能。相反，你应该继承一个叫做 collections.Mapping 的抽象基类（如果你想在创建后还能修改实例，就用 MutableMapping），然后实现一些必要的特殊方法，这样你就能从这个抽象基类中“免费”获得其他类似 dict 的方法。

你需要实现的方法包括 __getitem__（如果你想让对象可修改，还需要 __setitem__ 和 __delitem__），__len__，__iter__ 和 __contains__。

标准库中的 bisect 模块可以帮助你高效地在一个已排序的列表上实现这些功能。例如……：

import collections
import bisect

class MyDict(collections.Mapping):
  def __init__(self, contents):
    "contents must be a sequence of key/value pairs"
    self._list = sorted(contents)
  def __iter__(self):
    return (k for (k, _) in self._list)
  def __contains__(self, k):
    i = bisect.bisect_left(self._list, (k, None))
    return i < len(self._list) and self._list[i][0] == k
  def __len__(self):
    return len(self._list)
  def __getitem__(self, k):
    i = bisect.bisect_left(self._list, (k, None))
    if i >= len(self._list): raise KeyError(k)
    return self._list[i][1]

你可能需要根据不同的特殊情况来调整 __getitem__ 的实现，比如当 "k 大于 self 中的所有键" 时，你想返回什么（或者是否要抛出异常）。