在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)。在

我可以很容易地通过在字典中查找条目来做到这一点：

^{pr2}$

然而，这让我觉得效率低下，因为在最坏的情况下，我必须扫描整个字典（我之前提到的字典可能很大）。我会做成千上万的这种类型的查找，所以我希望它是执行。在

另一个解决性能问题的方法是创建一个我看到的缓存，这也是可行的，尽管我想知道内存限制（我不完全确定缓存会增长到多大）。在

这里有什么聪明的方法或Python核心模块可以使用吗？在

Answer 1

sortedcontainers可能是您想要的。在

它将保持键的排序顺序而不是插入顺序，这与collections.OrderedDict不同。在

安装

$ pip install sortedcontainers

达到你想要的

^{pr2}$

该方法的时间复杂度为O（logn）

Answer 2

编辑 我刚意识到你想要一个核心模块——我的答案是熊猫！在

如果具有唯一的日期值，则可以使用pandas创建一个使用日期作为索引的数据帧：

df = pd.DataFrame.from_dict(rates, orient='index', columns=['value'])
# Convert index to pandas datetime
df.index = pd.to_datetime(df.index)

这将返回：

^{pr2}$

然后：

def lookup(date, df):
    # Convert input to datetime
    date = pd.to_datetime(date)
    # Get closest date in index
    closest_date = min(df.index, key=lambda x: abs(x - date))
    # Find corresponding index of closest date
    index = np.where(df.index == closest_date)[0][0]
    # If the date found if greater than the input, then get the date at the index before
    if closest_date > date:
        index -= 1

    return df.iloc[index].value

>> lookup('2018-06-02', df)
Out: 110

>> lookup('2018-05-01', df)
Out: 100

Answer 3

由于您是按顺序将日期插入dict中，而且您可能使用的是Python 3.7（它使dict order变得重要），因此您可以使用一个递归函数来除法和征服，以O（logn）时间复杂度找到键列表的所需索引：

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)

因此：

^{pr2}$

返回：110