python有排序列表吗?

标准的python列表没有以任何形式排序。标准 heapq 模块可用于将o(log n)中的元素追加到现有列表中,并删除o(log n)中最小的元素,但在定义中不是排序列表。

有多种针对Python的平衡树实现可以满足您的需求,例如 rbtree , RBTree 或 pyavl .

你的大O要求有什么特别的原因吗?或者你只是想快点?这个 sortedcontainers 模块是纯python和fast(就像在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列表操作的“大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. Ah,对不起, 二等分 在参考问题中提到。不过,我认为如果这些信息在这里不会有太大的危害)

PPS。和 CPython lists are actually arrays (比如说,不是滑雪运动员等)。嗯,我想他们必须是简单的,但对我来说,这个名字有点误导人。

因此,如果我没有弄错,平分/列表速度可能是:

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

UPD。 在评论中讨论之后,让我在这里链接以下问题: How is Python's List Implemented 和 What is the runtime complexity of python list functions

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

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

在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]

一百零一

三

五十