Python - 找到最接近的时间戳

Question

我有一个Python日期时间戳和一个大的dict(索引),其中键是时间戳,值是我感兴趣的其他一些信息.

我需要尽可能有效地在索引中找到最接近时间戳的日期时间(键).

目前我做的事情如下:

for timestamp in timestamps:
    closestTimestamp = min(index,key=lambda datetime : abs(timestamp - datetime))

哪个有效,但需要太长时间 - 我的索引字典有数百万个值,我正在进行数千次搜索.我对数据结构很灵活等等 - 时间戳大致是顺序的,所以我从第一个时间戳到最后一个时间戳进行迭代.同样,我加载到dict中的文本文件中的时间戳是顺序的.

任何优化的想法将不胜感激.

Answer 1

字典不是为有效的近距离搜索而组织的.它们专为完全匹配而设计(使用哈希表).

您可能会更好地维护一个单独的,快速可搜索的有序结构.

一个简单的方法是使用bisect模块进行快速O(log N)搜索,但使用较慢的O(n)插入:

def nearest(ts):
    # Given a presorted list of timestamps:  s = sorted(index)
    i = bisect_left(s, ts)
    return min(s[max(0, i-1): i+2], key=lambda t: abs(ts - t))

适用于非静态,动态更新的dicts的更复杂的方法是使用blist,其使用树结构进行快速O(log N)插入和查找.如果dict会随着时间的推移而改变,你只需要这个.

如果您希望继续使用基于字典的方法,请考虑使用附近时间戳聚集条目的列表词典:

 def get_closest_stamp(ts):
      'Speed-up timestamp search by looking only at entries in the same hour'
      hour = round_to_nearest_hour(ts)
      cluster = daydict[hour]         # return a list of entries
      return min(cluster, key=lambda t: abs(ts - t))

请注意,对于群集边界附近的精确结果,请在主群集和相邻群集中存储接近边界的时间戳.