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

uathttae1年前 ⋅ 1454 阅读

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 可以用于需要排序集合的场景,例如:

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

    相关推荐