在R中为大型DataFrame的关联行高效分配通用ID

针对1900万行、81列的大型FST数据集，需要按以下规则为每个name组内的记录分配唯一序列ID：

• 未取消（cancelled为NA）的记录，若前一条的end与后一条的start匹配，则归为同一序列
• 已取消的记录单独作为独立序列，不与后续记录关联
• 采用"先到先得"原则，未分配ID的记录生成新ID并匹配所有符合条件的后续记录

核心思路 #

利用连通分量分析处理未取消记录的关联关系，结合data.table的高效分组操作适配大规模数据，避免循环带来的性能损耗。已取消记录直接标记为独立序列，无需参与关联计算。

实现代码 #

# 加载高效处理工具包
library(data.table)
library(fst)
library(igraph)

# 读取FST格式数据（比CSV/RDS快数倍，内存占用低）
dt <- read_fst("your_data_path.fst", as.data.table = TRUE)

# 预处理：标记取消状态，生成全局临时ID
dt[, `:=`(
  is_cancelled = !is.na(cancelled),
  temp_id = .I  # 全局唯一临时ID，用于后续图节点匹配
), by = name]

# 分组处理函数：为每个name组生成序列ID
assign_seq_id <- function(group_data) {
  # 拆分已取消和未取消记录
  cancelled_records <- group_data[is_cancelled]
  valid_records <- group_data[!is_cancelled]
  
  # 全为取消记录的情况
  if (nrow(valid_records) == 0) {
    group_data[, new_unique_id := temp_id]
    return(group_data)
  }
  
  # 构建衔接边：找到end与start匹配的记录对
  valid_records[, to := temp_id[match(start, end)]]
  edges <- valid_records[!is.na(to), .(from = temp_id, to = to)]
  
  # 构建图并提取连通分量
  graph <- graph_from_data_frame(edges, directed = FALSE, vertices = valid_records$temp_id)
  comps <- components(graph)
  
  # 为未取消记录分配分量ID
  valid_records[, component_id := comps$membership[as.character(temp_id)]]
  
  # 合并两类记录，统一组内ID
  combined <- rbind(
    valid_records[, new_unique_id := component_id],
    cancelled_records[, new_unique_id := temp_id]
  )
  
  # 组内ID连续化
  combined[, new_unique_id := frank(new_unique_id, ties.method = "dense")]
  return(combined)
}

# 按name分组执行，保留所有原始列
result <- dt[, assign_seq_id(.SD), by = name]

# 生成全局唯一的序列ID（跨name组）
result[, new_unique_id := rleid(new_unique_id)]

# 可选：按示例要求排序（若不需要原顺序可省略）
result <- result[order(new_unique_id, start)]

# 保存结果为FST格式
write_fst(result, "result_data.fst")

性能优化说明 #

1. data.table分组：相比dplyr，data.table采用引用修改和高效分组算法，处理千万级数据时内存占用减少30%以上，速度提升2-5倍。
2. 分组合连通分量：按name拆分处理，每个组单独构建图结构，避免一次性加载全量数据到内存，适合单组数据量较大的场景。
3. FST格式读写：专为大数据设计的存储格式，支持随机访问，读写速度远优于传统格式，同时压缩率高达70%。
4. 边构建优化：用match代替全量查找，减少不必要的边生成，进一步提升图构建效率。

特殊场景处理 #

• 若单name组内记录超过百万级，可将该组进一步拆分为时间块处理，或者采用dplyr的group_split分批处理。
• 若不需要全局连续ID，可省略最后一步的rleid，直接使用组内ID即可。

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