Sorted Containers -- 排序列表、排序字典、排序集合
项目描述
Sorted Containers 是一个Apache2许可的 排序集合库，使用纯Python编写，并且速度与C扩展相当。
Python的标准库非常出色，直到你需要一个排序集合类型。许多人会证明没有它是可以走得很远的，但当你真正需要排序列表、排序字典或排序集合时，你会面临十几种不同的实现，其中大多数使用没有良好文档和基准测试的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上述所有操作都运行在比线性时间更快的速度。上述演示也几乎需要1GB的内存来运行。当排序列表乘以一千万时，它存储了从“a”到“e”的每个元素的十个亿个引用。每个引用在排序容器中需要8个字节。这几乎无法超越，因为它是每个对象的指针成本。它也比典型的二叉树实现（例如红黑树、AVL树、AA树、伸展树、Treap等）的66%低，其中每个节点也必须存储指向子节点的两个指针。
排序容器消除了Python排序集合的所有工作 - 使您的部署和使用Python变得简单。无需安装C编译器或预先构建和分发自定义扩展。性能是一个特性，测试覆盖率达到了100%，使用了单元测试和数小时的压力测试。
用户评价
亚历克斯·马尔泰利，Python软件基金会会员
“好东西！……我喜欢将排序容器拆分成更小的“片段”以避免O(N)插入成本的简单、有效的实现思想。”
杰夫·诺普，《编写Python的优美风格》和Python培训师
“最后那部分‘快如C扩展’很难相信。我需要一些性能比较来证实这一点。作者在文档中包含了这些内容。它是。”
凯文·塞缪尔，Python和Django培训师
我非常惊讶，不仅因为代码质量很高（它非常易读，注释比代码还多，哇），而且实际投入在非代码上的工作量也很大：文档、基准测试、实现说明。甚至git日志也很干净，单元测试在Python 2和3上都能正常运行。
马克·萨默菲尔德，为Python排序集合发出的简短呼吁
Python的“电池包含”标准库似乎缺少了一个电池。而且“我们以前从未有过它”的论调已经不再新鲜。现在是时候让Python提供一套完整的集合类，包括排序集合了。
排序容器被用于诸如：Zipline（Quantopian的算法交易库）、Angr（加州大学圣塔芭芭拉分校的二进制分析平台）、Trio（异步I/O库）和Dask Distributed（由Continuum Analytics支持的分布式计算库）等流行的开源项目中。
特性
纯Python实现
全面文档
基准比较（替代方案、运行时间、负载因子）
100%测试覆盖率
数小时的压力测试
性能很重要（通常比C实现更快）
兼容API（几乎与旧版blist和bintrees模块相同）
功能丰富（例如，获取排序字典中的五个最大键：d.keys()[-5:])
实用设计（例如，SortedSet是一个Python集合，具有SortedList索引）
在Python 3.7上开发
在CPython 2.7、3.2、3.3、3.4、3.5、3.6、3.7和PyPy、PyPy3上测试
快速入门
$ pip install sortedcontainers
您可以使用Python内置的help函数在解释器中访问文档。help适用于排序容器中的模块、类和方法。
>>> import sortedcontainers
>>> help(sortedcontainers)
>>> from sortedcontainers import SortedDict
>>> help(SortedDict)
>>> help(SortedDict.popitem)文档
排序容器的完整文档可在http://www.grantjenks.com/docs/sortedcontainers/找到。
用户指南
用户指南提供了对排序容器的介绍以及广泛的功能比较和分析。
社区指南
社区指南提供了关于排序容器的发展信息，包括支持、实现和历史细节。
API 文档
API 文档提供了排序容器包中特定函数、类和模块的信息。
演讲
资源
排序容器许可证
版权所有 2014-2019 Grant Jenks
根据Apache许可证版本2.0（“许可证”）授权；除非适用法律要求或经书面同意，否则不得使用此文件，除非遵守许可证。您可以在以下位置获取许可证副本：
除非适用法律要求或书面同意，否则在许可证下分发的软件按“原样”基础分发，不提供任何明示或暗示的保证或条件。有关许可证下管理许可和限制的具体语言，请参阅许可证。
