
本文介绍一种借助并查集(disjoint set)解决“多列等价关系聚合”问题的方法:当记录通过 key1 或 key2 存在间接关联时,将其归入同一组并统计总数。
本文介绍一种借助并查集(disjoint set)解决“多列等价关系聚合”问题的方法:当记录通过 key1 或 key2 存在间接关联时,将其归入同一组并统计总数。
在 Polars 中,常规的 group_by(['key1', 'key2']) 仅支持显式组合匹配,无法自动识别跨列的传递性等价关系(例如:(a, x) 和 (a, y) 关联 a,(b, y) 又关联 y → 则 a、b、x、y 应属同一连通分量)。这类需求本质上是图论中的连通分量(Connected Components) 问题,需将 key1 和 key2 视为同一顶点集下的两类标签,并建立无向边连接每对 (key1, key2)。
Polars 原生不提供连通分量算法,但可通过轻量级外部库(如 scipy.cluster.hierarchy.DisjointSet)协同完成。以下是完整、可运行的解决方案:
✅ 步骤详解与代码实现
import polars as pl
from scipy.cluster.hierarchy import DisjointSet
# 构造示例数据
df = pl.DataFrame({
'id': [1, 2, 3, 4],
'key1': ['a', 'a', 'b', 'c'],
'key2': ['x', 'y', 'y', 'z'],
})
# Step 1: 提取所有唯一键(合并 key1 和 key2)
all_keys = df.select(
pl.col("key1").append(pl.col("key2")).unique().alias("key")
).to_series().to_list()
# Step 2: 获取唯一的关系对(去重后的边)
edges = df.select(["key1", "key2"]).unique().iter_rows()
# Step 3: 初始化并查集,逐条合并关联键
ds = DisjointSet(all_keys)
for key1, key2 in edges:
ds.merge(key1, key2)
# Step 4: 将每个连通分量映射为 (key → group_idx) 的长表
subsets = [list(s) for s in ds.subsets()]
group_map = (
pl.DataFrame({"key": subsets})
.with_row_index("group_idx")
.explode("key")
)
# Step 5: 将原始数据按 key1 关联分组索引,并聚合计数
result = (
df.lazy()
.join(group_map.lazy(), left_on="key1", right_on="key", how="left")
.group_by("group_idx")
.len()
.collect()
)
print(result)输出结果:
shape: (2, 2) ┌───────────┬─────┐ │ group_idx ┆ len │ │ --- ┆ --- │ │ u32 ┆ u32 │ ╞═══════════╪═════╡ │ 0 ┆ 1 │ │ 1 ┆ 3 │ └───────────┴─────┘
✅ 对应关系说明:
-
group_idx=1包含key1='a'(对应 id=1,2)和key1='b'(id=3),因'a'–'y'–'b'形成传递链; -
group_idx=0仅含'c'(id=4),无任何key2与其他行交集。
⚠️ 注意事项与最佳实践
-
键类型一致性:确保
key1和key2数据类型兼容(如均为字符串或数值),避免隐式转换导致合并失败; -
性能考量:对于超大规模数据(百万级边),
DisjointSet仍高效,但pl.DataFrame.iter_rows()在 Polars 中非最优;可改用to_numpy()批量处理提升速度; -
缺失值处理:若存在
null,需提前drop_nulls()或填充,否则DisjointSet会报错; -
替代方案:若无法引入
scipy,可用纯 Python 实现并查集(带路径压缩+按秩合并),时间复杂度仍为近似线性; -
结果解读:
group_idx是逻辑分组 ID,无业务含义;如需保留代表性键(如首个 key1),可在group_map中额外聚合pl.col("key").first().over("group_idx")。
该方法将图结构建模能力无缝融入 Polars 流水线,兼顾表达力与执行效率,是处理实体对齐、标签传播、会话合并等场景的可靠范式。

















