问题:python是否有排序列表?

我所说的结构是:

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

我也有一个有关性能的相关问题list(...).insert(...),现在在这里

By which I mean a structure with:

  • O(log n) complexity for x.push() operations
  • O(log n) complexity to find an element
  • O(n) complexity to compute list(x) which will be sorted

I also had a related question about performance of list(...).insert(...) which is now here.


回答 0

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

有许多符合您需求的Python平衡树实现,例如rbtreeRBTreepyavl

The standard Python list is not sorted in any form. The standard heapq module can be used to append in O(log n) to an existing list and remove the smallest one in O(log n), but isn’t a sorted list in your definition.

There are various implementations of balanced trees for Python that meet your requirements, e.g. rbtree, RBTree, or pyavl.


回答 1

您的big-O需求是否有特定原因?还是您只是想要它快?所述sortedcontainers模块是纯Python和快速(如在快速作为-C实现比如blist和rbtree)。

性能比较表明它与基准测试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

Is there a particular reason for your big-O requirements? Or do you just want it to be fast? The sortedcontainers module is pure-Python and fast (as in fast-as-C implementations like blist and rbtree).

The performance comparison shows it benchmarks faster or on par with blist’s sorted list type. Note also that rbtree, RBTree, and PyAVL provide sorted dict and set types but don’t have a sorted list type.

If performance is a requirement, always remember to benchmark. A module that substantiates the claim of being fast with Big-O notation should be suspect until it also shows benchmark comparisons.

Disclaimer: I am the author of the Python sortedcontainers module.


Installation:

pip install sortedcontainers

Usage:

>>> from sortedcontainers import SortedList
>>> l = SortedList()
>>> l.update([0, 4, 1, 3, 2])
>>> l.index(3)
3
>>> l.add(5)
>>> l[-1]
5

回答 2

尽管我仍然从未检查过基本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。啊,对不起,bisect在提到的问题中被提及。不过,我认为,如果此信息在这里,不会有太大危害)

PPS。而CPython的名单实际上是数组(不是,比方说,skiplists或等)。好吧,我想它们一定很简单,但就我而言,这个名称有点误导。


因此,如果我没记错的话,平分/列表速度可能是:

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

更新。在评论中进行讨论之后,让我在这里链接这些SO问题:如何实现Python的列表以及什么是Python列表函数的运行时复杂性

Though I have still never checked the “big O” speeds of basic Python list operations, the bisect standard module is probably also worth mentioning in this context:

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, sorry, bisect is mentioned in the referenced question. Still, I think it won’t be much harm if this information will be here )

PPS. And CPython lists are actually arrays (not, say, skiplists or etc) . Well, I guess they have to be something simple, but as for me, the name is a little bit misleading.


So, if I am not mistaken, the bisect/list speeds would probably be:

  • for a push(): O(n) for the worst case ;
  • for a search: if we consider the speed of array indexing to be O(1), search should be an O(log(n)) operation ;
  • for the list creation: O(n) should be the speed of the list copying, otherwise it’s O(1) for the same list )

Upd. Following a discussion in the comments, let me link here these SO questions: How is Python’s List Implemented and What is the runtime complexity of python list functions


回答 3

import bisect

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

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

回答 4

尽管(尚未)提供自定义搜索功能,但该heapq模块可能适合您的需求。它使用常规列表实现堆队列。您必须编写自己的有效成员资格测试,该测试利用队列的内部结构(可以在O(log n)中完成,我想说…)。有一个缺点:提取排序列表的复杂度为O(n log n)

Though it does not (yet) provide a custom search function, the heapq module may suit your needs. It implements a heap queue using a regular list. You’d have to write your own efficient membership test that makes use of the queue’s internal structure (that can be done in O(log n), I’d say…). There is one downside: extracting a sorted list has complexity O(n log n).


回答 5

我会使用biscectsortedcontainers模块。我确实没有经验,但是我认为该heapq模块有效。它包含一个Heap Queue

I would use the biscect or sortedcontainers modules. I don’t really am experienced, but I think the heapq module works. It contains a Heap Queue


回答 6

在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

It may not be hard to implement your own sortlist on Python. Below is a proof of concept:

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)

========= Results ============

[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


声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。