Python 中的有序集合 (数据结构) bug 和代替品

Go module 几篇文章消耗了太多的时间，以至于今天的 10 篇文章任务可能有点难以完成，既然这样，接下来的时间我们就来一些有趣的语言下的有趣的文章

第一篇，我们要讲的 Python 中的有序集合

与其它编程语言相比较，Python 在有序集合类型方面有点不寻常，TIOBE 索引中排名前五位的编程语言中有三种包括有序列表，有序字典或有序集合 ( ordered set) 等数据类型，唯独 Python 和 C 语言是个例外，C 语言可以理解，但作为一种被称为「包含电池」的 Python ，这有点奇怪

而对此的理由有点死循环的感觉，归纳为一句话就是：Python 标准库已经包行了大量的用例，而其它的东西，则交给 PyPI ( Python 包索引 ) 来解决，

其实 PyPI 的效果非常好。事实上，Python 社区的一些特性使得 PyPI 的工作非常困难。例如，Python 喜欢Monty Python 引用，许多人发现它们不同寻常或模糊不清。正如 Phil Karlton 指出的那样，命名事情很难

collections.OrderedDict

顺便说一句，值得注意的是 Python 标准库中的 collections.OrderedDict

OrderedDict 维护添加到字典中的条目的顺序，有时条目的顺序是已排序的

>>> from collections import OrderedDict
>>> letters = [('a', 0), ('b', 1), ('c', 2), ('d', 3)]
>>> values = OrderedDict(letters)
>>> print(values)
OrderedDict([('a', 0), ('b', 1), ('c', 2), ('d', 3)])
>>> print(list(values.keys()))
['a', 'b', 'c', 'd']

我们可以继续编辑这个 OrderedDict，它会根据我们添加的键，决定是否重新排序

>>> values['e'] = 4
>>> print(list(values.keys()))
['a', 'b', 'c', 'd', 'e']

但是，这个 OrderedDict 有一个 bug，也就是并不总能保持排序顺序。如果我们删除一个键，然后再将其添加回来，那么我们将看到它附加到见的末尾

>>> del values['a']
>>> values['a'] = 0
>>> print(list(values.keys()))
['b', 'c', 'd', 'e', 'a']

Ooops!

请注意，a 位于键列表的末尾。这是有序 ( ordered) 和排序 ( sorted) 之间的区别

OrderedDict 根据插入顺序维护顺序
SortedDict 将根据键的排序顺序维护顺序

SortedContainers

几年前，我开始从 PyPI 中选择一个已排序 ( sorted ) 的集合库。起初，我被结果所震撼。计算机科学理论中有许多数据类型可以使用，每种数据类型都有各种权衡。例如，红黑树 一般用在用 Linux 内核，而前缀树 ( Tries ) 通常更节省空间并用于嵌入式系统。 B 树 ( B-Trees ) 也可以很好地处理大量项目，并且通常用于数据库中

我真正想要的是一个足够快的纯 Python 解决方案。但在这些要求的交叉点找到解决方案非常困难。大多数快速实现都是用 C 语言编写的，而且许多都没有基准测试或文档

我找不到正确的答案，所以我建造了它：Sorted Containers 。正确的答案是纯 Python。它与 Python 2 和Python 3 兼容。它很快。它功能齐全。它经过 100％的覆盖率测试和数小时的压力测试

SortedContainers 包含了 SortedList, SortedDict 和 SortedSet ，它们的实现都有着相类似的 API

>>> from sortedcontainers import SortedList, SortedDict, SortedSet
>>> values = SortedList('zaxycb')
>>> values[0]
'a'
>>> values[-1]
'z'
>>> list(values)  # Sorted order is automatic.
['a', 'b', 'c', 'x', 'y', 'z']
>>> values.add('d>>> values[3]
'd'
>>> del values[0]
>>> list(values)  # Sorted order is maintained.
['b', 'c', 'd', 'x', 'y', 'z']

SortedList，SortedDict和 SortedSet 中的每一个数据类型都和 collections 中相对应的一样的外观，游泳和嘎嘎

>>> items = SortedDict(zip('dabce', range(5)))
>>> list(items.keys())  # Keys iterated in sorted order.
['a', 'b', 'c', 'd', 'e']
>>> items['b']
2
>>> del items['c']
>>> list(items.keys())  # Sorted order is automatic.
['a', 'b', 'd', 'e']
>>> items['c'] = 10
>>> list(items.keys())  # Sorted order is maintained.
['a', 'b', 'c', 'd', 'e']

每种排序数据类型也可以与其他数据类型很好地配合使用

>>> keys = SortedSet('dcabef')
>>> list(keys)
['a', 'b', 'c', 'd', 'e', 'f']
>>> 'c' in keys
True
>>> list(keys | 'efgh')
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> list(keys & 'cde')
['c', 'd', 'e']
>>> list(keys & 'yzab')
['a', 'b']

额外的特性

除了与内建的数据类型有着相类似的 API 外，维持排序顺序为搜索和索引提供了相当大的便利

可以非常快速有效地查找值是否存在或索引值

>>> import string
>>> values = SortedList(string.lowercase)
>>> 'q' in values
True
>>> values.index('r')
17

可以按索引或按值对容器进行切片。甚至映射和集也支持数字索引和迭代

>>> items = SortedDict(zip(string.lowercase, range(26)))
>>> list(items.irange('g', 'j'))
['g', 'h', 'i', 'j']
>>> items.index('g6
>>> items.index('j9
>>> list(items.islice(6, 10))
['g', 'h', 'i', 'j']

映射还支持使用类似 Pandas iloc 的接口进行数字索引

>>> items.iloc[0]
'a'
>>> items.iloc[5]
'f'
>>> items.iloc[:5]
['a', 'b', 'c', 'd', 'e']
>>> items.iloc[-3:]
['x', 'y', 'z']