Python的 - 定位最近的时间戳

我有一个Python的datetime时间戳和大字典（指数）键进行时间戳和值是我感兴趣的一些其他信息Python的 - 定位最近的时间戳

我需要找到的日期时间（尽可能高效的索引中最接近时间戳的键）。

在我做类似的时刻：

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

其工作原理，但过长需要 - 我的索引dict有上百万的价值观，和我做搜索数千次。我对数据结构等方面很灵活 - 时间戳大致是连续的，所以我从第一个时间戳到最后一个时间戳。同样，我加载到字典中的文本文件中的时间戳也是顺序的。

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

来源

2011-11-17 Caligari

是大字典相对静态，还是你经常添加和删除条目？ –

字典实际上完全是静态的。 – Caligari

非常感谢所有有用的答案。我已经对这些建议进行了一些改进，看起来像我一定能够解决我的问题，速度的提高是巨大的。现在是家庭时间，所以明天我会多一点戏剧，并更新我的最终实施。 – Caligari

词典没有组织成高效的接近未命中搜索。它们专为精确匹配而设计（使用hash table）。

维护一个单独的，快速搜索的有序结构可能会更好。

一个简单的方法，开始是用bisect module用于快速为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))

注意，对于接近群集边界确切的结果，存储特写TO-主群集和相邻群集中的边界时间戳。

来源

2011-11-17 05:10:10

优秀的综合答案！（很高兴在这里看到你在这里，顺便说一下，雷蒙德:) :) –

为什么i + 2的回报最小（s [max（0，i-1）：i + 2]，key = lambda t：abs（ ts - t））？在我看来，它可能是+1，它仍然有效 – Hammer

如果您的列表是真正排序的，而不只是“大致顺序”，您可以使用二分查找。有关更多信息，请参阅bisect module documentation。

来源

2011-11-17 05:14:18

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

来源

2011-11-17 05:21:24

Python的 - 定位最近的时间戳

回答

相关问题