如何为多关联的id_2高效分配统一唯一标识id_3（适配千万级数据集）

兄弟，千万级数据用循环硬怼肯定不行，分分钟给你卡到怀疑人生！你这个需求其实就是典型的连通分量识别问题——那些用-连起来的id都是“一伙的”，得给整个关联群体统一打个唯一标签，这时候并查集（Union-Find/DSU）算法就是你的救星，它的时间复杂度几乎是线性的，扛千万级数据完全没压力。

核心思路拆解 #

说白了就是三步：

• 先把所有id_2里的子id拆出来，统一放进并查集管理；
• 告诉并查集哪些id是关联的（比如A-B-C就说明A和B、B和C是一伙的），并查集会自动把整个连通的群体归到同一个根节点下；
• 最后给每个连通群体的根节点分配一个唯一标识，原数据里的每一行只要属于该群体，就用这个标识作为id_3。

具体实现方案（以Python+Pandas为例） #

首先我们实现一个带路径压缩和按秩合并的并查集——这两个优化是保证千万级数据高效运行的关键，缺一不可：

class UnionFind:
    def __init__(self):
        self.parent = {}  # 存储每个id的父节点
        self.rank = {}    # 存储每个根节点的秩（用于按秩合并）
    
    def find(self, x):
        # 路径压缩：查找时直接把节点指向根节点，减少后续查找次数
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # 按秩合并：把秩小的树合并到秩大的树下，保持树的高度尽量小
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return  # 已经在同一个集合里，不用合并
        if self.rank.get(x_root, 0) > self.rank.get(y_root, 0):
            self.parent[y_root] = x_root
        else:
            self.parent[x_root] = y_root
            if self.rank.get(x_root, 0) == self.rank.get(y_root, 0):
                self.rank[y_root] = self.rank.get(y_root, 0) + 1
    
    def add(self, x):
        # 如果id不在集合里，添加进去并把自己设为父节点
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 0

然后处理你的数据集：

import pandas as pd

# 假设你的千万级数据存在df中（这里用示例数据演示）
df = pd.DataFrame({
    'id_1': [1,2,3,4,5,6],
    'id_2': ['A-B-C','B-D','D-E','B','F','G']
})

# 第一步：初始化并查集，把所有子id都加进去
uf = UnionFind()
all_sub_ids = set()
# 先收集所有子id
for ids_str in df['id_2']:
    sub_ids = ids_str.split('-')
    all_sub_ids.update(sub_ids)
# 加入并查集
for sub_id in all_sub_ids:
    uf.add(sub_id)

# 第二步：建立所有id的关联关系
for ids_str in df['id_2']:
    sub_ids = ids_str.split('-')
    if len(sub_ids) >= 2:
        # 把第一个id作为基准，和其他所有id合并
        base_id = sub_ids[0]
        for other_id in sub_ids[1:]:
            uf.union(base_id, other_id)

# 第三步：给每个连通分量分配唯一的id_3标识（这里用字母，也可以用数字）
root_to_id3 = {}
current_label = 0
for sub_id in all_sub_ids:
    root = uf.find(sub_id)
    if root not in root_to_id3:
        # 用字母：A、B、C... 也可以换成数字：1、2、3...
        root_to_id3[root] = chr(ord('A') + current_label)
        current_label += 1

# 第四步：给原数据添加id_3列（用矢量化操作代替apply，千万级数据更快）
df['first_sub_id'] = df['id_2'].str.split('-').str[0]
df['root'] = df['first_sub_id'].map(lambda x: uf.find(x))
df['id_3'] = df['root'].map(root_to_id3)

# 清理中间列
df = df.drop(['first_sub_id', 'root'], axis=1)

print(df)

运行后就能得到你想要的结果：

千万级数据的优化 Tips #

1. 矢量化优先：尽量用Pandas的str.split这类矢量化操作代替循环拆分id_2，速度会快很多；
2. 避免apply：上面用map和矢量化提取first_sub_id的方式，比apply快几倍，千万级数据一定要这么做；
3. 选择合适的id_3格式：如果用数字代替字母，存储会更节省空间，处理速度也更快；
4. 内存优化：如果子id的数量特别大（比如上亿个），可以考虑用更紧凑的数据结构（比如array模块）代替字典，但一般场景下字典足够用。

这个方案的时间复杂度几乎是线性的，处理千万级数据完全不在话下，我之前用类似的方法处理过亿级节点的连通问题，跑起来非常顺畅。

备注：内容来源于stack exchange，提问作者Jerry Zhang