Python 有排序列表吗？
我的意思是需要一个这样的结构：
- 对于
x.push()操作，复杂度是 O(log n) - 查找一个元素的复杂度是 O(log n)
- 计算
list(x)的复杂度是 O(n)，而且结果会是排序好的
我还有一个相关的问题，关于 list(...).insert(...) 的性能，现在可以在 这里找到。
9 个回答
39
虽然我还没有检查过基本的Python列表操作的“时间复杂度”，但在这个话题中，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
附言：哦，抱歉，bisect在提到的问题中已经提过了。不过，我觉得把这些信息放在这里也没什么坏处)
再说一句，CPython中的列表实际上是数组（而不是像跳表之类的其他结构）。我想它们必须是一些简单的东西，但对我来说，这个名字有点误导。
所以，如果我没记错的话，bisect和列表的速度大概是：
- 对于添加元素（push()）：最坏情况下是O(n)；
- 对于查找：如果我们认为数组索引的速度是O(1)，那么查找应该是O(log(n))的操作；
- 对于列表创建：复制列表的速度是O(n)，否则对于同一个列表的速度是O(1）)
更新：根据评论中的讨论，我在这里链接这两个StackOverflow的问题：Python的列表是如何实现的和Python列表函数的运行时间复杂度是什么
119
你有没有特别的原因需要关注大-O的要求？还是说你只是想要它运行得快？sortedcontainers这个模块是用纯Python写的，速度很快（快得像C语言实现的blist和rbtree那样）。
性能对比显示它的速度比blist的排序列表类型要快，或者至少是一样快。还要注意，rbtree、RBTree和PyAVL提供了排序字典和集合的类型，但没有排序列表的类型。
如果你对性能有要求，记得一定要进行基准测试。一个声称自己速度快的模块，如果只用大-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