我有一些（非常大的）元组列表，它们来自包含 id、start_time 和 end_time 的数据库
我还有一个定期和有序的时间列表（这些都是日期时间对象）。
我基本上需要遍历这些时间并找到时间落在其范围内的所有元组。
我想知道最有效的方法是什么。想到的第一个想法是这样的（伪代码）：
for time in times:
for tuple in tuples:
if tuple.start_time <= time <= tuple.end_time:
# add tuple to some_other_list
if tuple.end_time < time
# remove tuple from tuples
我这样做的原因是迭代一个越来越小的列表，希望在那里减少一些时间，但是我也对完全不同的方法持开放态度。我想另一个想法是在每次迭代中只用给定的时间查询数据库，但我认为那里的延迟将远远超过将完整数据集保存在内存中并以这种方式使用它。
例如，我会有一个元组列表，其中每个元组看起来像：
[('783', datetime.datetime(2017, 12, 31, 20, 49, 28), datetime.datetime(2017, 12, 31, 23, 49, 28)), ('5274', datetime.datetime(2017, 12, 31, 20, 49, 45), datetime.datetime(2018, 1, 1, 0, 0)), ('757', datetime.datetime(2017, 12, 31, 20, 50, 25), datetime.datetime(2018, 1, 1, 1, 50, 25)), ('5600', datetime.datetime(2017, 12, 31, 20, 50, 59), datetime.datetime(2017, 12, 31, 23, 39)), ('5176', datetime.datetime(2017, 12, 31, 20, 51, 23), datetime.datetime(2018, 1, 1, 1, 51, 23)), ('5323', datetime.datetime(2017, 12, 31, 20, 52, 39), datetime.datetime(2018, 1, 1, 0, 0)), ('464', datetime.datetime(2017, 12, 31, 20, 52, 41), datetime.datetime(2018, 1, 1, 0, 52, 41))]
时间列表将基本上使用这个答案存储在生成器中，因此循环遍历它们会产生如下结果：
2017-12-15 00:00:00
2017-12-22 00:00:00
2017-12-29 00:00:00
2018-01-05 00:00:00
2018-01-12 00:00:00
2018-01-19 00:00:00
而我相当不可知的实际输出，它只是一些字典
{'2017-12-15 00:00:00': [list of matching ids], '2017-12-22 00:00:00': [list of matching ids], ...}
任何想法或建议将不胜感激！
首先，关于删除不相关间隔的注意事项：如果您从（长）列表中执行此操作，则性能将很糟糕，因为需要将后面的元素移入空白空间。可以通过用一个整数替换已删除的元素来解决这个问题，该整数表示要跳过多远才能找到下一个真实数据。
这是经典的区间查询问题，通常的答案是区间树或段树。但是，如果您可以一次存储所有结果（以及所有已排序的查询时间），则可以使用一个简单的替代方法：不是迭代时间然后搜索区间，而是在所有区间迭代一次并执行二分搜索找出每个区间包含的最早和最晚查询时间。然后将时间间隔的 ID 附加到为每个这样的时间维护的列表中：
def ids(iv,tm):
ret=[[] for _ in tm]
for nm,l,h in iv:
for i in range(bisect.bisect_left(tm,l),bisect.bisect_right(tm,h)):
ret[i].append(nm)
return ret
您当然可以使用dict(zip(tm,ids(iv,tm))).
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句