Python字典-二分查找一个键？

我想编写一个像字典一样的容器类（实际上派生自字典），该结构的键将是日期。

当使用键（即日期）从类中检索值时，如果该日期不存在，则使用该键之前的下一个可用日期来返回该值。

以下数据应该有助于进一步解释这个概念：

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 字典中搜索了 bsearch 字典键查找 - 但没有找到任何有用的东西。

无论如何，我想编写一个类似的类来封装这种行为。

这是我到目前为止所拥有的（不多）：

#
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

你真的不想子类化dict因为你无法真正重用它的任何功能。相反，子类化抽象基类collections.Mapping http://docs.python.org/library/collections.html?highlight=collections#abcs-abstract-base-classes (or MutableMapping如果您还希望能够在创建后修改实例），则为此目的实现不可或缺的特殊方法，您将获得其他dict- 类似于 ABC 的“免费”方法。

您需要编码的方法是__getitem__ (and __setitem__ and __delitem__如果你想要可变性），__len__, __iter__, and __contains__.

The bisect http://docs.python.org/library/bisect.html?highlight=bisect#module-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".