Python [sortedcontainers]有序容器库使用不完全指南

Python [sortedcontainers]有序容器库使用不完全指南

---

文档： https://grantjenks.com/docs/sortedcontainers/

---

简介：

sortedcontainers是一个纯Python开发的排序容器库。这里的容器指的是字典、列表、集合这样的数据结构，不是docer之类的容器技术。简单的说就是，使用该库中类创建的列表、字典或集合，都是自动排序的，同时这些类还提供了像二分查找这样的用于有序数据结构的常用算法。
该库虽然使用纯Python开发，但却号称拥有媲美甚至超越 C扩展 的速度。

Python标准库提供的容器已经非常好用了，直到……你需要一个真正的排序列表、排序字典或排序集合。sortedcontainers可以提供自带排序功能的上述容器，且排序算法的时间复杂度是好于线性时间的。同时，其实现相比于典型的使用二叉树（如，red-black tree、AVL-tree、AA-tree、Play-tree、Treap等）节省了66%的内存开销（因为树结构要存储指向子节点的指针，指针会占据额外空间，在大规模数据上尤其明显）。

Sorted Containers将Python 排序集合的工作都分离了出来，使得部署和使用Python都更加容易了，你不必在安装C编译器、预构建和分发自定义 C扩展。Sorted Containers拥有优异的性能表现、100%的单元测试覆盖率以及数小时的压力测试通过率。

---

特性：

• 纯Python开发
• 全文档覆盖
• 提供性能基准比较（benchmark comparison）：可替换性、运行时、负载因子（alternatives、runtimes、load-factors）
• 100% 测试覆盖
• 数小时压力测试
• 性能重要（常快于C语言实现）
• 具有兼容性的API（几乎与旧的 blist 和 bintree 模块完全相同）
• 功能丰富（如，查找排序字典中最大的5个key：d.keys()[-5:]）
• 务实的设计（如， SortedSet是一个带有SortedList索引的Python set）
• 基于python 3.7开发
• 在CPython 2.7，3.2，3.3, 3.4，3.5,3.6, 3.7，以及PyPy, PyPy3上进行了测试

---

安装：

• 从pypi进行安装：pip install sortedcontainers
• 从源码安装，sortedcontainers的github项目有着积极的开发提交，若果想体验最新的功能，可以 git clone git://github.com/grantjenks/python-sortedcontainers.git克隆仓库后，使用 python setup.py install 进行安装使用。

---

使用：

sortedcontainers提供的常用数据结构有以下几种：

• Sorted List
• Sorted-key List
• Sorted Dict
• Sorted Set

---

1. Sorted List：

sortedcontainers的核心就是可变序列数据类型 SortedList。
排序的列表值必须具有可比性。当值存储在排序列表中时，它们的总排序不能更改。SortedList会维持其包含的数据值为升序状态。与 Python 的内置列表数据类型一样，SortedList 支持元素重复和快速随机访问索引。

• 创建：

  from sortedcontainers import SortedList
  sl = SortedList()
  1
  2

• 更新：
  可以使用update() 或 add() 方法向SortedList中添加多个或单个新元素，执行操作时列表会一直保持有序状态：

  sl.update([5, 1, 3, 4, 2])
  sl  # SortedList([1, 2, 3, 4, 5])
  sl.add(0)
  sl  # SortedList([0, 1, 2, 3, 4, 5])
  1
  2
  3
  4

• 删除：
  有多种方法可以按照值或者索引来删除元素。
  按照值删除：discard(), remove()
  按照索引删除：pop(), __delitem__()对应使用del关键字
  删除所有数据：clear()

  sl  # SortedList([0, 1, 2, 3, 4, 5])
  sl.remove(0)
  sl.discard(1)
  sl  # SortedList([2, 3, 4, 5])
  sl.pop()  # 5
  del sl[1]
  sl  # SortedList([2, 4])
  sl.clear()  
  sl  # []
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 查找：
  因为SortedList是有序的，所以支持通过值或者索引进行高效的查找。
  当通过索引访问值时，SortedList 可以用作一个 order statistic tree 顺序统计树。与执行线性扫描性能不同，可以通过对树的内部结构重复进行二分查找，在对数时间内找到值。
  查找方法： __contains__(), count(), index(), bisect_left(), bisect_right(), 和 __getitem__().

  sl = SortedList('abbcccddddeeeee')
  'f' in sl  # False， 对应__contains__()方法
  sl.count('e')  # 5
  sl.index('c')  # 3
  sl[3]  # 'c'
  sl.bisect_left('d')  # 6 二分查找左边界
  sl.bisect_right('d')  # 10 二分查找右边界
  sl[6:10]  # ['d', 'd', 'd', 'd']
  1
  2
  3
  4
  5
  6
  7
  8

