R语言数据框复杂匹配批量生成分组ID的高效实现问题

需求本质 #

你要实现的是连通组分匹配：每一行的a、b两个值构成关联边，所有存在关联关系的边（行）归入同一分组，这是典型的图连通分量计算场景，用优化过的图算法效率远高于逐行匹配。

实现代码 #

依赖包安装（仅需一次） #

install.packages("igraph")

核心代码 #

library(igraph)
library(dplyr)

# 示例数据
df <- data.frame(a = c('x', 'y', 'z', 't', 'm', 'n'), 
                 b = c('x', 'x', 'y', NA, 'm', 'm')) 

# 1. 提取有效边（过滤b为NA的行）
valid_edges <- df %>% filter(!is.na(b)) %>% select(a, b)
# 2. 构建无向图并计算连通分量
g <- graph_from_data_frame(valid_edges, directed = FALSE)
comp <- components(g)
# 3. 给有效边对应行分配组号
valid_edges$group <- comp$membership[as.character(valid_edges$a)]
# 4. 合并回原数据框
df <- df %>% 
  left_join(valid_edges, by = c("a", "b")) %>% 
  # 可加一步按组号重排序让组号连续（可选）
  mutate(group = as.integer(factor(group, levels = unique(sort(group)))))

输出结果 #

> df
  a    b group
1 x    x     1
2 y    x     1
3 z    y     1
4 t <NA>    NA
5 m    m     2
6 n    m     2

效率说明 #

igraph的连通分量算法为底层C实现，时间复杂度接近线性，处理千万级行数据也不会出现性能瓶颈，完全可以满足大数据量场景需求，避免逐行匹配的O(n²)级时间消耗。

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