python - 使用日期时间键的字典搜索

Question

我有时间序列数据，我目前存储在字典中，其中字典“键”是 datetime.datetime 对象。类似的东西:

data[datetime.datetime(2012,5,14,15,28,2)]={'error':error,'flags':flags,'value':value}

我的问题是:找到指定时间最近两次(之前和之后)的最佳方法是什么？我需要这个函数尽可能快，因为它被称为(~10,000) 在两个最近点之间线性插值的循环内。

---

我目前有一种工作方法需要很长时间，因为它会搜索所有键 (~50,000):

def findTime(time):
    keys=data.keys()
    bdt=10000000000000000000
    adt=10000000000000000000
    minKey=False
    maxKey=False
    for key in keys:
        dt=(time-key).total_seconds()
        if abs(dt)<bdt and dt>0:
            bdt=abs(dt)
            minKey=key
        elif abs(dt)<adt and dt<0:
            adt=abs(dt)
            maxKey=key
    return minKey,maxKey

---

我尝试使用二分法:

def findTime(time):
    keys=data.keys()
    l,r = bisect.bisect_left(time,keys), bisect.bisect_right(time,keys)
    return l,r

不幸的是，这会产生一个错误:

TypeError: 'datetime.datetime' object does not support indexing

如有任何帮助，我们将不胜感激。

Answer 1

bisect 函数的第一个参数是一个排序数组(或列表，或者实际上，任何可以索引的东西)。 keys 是一个未排序的数组，您将其作为第二个参数传递。

这应该有效:

def findTime(time):
    keys = sorted(data.keys())
    return bisect.bisect_left(keys, time), bisect.bisect_right(keys, time)

尽管您应该保留已排序的副本以用于未更改数据的重复搜索，而不是每次都重新排序。