从时间排序列表中删除旧元素

假设我有一个列表l，其中每个元素都有一个属性time，该属性存储一个浮点，表示从某个基准点过去多少秒。当一些事件发生，我想从列表中删除，此事件发生之前超过T秒的所有元素，所以目前我做的是从时间排序列表中删除旧元素

l = [x in l if x.time > current_time - T]

这似乎是做事慢的方式。这怎么能更快地完成？元素在这里按时间排序，所以我想到找到不满足这个条件的第一个元素，例如

for i, x in enumerate(l): 
    if x.time > current_time - T: 
     break 
l = l[i:]

也许有一种方式吗？

来源

2016-01-21 Ilya

您可以使用collections的deque。它给你O(1)的复杂性，以从列表头移除元素。由于您的元素按时间排序，而最早的元素位于列表的头部，因此您可以轻松地逐个删除元素。

来源

2016-01-21 09:53:09 nikihub

由于它们是按时间顺序排列的，因此可以使用二分查找来查找分界点的索引，然后重新切分列表。二进制搜索应该（大致）O（log n）找到截止点，然后O（n）的切片。

但是，如果你经常这样做，最好使用一个deque和简单的弹出元素，直到头部处于“保持期限内”。

因此，无论什么最好都需要基准。然而，deque解决方案（可能）更容易编写，因此最好从头开始，然后在出现性能问题时考虑其他方法。

来源

2016-01-21 10:05:49 Vatine

import random 

class Element(): 

    def __init__(self, time): 
     self.time = time 

l = [ Element(z*5 - random.randrange(6) + 3) for z in range(21)] 
print('list:', [z.time for z in l]) 
target_time = 72 
print('cutoff time:', target_time) 


match = False 
working_list_from = 0 
working_list_to = len(l) 
while not match: 
    mid = (working_list_to - working_list_from) // 2 
    if l[working_list_from + mid].time < target_time: 
     working_list_from += mid 
    else: 
     working_list_to -= mid 


    match = (working_list_to - working_list_from) == 1 

print(' resulting list', [z.time for z in l[working_list_from+mid:]])

结果：

list: [3, 5, 9, 18, 21, 25, 32, 33, 40, 48, 49, 57, 62, 67, 73, 73, 79, 85, 93, 94, 99] 
cutoff time: 72 
resulting list [73, 73, 79, 85, 93, 94, 99]

来源

2016-01-21 10:11:08

从时间排序列表中删除旧元素

回答

相关问题