You need to enable JavaScript to run this app. Python中高效查找指定t1/t2值的自定义哈希Obj集合元素的方法
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.30 05:06:04