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词典中搜索了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

Answer 1

你真的不想要子类,dict因为你无法真正重用它的任何功能.相反,子类化抽象基类collections.Mapping(或者MutableMapping如果你想在创建后也能修改实例),为此目的实现必不可少的特殊方法,你将从dictABC中"免费" 获得类似其他方法.

你需要的代码的方法是__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".

Answer 2

所述sortedcontainers模块提供SortedDict维持按排序顺序的键和支持平分在琴键上的类型.该模块是纯Python和快速实现,具有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也是一个MutableMapping,所以它应该在你的类型系统中很好地工作.