代码之家 › 专栏 › 技术社区 › Jonah Bishop

在OrderedDictionary中高效地查找上一个键

python-3.x python

Jonah Bishop · 技术社区 · 6 年前

我有一个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核心模块可以使用吗?

5 回复 | 直到 6 年前

blhsing 6 年前

由于您是按顺序将日期插入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)

以便:

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

zxch3n 6 年前

sortedcontainers 可能是你想要的。

它将保持键的排序顺序,而不是插入顺序,这与 collections.OrderedDict

安装

$ pip install sortedcontainers

from sortedcontainers import SortedDict
def find_nearest(sorted_dict, lookup):
    key = sorted_dict.iloc[sorted_dict.bisect_left(lookup) - 1]
    return sorted_dict[key]

sd = SortedDict({0: '0', 4: '4', 8: '8', 12: '12'})
print(find_nearest(sd, 4))  # 0
print(find_nearest(sd, 3))  # 0
print(find_nearest(sd, 12))  # 8

Michele Tonutti 6 年前

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

如果具有唯一的日期值,则可以使用pandas创建一个数据帧,该数据帧使用这些日期作为索引:

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

这将返回:

              value
2017-01-01     95
2018-01-01    100
2018-06-01    110
2018-09-01    112

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

jpp 6 年前

自 OrderedDict 是通过链表实现的,您不能在少于O的时间内按位置直接检索值( n ). 另请参见: Accessing dictionary items by position in Python 3.6+ efficiently

为了提高效率,我建议您使用第三方库,例如Pandas,它使用保存在连续内存块中的NumPy数组。时间复杂度为O( n ),但对于较大的输入字典,应该可以看到性能的提高。

import pandas as pd
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}

df = pd.DataFrame.from_dict(d, orient='index')
df.index = pd.to_datetime(df.index)

my_date = pd.to_datetime(date(2018, 8, 1))
res = df[0].iat[df.index.get_loc(my_date, method='ffill')]  # 110

另一种更详细的方法:

diffs = (my_date - df.index) > pd.Timedelta(0)
res = df[0].iat[-(diffs[::-1].argmax() + 1)]                # 110

-1

Petru Tanas 6 年前

可以尝试.get()方法,该方法仅在值存在时返回值,否则不返回任何值

import datetime
from datetime import date

def findNearest(somedate, dictionary):
    while dictionary.get(somedate) is None:
        somedate=somedate-datetime.timedelta(1)

    return dictionary.get(somedate)


result=findNearest(date(2017, 1, 3), yourDictionary)