Python SortedContainers Module

一款純 python 寫(xiě)的對(duì)列表、字典、集合排序的模塊

Sorted Containers 是Apache2 許可的 Sorted Collections 庫(kù)，用純 Python 編寫(xiě)，并且速度與 C 擴(kuò)展一樣快。

在需要排序的集合類型之前，Python 的標(biāo)準(zhǔn)庫(kù)非常有用。許多人會(huì)證明，即使沒(méi)有排序，您也可以真正走得很遠(yuǎn)，但是，當(dāng)您真正需要排序列表，排序 dict 或排序集時(shí)，您將面臨許多不同的實(shí)現(xiàn)，其中大多數(shù)使用 C 擴(kuò)展而沒(méi)有出色的文檔和基準(zhǔn)。

在 Python 中，我們可以做得更好。

我們可以用純 Python 做到這一點(diǎn)！

 from sortedcontainers import SortedList
 sl = SortedList(['e', 'a', 'c', 'd', 'b'])
 sl
SortedList(['a', 'b', 'c', 'd', 'e'])
 sl *= 10_000_000
 sl.count('c')
10000000
 sl[-3:]
['e', 'e', 'e']
 from sortedcontainers import SortedDict
 sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
 sd
SortedDict({'a': 1, 'b': 2, 'c': 3})
 sd.popitem(index=-1)
('c', 3)
 from sortedcontainers import SortedSet
 ss = SortedSet('abracadabra')
 ss
SortedSet(['a', 'b', 'c', 'd', 'r'])
 ss.bisect_left('c')
2

上面顯示的所有操作都比線性時(shí)間快。上面的演示還占用了將近 1 GB 的內(nèi)存。當(dāng)排序列表乘以一千萬(wàn)時(shí)，它將存儲(chǔ)一千萬(wàn)個(gè)對(duì)“ a”至“ e”中每一個(gè)的引用。每個(gè)引用在已排序的容器中需要八個(gè)字節(jié)。很難克服，因?yàn)檫@是指向每個(gè)對(duì)象的指針的代價(jià)。

與每個(gè)節(jié)點(diǎn)還必須存儲(chǔ)兩個(gè)指向子節(jié)點(diǎn)的指針的典型二叉樹(shù)實(shí)現(xiàn)（例如，紅黑樹(shù)，AVL-Tree，AA-Tree，Splay-Tree，Treap等）相比，開(kāi)銷(xiāo)也減少了66％。

Sorted Containers 將所有工作從 Python 分類集合中剔除-簡(jiǎn)化了 Python 的部署和使用。

無(wú)需安裝 C 編譯器或預(yù)先構(gòu)建和分發(fā)自定義擴(kuò)展。性能是一項(xiàng)功能，測(cè)試具有100％的單元測(cè)試覆蓋率和數(shù)小時(shí)的壓力。

安裝：

$ pip install sortedcontainers

可以使用 Python 的內(nèi)置幫助功能訪問(wèn)解釋器中的文檔。該幫助適用于已排序容器中的模塊，類和方法。

 import sortedcontainers
 help(sortedcontainers)
 from sortedcontainers import SortedDict
 help(SortedDict)
 help(SortedDict.popitem)

也可使用匿名函數(shù)排序

class sortedcontainers.SortedList(iterable=None, key=None)

Python SortedList

1.添加值

• SortedList.add(value) 添加新元素，并排序。時(shí)間復(fù)雜度O(log(n)).
• SortedList.update(iterable) 對(duì)添加的可迭代的所有元素排序。時(shí)間復(fù)雜度O(k*log(n)).

2.移除值

