python 排序容器
v2.1.0 JOSS
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上面显示的所有操作的运行速度都快于线性时间。上面的演示还需要近 GB 的内存才能运行。当排序列表乘以一千万时，它存储对“a”到“e”中每一个的一千万个引用。每个引用在排序容器中需要八个字节。这是很难击败的，因为它是指向每个对象的指针的成本。与典型的二叉树实现（例如红黑树、AVL-Tree、AA-Tree、Splay-Tree、Treap 等）相比，它的开销也减少了 66%，因为典型的二叉树实现的每个节点还必须存储两个指向子节点的指针。
Sorted Containers 承担了 Python 排序集合中的所有工作 - 让您轻松部署和使用 Python。无需安装 C 编译器或预构建和分发自定义扩展。性能是一项功能，测试通过单元测试和压力时间达到 100% 的覆盖率。
Alex Martelli ，Python 软件基金会研究员
“好东西！……我喜欢这种简单、有效的实现思路，即将排序的容器分割成更小的“片段”，以避免 O(N) 插入成本。”
Jeff Knupp ，《Writing Idiomatic Python》和《Python Trainer》的作者
“最后一部分，‘像 C 扩展一样快’，令人难以置信。我需要某种性能比较来确信这是真的。作者将其包含在文档中。确实如此。”
Kevin Samuel ，Python 和 Django 培训师
我非常惊讶，不仅是代码质量（它的可读性非常好，而且比代码有更多的注释，哇），还有你在代码以外的东西上投入的实际工作量：文档、基准测试、实现解释。甚至 git 日志也是干净的，并且单元测试在 Python 2 和 3 上开箱即用。
Mark Summerfield ，Python 排序集合的简短请求
Python 的“包含电池”标准库似乎缺少电池。而“我们以前从未有过这样的经历”的论点已经变得不那么重要了。 Python 是时候提供一整套开箱即用的集合类了，包括排序的集合类。
Sorted Containers 用于流行的开源项目，例如：Zipline，Quantopian 的算法交易库； Angr，加州大学圣巴巴拉分校的二进制分析平台； Trio，一个异步 I/O 库； Dask Distributed，一个由 Continuum Analytics 支持的分布式计算库。
使用 pip 安装 Sorted Containers 很简单：
$ pip 安装sortedcontainers
您可以使用 Python 的内置帮助功能访问解释器中的文档。该帮助适用于排序容器中的模块、类和方法。
> >> import sortedcontainers
> >> help ( sortedcontainers )
> >> from sortedcontainers import SortedDict
> >> help ( SortedDict )
> >> help ( SortedDict . popitem )有关排序容器的完整文档，请访问 http://www.grantjenks.com/docs/sortedcontainers/
用户指南提供了排序容器的介绍以及广泛的性能比较和分析。
该社区指南提供了有关 Sorted Containers 开发的信息以及支持、实施和历史详细信息。
API 文档提供了有关 Sorted Containers 包中的特定函数、类和模块的信息。
版权所有 2014-2024 格兰特·詹克斯
根据 Apache 许可证 2.0 版（“许可证”）获得许可；除非遵守许可证，否则您不得使用此文件。您可以在以下位置获取许可证副本：
http://www.apache.org/licenses/LICENSE-2.0
除非适用法律要求或书面同意，否则根据许可证分发的软件均按“原样”分发，不带任何明示或暗示的保证或条件。请参阅许可证，了解许可证下管理权限和限制的特定语言。
