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

Question

假设我有一个列表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:]

也许有更好的方法

Answer 1

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]

Answer 2

因为它们是按时间顺序排列的，所以可以使用二进制搜索来查找截止点的索引，然后重新对列表进行切片。二进制搜索应该是（大致）O（logn）来寻找截止点，然后O（n）来进行切片

但是，如果您经常这样做，最好使用deque并简单地弹出元素，直到头部处于“保留期内”

因此，无论什么是最好的都需要基准测试。但是，deque解决方案（可能）更容易编写，因此最好从这里开始，如果您看到性能问题，那么考虑其他方法

Answer 3

您可以使用来自collections的deque。它给了您从列表头中删除元素的O(1)复杂性。由于元素是按时间排序的，并且最早的元素位于列表的开头，因此可以轻松地逐个删除元素