python - python有排序列表吗？

Question

我的意思是一个结构:

x.push() 操作的
• O(log n) 复杂度
• 找到一个元素的复杂度为 O(log n)
• O(n) 复杂度来计算 list(x) 这将被排序

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

Answer 1

您的 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