我有一个包含汇率值的 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 核心模块吗?
最佳答案
由于您按顺序将日期插入到字典中,并且您可能使用的是 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
关于python - 有效地找到 OrderedDictionary 中的上一个键,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52535803/