Python 有排序后的列表吗？

我指的是这样一个结构:

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

我也有一个相关的问题，关于性能的 list(...).insert(...)现在是 给你。

113274 次浏览
小开
最佳答案

标准的 Python 列表不以任何形式排序。标准的 Heapq模块可以用来将 O (log n)附加到现有列表中，并删除 O (log n)中最小的一个，但是在您的定义中不是排序列表。

Python 中有各种平衡树的实现，可以满足您的需求，例如 Rbtree、 RBTree或 Pyavl。

小开

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

小开

虽然我还没有检查过基本 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

附言。啊，对不起，参考问题中提到了 bisect。尽管如此，我认为如果这些信息在这里，也不会造成太大的伤害)

又及。和 CPython 列表实际上是数组(不是，比如说，跳过列表或者其他)。好吧，我想他们必须是简单的东西，但对我来说，这个名字有点误导。

因此，如果我没有弄错的话，对分/列表的速度可能是:

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

Upd.在评论中的讨论之后，让我在这里链接这些 SO 问题: Python 的列表是如何实现的和 < a href = “ https://stackoverflow.com/questions/1005590/What-is-the-running-plex-of-python-list-function”> Python 列表函数的运行时复杂度是多少

小开

在 Python 上实现自己的分类列表可能并不困难:

import bisect


class sortlist:
def __init__(self, list):
self.list = list
self.sort()
def sort(self):
l = []
for i in range(len(self.list)):
bisect.insort(l, self.list[i])
self.list = l
self.len = i
def insert(self, value):
bisect.insort(self.list, value)
self.len += 1
def show(self):
print self.list
def search(self,value):
left = bisect.bisect_left(self.list, value)
if abs(self.list[min([left,self.len-1])] - value) >= abs(self.list[left-1] - value):
return self.list[left-1]
else:
return self.list[left]


list = [101, 3, 10, 14, 23, 86, 44, 45, 45, 50, 66, 95, 17, 77, 79, 84, 85, 91, 73]
slist = sortlist(list)
slist.show()
slist.insert(99)
slist.show()
print slist.search(100000000)
print slist.search(0)
print slist.search(56.7)

= = = = = = = = = = = = 结果 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

[3,10,14,17,23,44,45,45,50,66,73,77,79,84,85,86,91,95,101]

[3,10,14,17,23,44,45,45,50,66,73,77,79,84,85,86,91,95,99,101]

101

3

50

小开

你有什么特别的要求吗？还是你只想快点？分类容器模块是纯 Python 和快速的(就像 blist 和 rbtree 等 C 实现一样)。

性能比较显示它的基准测试速度更快，或者与 blist 的排序列表类型相当。还要注意，RBTree、 RBTree 和 PyAVL 提供了排序的 dict 和 set 类型，但没有排序的列表类型。

如果性能是一个需求，请始终记住进行基准测试。一个模块，证实了声称是快速的大 -O 符号应该是可疑的，直到它也显示基准比较。

免责声明: 我是 Python sortedContainer 模块的作者。

安装:

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
小开 
import bisect


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

我会使用 biscect或 sortedcontainers模块。我真的没有经验，但我认为 heapq模块工程。它包含一个 Heap Queue

小开

一个 AVL 树[ https://en.wikipedia.org/wiki/avl_tree ]加上顺序遍历可以在所需的时间复杂度内解决这个问题。

小开

有趣的例子: 如果您的列表 L已经排序(例如，因为您按照排序顺序附加了它们) ，您可以使用标准 Python 列表使用以下方法从快速 查找 in O (log n)中受益:

import bisect
def in_sorted_list(elem, sorted_list):
i = bisect.bisect_left(sorted_list, elem)
return i != len(sorted_list) and sorted_list[i] == elem
L = ["aaa", "bcd", "hello", "world", "zzz"]
print(in_sorted_list("hellu", L))       # False

详情请参阅 这个答案。


提交答案