我的意思是一个结构:
- O(log n) 复杂度
- 找到一个元素的复杂度为 O(log n)
- O(n) 复杂度来计算
list(x)
这将被排序
x.push()
操作的我还有一个关于 list(...).insert(...)
性能的相关问题,现在是 here .
最佳答案
您的 big-O 要求有什么特殊原因吗?或者你只是想让它快点? sortedcontainers模块是纯 Python 且速度很快(就像在 blist 和 rbtree 等 fast-as-C 实现中一样)。
performance comparison显示它的基准测试速度更快或与 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
关于python - python有排序列表吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1109804/