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)

SortedList 插入被摊销O(sqrt n)，或者O(cbrt n)使用不同的参数选择，但它比 更好地扩展blist，即O(log n)，因为常量要好得多。有一个非常深入的看看他们的网站上的表现。

或者，你可能会想要一个优先级队列在这种情况下，你可以得到潜在更快的插入的heapq模块。