Python中的有效隊列/鏈接列表

Question

我需要在Python中編寫事件日曆，它允許在任何位置粘貼事件，並且作爲FIFO（左側的彈出元素）工作。

Python collections.deque可以有效地作爲FIFO工作，但它不允許在當前元素之間粘貼元素。

另一方面，Python列表允許插入到中間，但popleft效率不高。

那麼，有沒有一些妥協？

UPD這樣的結構可能比隊列更接近鏈表。標題已更改。

Answer 1

你可以看看blist。從他們的網站引用：

blist是Python列表的替代品，在修改大型列表時提供了更好的性能。

...

下面是一些使用情況下blist漸近優於內置列表：

Use Case          blist    list 
-------------------------------------------------------------------------- 
Insertion into or removal from a list   O(log n)   O(n) 
Taking slices of lists      O(log n)   O(n) 
Making shallow copies of lists    O(1)    O(n) 
Changing slices of lists      O(log n + log k) O(n+k) 
Multiplying a list to make a sparse list  O(log k)   O(kn) 
Maintain a sorted lists with bisect.insort O(log**2 n)  O(n) 

這裏的一些性能參數 - >http://stutzbachenterprises.com/performance-blist

Answer 2

只是一個想法 - 你可以使用heapq來維護你的事件列表。作爲堆中元素的優先級/鍵，您可以使用事件的時間戳。

Answer 3

這有點破解，但你也可以使用的SortedListWithKey數據類型模塊。您只需要按鍵返回一個常量，以便您可以按照您喜歡的方式訂購元素。試試這個：

from sortedcontainers import SortedListWithKey 

class FastDeque(SortedListWithKey): 
    def __init__(self, iterable=None, **kwargs): 
     super(FastDeque, self).__init__(iterable, key=lambda val: 0, **kwargs) 

items = FastDeque('abcde') 

print items 
# FastDeque(['a', 'b', 'c', 'd', 'e'], key=<function <lambda> at 0x1089bc8c0>, load=1000) 

del items[0] 
items.insert(0, 'f') 

print list(items) 
# ['f', 'b', 'c', 'd', 'e'] 

的FastDeque將有效地支持快速隨機訪問和刪除。 SortedContainers模塊的其他好處：純Python，快速實現C，100％單元測試覆蓋率，壓力測試小時數。