• 迭代：
  SortedList 也提供用于迭代元素的几种方法.
  序列常用的迭代器：__iter__(), __reversed__()
  通过值或索引进行迭代：irange(), islice()
  这些方法生成的迭代器比重复索引 SortedList 更快。

  sl = SortedList('acegi')
  list(iter(sl))  # ['a', 'c', 'e', 'g', 'i']
  list(reversed(sl))  # ['i', 'g', 'e', 'c', 'a']
  
  list(sl.irange('b', 'h'))  # ['c', 'e', 'g'] 通过值切片
  list(sl.islice(1, 4))  # ['c', 'e', 'g'] 通过索引切片
  1
  2
  3
  4
  5
  6

• 运算操作：
  SortedList 还支持典型的序列操作 __add__() 和 __mul__() 产生他的原地副本（in-place counterparts）。

  sl = SortedList('abc')
  # 产生副本，不影响原对象
  sl + sl  # SortedList(['a', 'a', 'b', 'b', 'c', 'c']) 
  sl * 3  # SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
  
  # 将结果赋值给原对象
  sl += 'de'
  sl  # SortedList(['a', 'b', 'c', 'd', 'e'])
  sl *= 2
  sl  # SortedList(['a', 'a', 'b', 'b', 'c', 'c', 'd', 'd', 'e', 'e'])
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 未实现功能：
  尽管 SortedList 实现了大多数可变序列方法，但还有五个方法没有实现：直接赋值、reverse()、append()、extend()、insert()。这些方法中的每一个都在 SortedList 不支持的索引处分配一个值。

  >>> sl = SortedList('abcde')
  >>> sl[2] = 'c'
  Traceback (most recent call last):
    ...
  NotImplementedError: use ``del sl[index]`` and ``sl.add(value)`` instead
  
  >>> sl.reverse()
  Traceback (most recent call last):
    ...
  NotImplementedError: use ``reversed(sl)`` instead
  
  >>> sl.append('f')
  Traceback (most recent call last):
    ...
  NotImplementedError: use ``sl.add(value)`` instead
  
  >>> sl.extend(['f', 'g', 'h'])
  Traceback (most recent call last):
    ...
  NotImplementedError: use ``sl.update(values)`` instead
  
  >>> sl.insert(5, 'f')
  Traceback (most recent call last):
    ...
  NotImplementedError: use ``sl.add(value)`` instead
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25

  其实可以这样理解，这种想向某个索引插入或追加数据的行为是没有作用的，数据进入SortedList后会被立即排序到应在所在的索引位置，而不能固定在我们想要制定的位置。
  SortedList 在进行比较运算时，与其他序列类型一样也使用词典排序。

SortedList API文档：https://grantjenks.com/docs/sortedcontainers/sortedlist.html

---

2. Sorted-key List:

Sorted Containers 项目还维护一个专门的类似排序列表（sorted-list-like）的类型，它可以接受一个 Python内置sorted()方法中的键参数（key-parameters）对数据进行排序。
SortedKeyList 提供与 SortedList 相同的功能，但它基于使用的键函数维护所包含值的顺序。这简化了原本需要的装箱（boxing）和取消装箱（unboxing）的模式。

• 创建：

  from operator import neg
  from sortedcontainers import SortedKeyList
  skl = SortedKeyList(key=neg)  # 使用neg函数（取负值）作为key用于排序
  1
  2
  3

  Key 函数提取一个比较键，用于对列表中的项进行排序。在上面的例子中，我们应用了求逆运算符。在上面的示例中，整数的排序列表将按降序排序。
  还可以使用 SortedList 类型通过向初始时的参数传递键函数来构造 SortedKeyList。

  from sortedcontainers import SortedList
  
  values = SortedList([1, 2, 3, 4, 5], key=neg)  #设置key参数
  values  # SortedKeyList([5, 4, 3, 2, 1], key=<built-in function neg>)
  isinstance(values, SortedList)  # True
  issubclass(SortedKeyList, SortedList)  # True 子类关系
  values.key  # <built-in function neg>
  1
  2
  3
  4
  5
  6
  7

• 额外操作：
  SortedKeyList相比于SortedList 额外提供了三个方法：bisect_key_left(), bisect_key_right(), irange_key()。这些方法都接受其对应的 SortedList 的键而不是值。

  skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
  skl  # SortedKeyList([5, 4, 3, 2, 1], key=<built-in function neg>)
  skl.bisect_key_left(-4.5)  # 1  # neg(value)=-4.5的值，即对应4.5的位置
  skl.bisect_key_right(-1.5)  # 4
  list(skl.irange_key(-4.5, -1.5))  # [4, 3, 2]
  1
  2
  3
  4
  5

