4

我有时间序列数据，我目前存储在字典“键”是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

我尝试使用 bisect：

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

任何帮助，将不胜感激。

4

3 回答 3

4

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

这应该有效：

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

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

于 2012-05-14T20:07:02.097 回答
3

你最好为你的 dict 使用不同的键。

有两个很明显。

1) 您可以使用ISO 8601日期格式作为字符串。这本质上是YYYY-MM-DD格式。您也可以使用YYYY-MM-DD:HH:MM:SS格式。ISO 8601 的一个属性是词法排序，因此在已排序的键列表中，只需取插入点上方和下方的两个排序键。

2）您可以使用日期的浮点表示，整数部分是与千年标记的日期偏移量，而浮点数是当天的小数部分，然后可以轻松转换为 HH:MM:SS。Excel 和 Windows 和 Unix 使用这种方法。

1）的例子：

>>> datetime.datetime.fromtimestamp(time.time()).isoformat()
'2012-05-14T13:55:22.142548'  # a hashable, sortable dict key based on time

2）的例子：

>>> time.time()               # That is days and fraction of day since 1/1/1970 
1337028447.499273             # THAT is you dict key
>>> datetime.datetime.fromtimestamp(time.time()).timetuple()
time.struct_time(tm_year=2012, tm_mon=5, tm_mday=14, tm_hour=13, tm_min=52, tm_sec=13, tm_wday=0, tm_yday=135, tm_isdst=-1)

无论哪种情况，Python 都能够在几毫秒内管理 50,000 个元素的数据结构。

根据需要将时间戳转换为日期时间对象。

于 2012-05-14T20:42:10.343 回答
1

基于bisect模块创建索引似乎是一个值得深入研究的想法。但是，通过查看文档，您会看到 bisect 函数将排序列表作为第一个参数，而不是第二个参数。

尝试：

keys=sorted(data.keys())
bisect.bisect_left(keys,time), bisect.bisect_right(keys,time)

此外，您可以尝试通过在keys函数之外构造对象来优化代码findTime。如果您data的字典没有通过您的findTime调用序列进行修改，您只需支付一次排序列表的构建费用。

于 2012-05-14T20:08:07.447 回答