python - 有效地找到 OrderedDictionary 中的上一个键

Question

我有一个包含汇率值的 OrderedDictionary。每个条目都有一个键的日期(每个日期恰好是每年一个季度的开始)，值是一个数字。日期按从旧到新的顺序插入。

{
    date(2017, 1, 1): 95,
    date(2018, 1, 1): 100,
    date(2018, 6, 1): 110,
    date(2018, 9, 1): 112,
}

我的利率词典比这个大得多，但这是一般的想法。给定一个任意日期，我想在字典中找到它之前的值。。例如，查找 date(2018, 8, 1) 的日期应返回值 110，因为条目 date(2018, 6, 1)是我的日期查找之前最近的键。同样，日期 date(2017, 12, 1)应该返回 95，因为最近的前一个键恰好是 date(2017, 1, 1) .

我可以通过遍历字典中的项目轻松地做到这一点:

def find_nearest(lookup):
    nearest = None
    for d, value in rates.items():
        if(d > lookup):
            break
        nearest = value
    return nearest

然而，这对我来说感觉效率很低，因为在最坏的情况下我必须扫描整个字典(我之前提到过它可能很大)。我将进行数以万计的此类查找，因此我希望它具有高性能。

解决性能问题的另一种选择是为我所见创建一个缓存，这也是可行的，尽管我想知道内存限制(我不完全确定缓存会增长到多大)。

我可以在这里使用任何巧妙的方法或 Python 核心模块吗？

Answer 1

由于您按顺序将日期插入到字典中，并且您可能使用的是 Python 3.7(这使得字典顺序很重要)，因此您可以使用分而治之的递归函数在 O 中找到所需的键列表索引(log n) 时间复杂度:

def find_nearest(l, lookup):
    if len(l) == 1:
        return l[0]
    mid = len(l) // 2
    if l[mid] > lookup:
        return find_nearest(l[:mid], lookup)
    return find_nearest(l[mid:], lookup)

这样:

from datetime import date
d = {
    date(2017, 1, 1): 95,
    date(2018, 1, 1): 100,
    date(2018, 6, 1): 110,
    date(2018, 9, 1): 112,
}
d[find_nearest(list(d), date(2018, 8, 1))]

返回:110