從時間排序列表中刪除舊元素

假設我有一個列表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

從時間排序列表中刪除舊元素

回答

相關問題