我需要在Python中編寫事件日曆,它允許在任何位置粘貼事件,並且作爲FIFO(左側的彈出元素)工作。Python中的有效隊列/鏈接列表
Python collections.deque可以有效地作爲FIFO工作,但它不允許在當前元素之間粘貼元素。
另一方面,Python列表允許插入到中間,但popleft效率不高。
那麼,有沒有一些妥協?
UPD這樣的結構可能比隊列更接近鏈表。標題已更改。
我需要在Python中編寫事件日曆,它允許在任何位置粘貼事件,並且作爲FIFO(左側的彈出元素)工作。Python中的有效隊列/鏈接列表
Python collections.deque可以有效地作爲FIFO工作,但它不允許在當前元素之間粘貼元素。
另一方面,Python列表允許插入到中間,但popleft效率不高。
那麼,有沒有一些妥協?
UPD這樣的結構可能比隊列更接近鏈表。標題已更改。
你可以看看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
只是一個想法 - 你可以使用heapq
來維護你的事件列表。作爲堆中元素的優先級/鍵,您可以使用事件的時間戳。
這有點破解,但你也可以使用的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%單元測試覆蓋率,壓力測試小時數。
Afaik沒有可以有效地做到這一點的課程。你已經釘了它:列表可以插入任何位置,雙向可以彈出/插入/擴展左右。 – sphere
在中間插入'list'與popleft一樣效率低下。 –