SortedKeyList API文档：https://grantjenks.com/docs/sortedcontainers/sortedlist.html#sortedkeylist

---

3. Sorted Dict：

SortedDict是构建在Python内置的dict数据类型和SortedList之上的一种可变映射数据类型。SortedDict的键是按照排序顺序进行维护的。
SortedDict的设计很简单：它继承自dict，提供存储item的能力，并维护一个键的排序列表。SortedDict键必须是可散列（hashable）和可比较的。键的散列值和总顺序在存储在SortedDict中时不得更改。

• 创建：

  from sortedcontainers import SortedDict
  sd = SortedDict()
  1
  2

• 更新：
  items可使用__setitem__()、update()、setdefault() 添加到字典中，执行操作时，字典的键保持有序。

  sd['e'] = 5
  sd['b'] = 2
  sd  # SortedDict({'b': 2, 'e': 5})
  
  sd.update({'d': 4, 'c': 3})
  sd  # SortedDict({'b': 2, 'c': 3, 'd': 4, 'e': 5})
  
  sd.setdefault('a', 1) # 1 如果键位于排序后的结果中，则返回其值。如果键不在排序的结果中，则插入带有默认值的键并返回默认值。
  sd  # SortedDict({'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5})
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 删除：
  通过键删除item：__delitem__(), pop()
  通过索引删除item：popitem()
  删除所有数据：clear()

  sd  # SortedDict({'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5})
  
  del sd['d']
  sd.pop('c')  # 3
  
  sd.popitem(index=-1)  # ('e', 5)
  sd  # SortedDict({'a': 1, 'b': 2})
  1
  2
  3
  4
  5
  6
  7

• 查找：
  因为 SortedDect 同时使用 dict 和 SortedList，所以有许多方法可以从每种类型查找键。
  映射类型支持的查找方式有：__getitem__(), __contains__(), get(), peekitem()
  序列类型支持的查找方法和上面SortedList的查找方法一样，如：bisect_left(), bisect_right()， index(), irange()等

  sd  # SortedDict({'a': 1, 'b': 2})
  
  sd['b']  # 2
  'c' in sd  # False
  sd.get('z') is None  # True
  sd.peekitem(index=-1)  # ('b', 2)
  
  sd.bisect_right('b')  # 2
  sd.index('a')  # 0
  list(sd.irange('a', 'z'))  # ['a', 'b']
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 字典视图（view函数）：
  keys, items 和 values 视图还支持集合语义和序列语义，并提供了按索引进行查找的优化方法。

  sd  # SortedDict({'a': 1, 'b': 2})
  
  keys = sd.keys()
  keys[0]  # 'a'
  
  items = sd.items()
  items[-1]  # ('b', 2)
  
  values = sd.values()
  values[:]  # [1, 2]
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 键函数：
  SortedDect 在初始化时支持一个额外的位置参数。位置参数必须位于用于初始化 SortedDect 中的项的任何序列、映射或关键字参数之前。第一个位置参数是一个可选的可调用键函数key-function，用于从 SortedDect 的键中提取比较键（对字典的key执行key-function计算，获得排序依据）。
  例如，按降序构造带有整数键的 SortedDect:

  sd = SortedDict(neg, enumerate('abc', start=1))  # key-function使用neg函数
  sd  # SortedDict(<built-in function neg>, {3: 'c', 2: 'b', 1: 'a'})
  keys = sd.keys()
  list(keys)  # [3, 2, 1]
  1
  2
  3
  4

• 缺省值：
  因为SortedDict 继承自dict，__missing__ 方法可以用来给缺省的key提供一个默认值。自定义 __missing__ 方法可以创建类似 collections.defaultdict 的数据类型。

  class DefaultSortedDict(SortedDict):
      def __missing__(self, key):  # 自定义该函数
          return 0
  
  dsd = DefaultSortedDict()
  dsd['z']  # 0
  1
  2
  3
  4
  5
  6

SortedDict API文档：https://grantjenks.com/docs/sortedcontainers/sorteddict.html

---

4. Sorted Set：

SortedSet是一种基于内置set类型和SortedList类型之上的可变集合数据结构。SortedSet的值是按照排序顺序维护的。
SortedSet的设计也很简单：它使用Python内置的set类来提供集合相关的操作，同时维护一个值的排序列表。存储在 SortedSet 中的值必须是可散列（hashable）和可比较的。值的哈希值和总排序在存储在 SortedSet 中时不得更改。

• 创建：

  from sortedcontainers import SortedSet
  ss = SortedSet()
  1
  2

