SortedContainers 是一个排序集合库，用纯 Python 编写，速度与 C 扩展一样快

uathttae ⋅ 1年前 ⋅ 1463 阅读

https://github.com/grantjenks/python-sortedcontainers

https://grantjenks.com/docs/sortedcontainers/     官网文档

https://grantjenks.com/docs/sortedcontainers/performance.html  有一个好的基准测试的性能比较用起来让人放心，sortedcontainers与其他库比较各方面性能都比较优秀

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

特征

  • 纯Python
  • 完全记录
  • 基准比较（替代方案、运行时间、负载因子）
  • 100% 测试覆盖率
  • 压力测试时间
  • 性能很重要（通常比 C 实现更快）
  • 兼容的 API（与旧的 blist 和 bintrees 模块几乎相同）
  • 功能丰富（例如，获取已排序字典中最大的五个键：d.keys()[-5:]）
  • 实用设计（例如 SortedSet 是一个带有 SortedList 索引的 Python 集）
  • 基于 Python 3.10 开发
  • 使用 CPython 3.7、3.8、3.9、3.10 和 PyPy3 进行测试
  • 在 Linux、Mac OSX 和 Windows 上测试

性能确实很nice

精益求精 精工利器 拍案叫绝 SortedContainers 用纯 Python 排序 编写

有哪些使用场景？

SortedContainers 可以用于需要排序集合的场景，例如：

1. 缓存数据：使用 SortedDict 可以存储缓存数据，并从中搜索指定的元素，查找速度快，同时保持数据的有序性。

2. 任务调度：使用 SortedList 可以按照任务的优先级顺序调度任务，优先级高的任务先执行。

3. 倒排索引：使用 SortedList 可以将倒排索引按照关键字的出现频率排序，加速文本索引和搜索。

4. 数据分析：SortedSet 可以将数据按照大小进行排序，便于统计和分析。

总之，SortedContainers 可以应用于任何需要排序的场景，例如搜索、排序、过滤、分组和聚合等操作。

有哪些类似的项目？

1. bisect - 内置 Python 模块，提供了对序列的二分查找和插入操作。
2. heapq - 内置 Python 模块，提供了堆数据结构的实现。
3. sortedlist - 实现了一个基于有序列表的集合数据类型。
4. sortedset - 实现了一个基于有序集合的集合数据类型。
5. blist - 提供了对序列的操作，比 Python 内置的列表实现更优秀，但无法与 SortedContainers 相比。
6. bintrees - 实现了基于 AVL 树和红黑树的二叉树数据结构。
7. treap - 实现了基于搜索树和堆的数据结构，和 SortedContainers 类似都提供了排序、映射和集合的功能。

有哪些优缺点？

优点：

1. SortedContainers 可以非常快速地进行排序，因为它使用的是基于二分查找的排序算法。

2. 由于 SortedContainers 是纯 Python 编写的，因此可以跨平台使用，不需要额外的 C 扩展或其他外部依赖库。

3. SortedContainers 支持添加、删除和查找元素，并且与 Python 的内置数据类型兼容，因此可以轻松地集成到 Python 代码中。

4. SortedContainers 的 API 非常简单易用，可以方便地完成各种排序集合操作，如查找、遍历、排序等。

缺点：

1. SortedContainers 可能会占用更多的内存空间，因为它需要存储额外的元数据来保证集合的有序性。

2. SortedContainers 的性能可能会受到数据规模的影响，当数据集非常大时，排序的时间复杂度可能会变得较高。

3. 相比于一些其他的排序集合库，SortedContainers 的功能可能略微有限，没有提供一些高级的功能，如聚合、分组等。

全部评论: 0 条

    相关推荐