• SortedList.clear() 移除所有元素。時(shí)間復(fù)雜度O(n).
• SortedList.discard(value) 移除一個(gè)值元素，如果元素不存在，不報(bào)錯(cuò)。時(shí)間復(fù)雜度O(log(n)).
• SortedList.remove(value) 移除一個(gè)值元素，如果元素不存在，報(bào)錯(cuò)ValueError。時(shí)間復(fù)雜度O(log(n)).
• SortedList.pop(index=-1) 移除一個(gè)指定下標(biāo)元素，如果有序序列為空或者下標(biāo)超限，報(bào)錯(cuò)IndexError. 時(shí)間復(fù)雜度O(log(n

3.查找

SortedList.bisect_left(value) 查找元素可以插入的位置下標(biāo)，如果這個(gè) value 已經(jīng)存在，則插入已經(jīng)存在的所有 values 之前（左側(cè)）.時(shí)間復(fù)雜度O(log(n)).

s = SortedList([1,2,3,9,8,6,5,5,5,5,5])
s.bisect_left(5)
Out[5]: 3
s
Out[6]: SortedList([1, 2, 3, 5, 5, 5, 5, 5, 6, 8, 9])

SortedList.bisect_right(value) 查找元素可以插入的位置下標(biāo)，如果這個(gè)value已經(jīng)存在，則插入已經(jīng)存在的所有values之后（右側(cè)）。時(shí)間復(fù)雜度O(log(n)).

s.bisect_right(5)
Out[7]: 8
s
Out[8]: SortedList([1, 2, 3, 5, 5, 5, 5, 5, 6, 8, 9])

SortedList.count(value) 查找元素出現(xiàn)的次數(shù)。時(shí)間復(fù)雜度O(log(n)).

s.count(5)
Out[9]: 5

SortedList.index(value, start=None, Stop=None) 查找索引范圍[start,stop）內(nèi)第一次出現(xiàn) value 的索引，如果 value 不存在，報(bào)錯(cuò)ValueError. 時(shí)間復(fù)雜度O(log(n)).

4.迭代值

SortedList.irange(minimun=None, maximum=None, inclusive=True, True, reverse=False) 返回 value = [minimun，maximum]之間的可迭代值，inclusive = Ture, True 第一個(gè)True表示包括索引minimun， 第二個(gè)Ture表示包括索引maximum，reverse是表示返回的可迭代值是否反轉(zhuǎn)。

SortedList.islice(start=None, stop=None, reverse=False) 返回index=[start, stop)之間的可迭代值（切片）。

5. 其他

SortedList.copy() 返回一個(gè)淺拷貝有序序列。時(shí)間復(fù)雜度O(n)。

淺拷貝（1）直接賦值，默認(rèn)淺拷貝傳遞對(duì)象的引用而已，原始列表改變，被賦值的列表也會(huì)做相同的改變。

a = [1,2,3]
b=a
b
Out[60]: [1, 2, 3]
a[0]=0
a
Out[62]: [0, 2, 3]
b
Out[63]: [0, 2, 3]

淺拷貝(2) copy 函數(shù)，淺拷貝傳遞子對(duì)象的引用，原始數(shù)據(jù)改變，只有子對(duì)象會(huì)改變。

a = [[1],2,3]
b = a.copy()
a
Out[85]: [[1], 2, 3]
b
Out[86]: [[1], 2, 3]
# 對(duì)象不改變
a.append(4)
a
Out[88]: [[1], 2, 3, 4]
b
Out[89]: [[1], 2, 3]
# 子對(duì)象跟著改變
a[0].append(2)
a
Out[91]: [[1, 2], 2, 3, 4]
b
Out[92]: [[1, 2], 2, 3]

計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)

from sortedcontainers import SortedList
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        ans = []
        #sl = SortedList() 
        q = [] # 插入排序
        for x in reversed(nums):
            #i = sl.bisect_left(x)
            i = bisect_left(q, x)
            #print(i)
            ans.append(i)
            #sl.add(x)
            insort_left(q, x)
        return ans[::-1]

數(shù)組中的逆序?qū)?/h3>

from sortedcontainers import SortedList as sl
class Solution:
    def reversePairs(self, nums: List[int]) -> int:    
        q = sl()
        ans = 0
        for i, x in enumerate(nums):
            idx = q.bisect_right(x)
            ans += i - idx
            q.add(x)           
        return ans

到此這篇關(guān)于Python中的SortedList詳解的文章就介紹到這了,更多相關(guān)SortedList詳解內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

• 以SortedList為例詳解Python的defaultdict對(duì)象使用自定義類型的方法
• 關(guān)于python類SortedList詳解

最新評(píng)論