我正在尝试优化我的一段代码,但我不知道哪一个是最好的数据结构,也不知道是否有什么能满足我的要求。
我有一个实体列表,其中有一个定义的开始和停止时间点(都是浮动的(。我正在尝试建立一个索引,让我可以查找在给定时间点上的窗口(开始和停止(。目前,我只是简单地迭代dict并检查每个实体是否为start < t < stop
。
这里有一个小例子:
entities = {
'a': (0, 32.31),
'b': (2, 22.00312),
'c': (10, 34.1),
'd': (22, 40.2)
}
预期输出如下:
t = 12
index = build_index(entities)
candidates = find_candidates(t, index)
print(candidates)
['a', 'b', 'c']
t = 33
index = build_index(entities)
candidates = find_candidates(t, index)
print(candidates)
['c', 'd']
实体列表可以增加到几十万。什么是一种好的数据结构/编程方法,可以在标准笔记本电脑(比如8GB RAM(上尽快找到这些窗口
我很高兴有任何解决方案的想法,我不一定在寻找一个完整的工作代码,它可以满足我的需求!
多亏了@Adam.Er8的帮助,我找到了解决方案。
使用intervaltree模块可以很容易地解决这个问题。
from intervaltree import IntervalTree
entities = {
'a': (0, 32.31),
'b': (2, 22.00312),
'c': (10, 34.1),
'd': (22, 40.2)
}
for key, r in entities.items():
t[r[0]:r[1]] = key
results = t.at(12)
print([x.data for x in results])
['a', 'b', 'c']