Python - 找到最近的时间戳

Question

我有一个Python的时间戳和一个很大的字典（索引），这个字典的键是时间戳，值是我感兴趣的其他信息。

我需要在这个索引中找到离这个时间戳最近的时间（也就是键），而且希望这个过程尽可能高效。

目前我做的事情是这样的：

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

这样做是有效的，但速度太慢了——我的索引字典有几百万个值，而我需要搜索的次数有成千上万次。我对数据结构等方面比较灵活——这些时间戳大致是顺序排列的，所以我从第一个时间戳遍历到最后一个时间戳。同样，我从文本文件中加载到字典中的时间戳也是顺序的。

如果有任何优化的建议，我将非常感激。

Answer 1

如果你的列表是完全排序好的，而不是那种“差不多顺序”的情况，你可以使用二分查找。想了解更多，可以看看bisect模块的说明。

Answer 2

datetime对象之间是可以比较的，所以你可以像这样把你的键值对整理成一个排序好的列表：

myPairs = list(dict.iteritems())
myPairs.sort()

在每个元素 myPairs[i] 中，myPairs[i][0] 是 datetime 的键，而 myPairs[i][1] 是对应的值。

你可以使用 bisect_left 来高效地搜索这个列表：

import bisect
i = bisect.bisect_left(myPairs, targetDatetime)

元素 myPairs[i] 是在 targetDatetime 之后的最早的时间。但如果有前一个元素，它可能离 targetDatetime 更近。或者 targetDatetime 可能比 myPairs 中的任何时间都要晚。所以你需要检查一下：

if i > 0 and i == len(myPairs):
    i -= 1
elif i > 0 and targetDatetime - myPairs[i-1][0] < myPairs[i][0]- targetDatetime:
    i -= 1

Answer 3

字典并不是为了高效地进行近似搜索而设计的。它们主要是用来查找完全匹配的内容（使用的是哈希表）。

如果你需要更快的搜索，可能需要维护一个单独的、可以快速搜索的有序结构。

一个简单的开始方法是使用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))

如果你需要处理动态变化的字典，可以考虑使用blist，它采用树结构，能够实现快速的O(log N)插入和查找。只有在字典会随着时间变化时，你才需要使用这个方法。

如果你想继续使用字典的方式，可以考虑使用一个字典里面包含列表，这样可以把时间戳相近的条目聚集在一起：

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

需要注意的是，为了在聚类边界附近获得准确的结果，要在主聚类和相邻聚类中都存储接近边界的时间戳。