python是否有排序列表？

101

O（log n）的複雜性x.push()操作
O（log n）的複雜性，以找到一個元素
O（n）的複雜計算list(x)哪些將被排序

我還有一個相關的問題，關於性能list(...).insert(...)現在是here。

2009-07-10 ilya n.

`memcpy`仍然是* O（n）*操作。我不知道Python是如何實現列表*的，但我敢打賭，它們存儲在連續的內存中（當然不是鏈接列表）。如果確實如此，那麼使用您演示的「bisect」插入將具有複雜性* O（n）*。 – Stephan202 2009-07-10 15:38:15

...然後這個例子不見了;） – Stephan202 2009-07-10 15:40:07

@ stephan202：對不起，我認爲它本身應該是一個完全獨立的問題！ – 2009-07-10 15:43:43

標準Python列表沒有以任何形式排序。標準heapq模塊可用於追加O（log n）並刪除O（log n）中的最小值，但不是定義中的排序列表。

Python的平衡樹有多種實現方式可以滿足您的需求，例如， rbtree，RBTree或pyavl。

來源

2009-07-10 14:26:45

+ 1爲rbtree，它工作得很好（但包含本機代碼;不是純粹的python，可能不那麼容易部署） – Will 2011-05-13 12:34:07

雖然它尚未提供自定義搜索功能，但heapq模塊可能會滿足您的需求。它使用常規列表實現堆隊列。你必須編寫自己的高效成員測試，利用隊列的內部結構（可以在O（log n），我會說......）。有一個缺點：提取排序列表具有複雜性O（n log n）。

來源

2009-07-10 14:43:24 Stephan202

雖然我還是從來沒有檢查基本的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 lists are actually arrays（不是說，跳過列表等）。那麼，我想他們必須是簡單的東西，但就我而言，這個名字有點誤導。

所以，如果我沒有記錯的話，平分線/列表速度很可能是：

的推（）：爲最壞的情況爲O（n）;
搜索：如果我們認爲數組索引的速度爲O（1），搜索應該是O（log（n））操作;
爲列表創建：O（N）應在列表複製的速度，否則它的O（1）對同一列表）

UPD。繼評論中的討論後，讓我在這裏鏈接這些SO問題：How is Python's List Implemented和What is the runtime complexity of python list functions

來源

2011-05-25 19:59:28

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

來源

2012-10-10 22:18:25 Fan

是否有特定的原因爲您的大O的要求？或者你只是想讓它變快？ sortedcontainers模塊是純Python和快速的（就像blist和rbtree那樣快速的C實現）。

performance comparison顯示其基準更快或與blist的排序列表類型相當。還要注意，rbtree，RBTree和PyAVL提供了排序字典和集合類型，但沒有排序列表類型。

如果性能是一項要求，請務必記住基準。一個能夠證明快速使用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

來源

2014-03-24 17:52:26 GrantJ

import bisect 

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

來源

2014-08-03 03:59:14 Dave31415

我會用biscect或sortedcontainers模塊。我並不是很有經驗，但我認爲heapq模塊可以工作。它包含一個Heap Queue

來源

2015-07-31 01:26:19 Slass33

python是否有排序列表？

回答

相關問題