Python：比O（N）更快地插入列表？

Question

我有一個排序列表L和我有一個二進制搜索來確定列表中插入元素的位置，使得結果列表仍然按順序排列。

但L.insert（索引，對象）需要O（N）時間複雜度。

是否有另一個L的數據結構可以達到同樣的目的，但是可以更快地插入？

Answer 1

查看blist模塊。

https://pypi.python.org/pypi/blist/

它聲稱O（log n）的插入。

用法：

x = #list contents 
y = blist(x) 
y.insert(index, object) #now works in O(log n) 

Answer 2

一個喊出來給sortedcontainers.SortedList。這將自動保留您的列表，並且插入時間很快。

from sortedcontainers import SortedList 

mylist = SortedList([1, 2, 4, 5]) 
mylist.add(3) 
mylist 
#>>> SortedList([1, 2, 3, 4, 5], load=1000) 

SortedListinsertions are amortized O(sqrt n), or O(cbrt n) with different choices of parameters,但鱗比blist，這是O(log n)更好，因爲常量要好得多。有a very in-depth look at performance on their website。

或者，您可能想要一個priority queue，在這種情況下，您可以使用the heapq module獲得可能更快的插入。