在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