我有一个 Python 日期时间时间戳和一个大字典(索引),其中键是时间戳,值是我感兴趣的其他一些信息。
我需要尽可能高效地找到索引中最接近时间戳的日期时间(键)。
目前我正在做类似的事情:
for timestamp in timestamps:
closestTimestamp = min(index,key=lambda datetime : abs(timestamp - datetime))
它有效,但需要太长时间 - 我的索引字典有数百万个值,并且我正在执行数千次搜索。我对数据结构等很灵活 - 时间戳大致是连续的,因此我从第一个时间戳迭代到最后一个时间戳。同样,我加载到字典中的文本文件中的时间戳是连续的。
任何优化的想法将不胜感激。
字典的组织方式并不是为了高效的未遂搜索。它们是为精确匹配而设计的(使用哈希表).
您最好维护一个单独的、可快速搜索的有序结构。
一个简单的开始方法是使用对分模块对于快速 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))
请注意,为了获得集群边界附近的精确结果,请在主集群和相邻集群中存储接近边界的时间戳。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)