Python SortedContainers Module

一款纯 python 写的对列表、字典、集合排序的模块

Sorted Containers 是Apache2 许可的 Sorted Collections 库，用纯 Python 编写，并且速度与 C 扩展一样快。在需要排序的集合类型之前，Python 的标准库非常有用。许多人会证明，即使没有排序，您也可以真正走得很远，但是，当您真正需要排序列表，排序 dict 或排序集时，您将面临许多不同的实现，其中大多数使用 C 扩展而没有出色的文档和基准。在 Python 中，我们可以做得更好。我们可以用纯 Python 做到这一点！

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

上面显示的所有操作都比线性时间快。上面的演示还占用了将近 1 GB 的内存。当排序列表乘以一千万时，它将存储一千万个对“ a”至“ e”中每一个的引用。每个引用在已排序的容器中需要八个字节。很难克服，因为这是指向每个对象的指针的代价。与每个节点还必须存储两个指向子节点的指针的典型二叉树实现（例如，红黑树，AVL-Tree，AA-Tree，Splay-Tree，Treap等）相比，开销也减少了66％。Sorted Containers 将所有工作从 Python 分类集合中剔除-简化了 Python 的部署和使用。无需安装 C 编译器或预先构建和分发自定义扩展。性能是一项功能，测试具有100％的单元测试覆盖率和数小时的压力。

安装：

$ pip install sortedcontainers

可以使用 Python 的内置帮助功能访问解释器中的文档。该帮助适用于已排序容器中的模块，类和方法。

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

GitHub地址：https://github.com/grantjenks/python-sortedcontainers

也可使用匿名函数排序

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

Python SortedList

1.添加值

SortedList.add(value) 添加新元素，并排序。时间复杂度O(log(n)).
SortedList.update(iterable) 对添加的可迭代的所有元素排序。时间复杂度O(k*log(n)).

2.移除值

SortedList.clear() 移除所有元素。时间复杂度O(n).
SortedList.discard(value) 移除一个值元素，如果元素不存在，不报错。时间复杂度O(log(n)).
SortedList.remove(value) 移除一个值元素，如果元素不存在，报错ValueError。时间复杂度O(log(n)).
SortedList.pop(index=-1) 移除一个指定下标元素，如果有序序列为空或者下标超限，报错IndexError. 时间复杂度O(log(n

3.查找

SortedList.bisect_left(value) 查找元素可以插入的位置下标，如果这个 value 已经存在，则插入已经存在的所有 values 之前（左侧）.时间复杂度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) 查找元素可以插入的位置下标，如果这个value已经存在，则插入已经存在的所有values之后（右侧）。时间复杂度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) 查找元素出现的次数。时间复杂度O(log(n)).

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

SortedList.index(value, start=None, Stop=None) 查找索引范围[start,stop）内第一次出现 value 的索引，如果 value 不存在，报错ValueError. 时间复杂度O(log(n)).

4.迭代值

SortedList.irange(minimun=None, maximum=None, inclusive=True, True, reverse=False) 返回 value = [minimun，maximum]之间的可迭代值，inclusive = Ture, True 第一个True表示包括索引minimun， 第二个Ture表示包括索引maximum，reverse是表示返回的可迭代值是否反转。
SortedList.islice(start=None, stop=None, reverse=False) 返回index=[start, stop)之间的可迭代值（切片）。

5. 其他

SortedList.copy() 返回一个浅拷贝有序序列。时间复杂度O(n)。
浅拷贝（1）直接赋值，默认浅拷贝传递对象的引用而已，原始列表改变，被赋值的列表也会做相同的改变。

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 函数，浅拷贝传递子对象的引用，原始数据改变，只有子对象会改变。

a = [[1],2,3]
b = a.copy()
a
Out[85]: [[1], 2, 3]
b
Out[86]: [[1], 2, 3]
# 对象不改变
a.append(4)
a
Out[88]: [[1], 2, 3, 4]
b
Out[89]: [[1], 2, 3]
# 子对象跟着改变
a[0].append(2)
a
Out[91]: [[1, 2], 2, 3, 4]
b
Out[92]: [[1, 2], 2, 3]

315. 计算右侧小于当前元素的个数

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]

剑指 Offer 51. 数组中的逆序对

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

最后

以上就是平常鸭子为你收集整理的Python SortedListPython SortedContainers ModulePython SortedList315. 计算右侧小于当前元素的个数剑指 Offer 51. 数组中的逆序对的全部内容，希望文章能够帮你解决Python SortedListPython SortedContainers ModulePython SortedList315. 计算右侧小于当前元素的个数剑指 Offer 51. 数组中的逆序对所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。