Python中高效查找指定t1/t2值的自定义哈希Obj集合元素的方法
无向Obj集合的端点匹配优化方案
现有方案的问题
- 双SortedKeyList的实现依赖两次独立的有序结构构建,整体索引搭建复杂度为2*O(n log n),在数据量较大时构建开销偏高。
- 没有利用Obj本身“t1/t2交换等价”的无向特性,做了冗余的结构设计。
核心优化思路
我们的查询目标本质是找出所有端点值包含目标key的无向边对象,和无向图的邻接表索引逻辑完全匹配,不需要依赖有序排序结构。
具体实现
1. 修正原Obj类的笔误
原类的__eq__方法中存在笔误,other.r1实际应为other.t1,修正后的完整类定义:
class Obj: t1: int t2: int def __hash__(self): # 基于frozenset计算哈希值,保证交换两个端点ID的对象哈希值一致 return hash(frozenset((self.t1, self.t2))) def __eq__(self, other: 'Obj'): pairs = (self.t1, self.t2) return other.t1 in pairs and other.t2 in pairs
2. 单次遍历构建哈希索引
仅需遍历一次原集合,把每个Obj对象关联到它对应的两个端点下,整体构建复杂度为O(n):
from collections import defaultdict # 端点到关联Obj的映射索引 endpoint_index = defaultdict(list) s = {Obj(1, 2), Obj(1, 3), Obj(4, 1), Obj(9, 5)} for obj in s: # 先将对象关联到t1对应的索引项 endpoint_index[obj.t1].append(obj) # 若t1和t2值不同,再关联到t2对应的索引项,避免自环对象重复挂载 if obj.t1 != obj.t2: endpoint_index[obj.t2].append(obj)
3. 快速查询
需要查询所有带目标key的对象时,直接从索引中读取对应列表即可,均摊查询复杂度为O(k),k为匹配到的结果数量:
key = 1 output = endpoint_index.get(key, []) # 最终结果为 [Obj(1,2), Obj(1,3), Obj(4,1)],和预期一致
方案优势对比
- 不需要依赖
sortedcontainers这类第三方库,纯标准库即可实现 - 索引构建开销远低于双排序方案,从2*O(n log n)降低到单次O(n)遍历
- 查询没有二分查找的对数级开销,命中速度更快
- 天然适配Obj的无向等价规则,不需要单独拆分t1、t2的逻辑
- 避免了原有双排序方案拼接结果时的自环对象重复统计问题,不需要额外做结果去重
- 动态增删对象时的维护成本极低:新增对象仅需在对应端点的索引列表追加,删除时直接从列表移除,无需像有序列表那样做大规模元素移位操作
注意:如果集合是动态变化的高频增删场景,索引列表可以替换为集合类型,保证索引内的对象不重复,维护时的去重逻辑更简单。
内容的提问来源于stack exchange,提问作者DUWUDA
相关产品推荐
相关产品推荐