• 更新、删除等操作：
  SortedSet实现了 核心可变集合（core mutable set） 方法的优化版本：__contains__(), add(), update(), discard() 和更严格的remove()。

  ss.add('c')
  ss.add('a')
  ss.add('b')
  ss  # SortedSet(['a', 'b', 'c'])
  
  'c' in ss  # True
  
  ss.discard('a')
  ss.remove('b')
  _ = ss.update('def')
  ss  # SortedSet(['c', 'd', 'e', 'f'])
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

  SortedSet也有类似于序列的操作，如__getitem__(), __reversed__()方法。另外还包括可变序列的方法：__delitem__() 和 pop() 。

  ss[0]  # 'c'
  list(reversed(ss))  # ['f', 'e', 'd', 'c']
  del ss[0]
  ss.pop(index=-1)  # 'f'
  
  ss  # SortedSet(['d', 'e'])
  1
  2
  3
  4
  5
  6

• 集合操作：
  像 difference(), intersection(), symmetric_difference() 和 union() 等创建原地副本和集合操作也都支持。

  abcd = SortedSet('abcd')
  cdef = SortedSet('cdef')
  
  abcd.difference(cdef)  # SortedSet(['a', 'b']) 差集
  abcd.intersection(cdef)  # SortedSet(['c', 'd'])  交集
  abcd.symmetric_difference(cdef)  # SortedSet(['a', 'b', 'e', 'f']) 对称差
  abcd.union(cdef)  # SortedSet(['a', 'b', 'c', 'd', 'e', 'f']) 并集
  abcd | cdef  # SortedSet(['a', 'b', 'c', 'd', 'e', 'f'])  并集，副本
  abcd |= cdef
  abcd  # SortedSet(['a', 'b', 'c', 'd', 'e', 'f'])  并集，赋值给原对象
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 序列方法：
  几个像 bisect(), index(), irange(), 和islice() 这样的SortedList类方法也在SortedSet中提供。

  ss = SortedSet('abcdef')
  
  ss.bisect('d')  # 4
  ss.index('f')  # 5
  list(ss.irange('b', 'e'))  # ['b', 'c', 'd', 'e']
  list(ss.islice(-3))  # ['d', 'e', 'f']
  1
  2
  3
  4
  5
  6

• 键函数：
  与 SortedList 类似，也可以使用一个附加的键参数，通过一个用于提取比较键的可调用对象来初始化 SortedSet。

  ss = SortedSet([1, 2, 3], key=neg)
  ss  # SortedSet([3, 2, 1], key=<built-in function neg>)
  1
  2

• 比较：
  排序集合比较时会使用子集（subset）和超集（superset）关系。
  当且仅当每个排序集的每个元素都包含在另一个中（每个元素都是另一个的子集）时，两个排序集相等。
  当且仅当第一个排序集是第二个排序集的适当子集（是子集，但不相等）时，排序集小于另一个排序集。
  当且仅当第一个排序集是第二个排序集的适当超集（是超集，但不相等）时，排序集大于另一个排序集。
  排序集的比较语义并不定义总排序（不产生新的排序集合，不对原排序集合的总排序产生影响）。

SortedSet API文档：https://grantjenks.com/docs/sortedcontainers/sortedset.html

---

警告：

sorted containers 数据类型有三个要求：

1. 比较的值或键必须具有总排序（total ordering，全序关系）。
2. 比较的值或键保存在sorted containers中时必须是不能更改的。
3. 如果使用键函数参数，则相等的值必须具有相等的键。
   如果违反了这三个要求中的任何一个，那么sorted containers 的保证就是无效的，它将不能正常工作。虽然可以设计没有这些要求的有用数据类型，但这些是排序容器的注意事项，它们与替代实现的注意事项相匹配。这些需求中的每一个都允许进行优化，它们一起试图在功能和性能之间找到正确的折衷。
   尤其是上述的第三条要求，在重写了富比较方法的类中往往会因为数据的更新导致所使用的key-function失效而不能排序。

警告情况示例：https://grantjenks.com/docs/sortedcontainers/introduction.html#caveats

---

性能比较：

https://grantjenks.com/docs/sortedcontainers/performance.html

详细的性能测试图表可以从上面的连接查看，总体来说，sortedcontainers提供了媲美C扩展和Cython实现库的速度。同时还IT拱了不同负载情况和不同运行时环境（python2.7，python3.7 和PyPy）情况下的个操作用时统计。感兴趣的可以自己读图。

---

类似项目：

部分项目已经长时间不在维护了。

• blist：https://pypi.org/project/blist/
• bintrees：https://pypi.org/project/bintrees/
• banyan: https://pypi.org/project/Banyan/

从其他项目迁移到sortedcontainers的注意事项：https://grantjenks.com/docs/sortedcontainers/introduction.html#migrating