python有排序列表吗？

Question

我的意思是一个结构:

• O(log n)x.push()操作的复杂性
• O(log n)查找元素的复杂性
• O(n)计算的复杂性list(x)将被排序

我还有一个关于性能的相关问题list(...).insert(...)现在在这里.

Answer 1

您的大O要求有特殊原因吗？或者你只是希望它快？所述sortedcontainers模块是纯Python和快速(如在快速作为-C实现比如blist和rbtree).

在性能比较显示其基准测试速度更快或与blist的排序列表类型相提并论.另请注意,rbtree,RBTree和PyAVL提供了已排序的dict和set类型,但没有排序列表类型.

如果要求性能,请始终记住基准测试.在证明基准比较之前,应该怀疑用Big-O符号表示快速声明的模块.

免责声明:我是Python sortedcontainers模块的作者.

安装:

pip install sortedcontainers

用法:

>>> from sortedcontainers import SortedList
>>> l = SortedList()
>>> l.update([0, 4, 1, 3, 2])
>>> l.index(3)
3
>>> l.add(5)
>>> l[-1]
5

Answer 2

标准Python列表未以任何形式排序.标准heapq模块可用于将O(log n)附加到现有列表中并删除O(log n)中的最小值,但不是定义中的排序列表.

Python的平衡树有各种实现,可满足您的要求,例如rbtree,RBTree或pyavl.

Answer 3

虽然我还没有检查过基本Python列表操作的"大O"速度,但bisect标准模块在这方面可能也值得一提:

import bisect
L = [0, 100]

bisect.insort(L, 50)
bisect.insort(L, 20)
bisect.insort(L, 21)

print L
## [0, 20, 21, 50, 100]

i = bisect.bisect(L, 20)
print L[i-1], L[i]
## 20, 21

PS.啊,对不起,bisect在引用的问题中提到了.不过,我认为如果这些信息会在这里不会有太大的危害)

PPS.而CPython的名单实际上是数组(不是,比方说,skiplists或等).嗯,我想他们必须是简单的东西,但就我而言,这个名字有点误导.

所以,如果我没有弄错的话,bisect/list的速度可能是:

• 对于push():O(n)表示最坏的情况;
• 对于搜索:如果我们认为数组索引的速度为O(1),则搜索应该是O(log(n))操作;
• 对于列表创建:O(n)应该是列表复制的速度,否则它是相同列表的O(1))

UPD.在评论中讨论之后,让我在这里链接这些SO问题:如何实现Python的列表以及python列表函数的运行时复杂性是什么

Answer 4

虽然它(尚未)提供自定义搜索功能,但该heapq模块可能适合您的需求.它使用常规列表实现堆队列.您必须编写自己的有效成员资格测试,该测试利用队列的内部结构(可以在O(log n)中完成,我会说...).有一个缺点:提取排序列表的复杂度为O(n log n).

Answer 5

import bisect

class sortedlist(list):
    '''just a list but with an insort (insert into sorted position)'''
    def insort(self, x):
        bisect.insort(self, x)