Python中SortedSet类型注解适配及性能优化方案求助

一、规避sortedcontainers类型注解报错的方法 #

1. 局部/全局忽略类型检查 #

• 在使用SortedSet的代码行添加# type: ignore注释，跳过单条语句的类型检查：

  self.adj_list = dict(zip(range(self.noNodes), [SortedSet([]) for i in range(self.noNodes)]))  # type: ignore
  

• 或者在mypy配置文件（mypy.ini或pyproject.toml）中全局忽略该库的类型缺失问题：

  [mypy]
  ignore_missing_imports = true
  
  # 更精确的配置：仅忽略sortedcontainers相关检查
  [mypy-sortedcontainers.*]
  ignore_missing_imports = true
  

2. 自定义类型存根（Stub）文件 #

创建sortedcontainers.pyi存根文件，放在项目根目录或mypy识别的stubs目录中，为SortedSet补充必要的类型注解：

from typing import Generic, Iterable, Set, TypeVar

T = TypeVar('T')

class SortedSet(Generic[T], Set[T]):
    def __init__(self, iterable: Iterable[T] = ...) -> None: ...
    def add(self, value: T) -> None: ...
    def intersection(self, other: Iterable[T]) -> SortedSet[T]: ...
    # 根据你的业务需求补充其他用到的方法注解

mypy会优先使用自定义存根文件进行类型检查，无需等待官方PR合并。

3. 类型强制转换 #

通过typing.cast将SortedSet实例转换为标准库Set类型，绕过类型检查：

from typing import cast, Set

self.adj_list = dict(zip(
    range(self.noNodes),
    [cast(Set[int], SortedSet([])) for i in range(self.noNodes)]
))

二、替代库推荐（带完整类型注解） #

如果不想处理类型兼容问题，可以直接替换为以下支持类型注解的有序集合库：

• ordered-set：纯Python实现，基于bisect模块维护有序列表，支持基础有序集合操作，自带完整类型注解，适合中小数据量场景。
• pyavl：基于AVL平衡二叉搜索树的实现，支持插入、删除、交集、并集等操作，自带类型注解，性能优于基于列表的实现。

三、基于平衡二叉搜索树的高性能有序集合 #

如果需要平衡二叉树实现的高性能有序集合，推荐以下选项：

• pyavl：纯Python编写的AVL树，API设计接近标准库集合，支持类型注解，在纯Python实现中性能处于第一梯队，适合需要平衡树特性的场景。
• rbtree：C扩展实现的红黑树，性能远超纯Python库，支持海量数据的快速插入、删除和查询操作，适合对性能要求极高的场景。
• treelib：虽主打树形结构存储，但可自定义扩展为有序集合，支持类型注解，适合需要灵活定制树结构的场景。

内容的提问来源于stack exchange，提问作者Jarus