Union-Find Set 的应用

发表于   |   分类于   |  

有这么一个问题，有一个10万条记录的文件，每条记录有两列，分别是用户一次访问在两个服务器上留下的两条cookie记录，可以记作cookie A 和 cookie B。同一个用户的多次访问记录，cookie可能相同，也可能不同（cookie有时效性）。任意两条数据i,j ，如果cookie A相同或者cookie B相同，则认为i, j 是同一个用户留下的记录。同一个用户留下的访问记录可以合并，输出每个用户的所有cookie。例如有文件记录如下(用小写字母表示cookie)：

a, b
a, d
c, e
f, d
c, g

则输出为:

{a, f}, {b, d}
{c}, {e, g}

在面试的时候被问到这个问题，当时没有什么思路。回到宿舍，问了宿舍的冰神，冰神告诉我应该用并查集。我才恍然大悟，对于不相交集合的数据就应该用并查集，就是算法导论中的 disjoint-set data structure.

并查集

对并查集介绍摘自CYJB博客。

并查集(Union-find Set)是冰神心中完美的数据结构——简单却有非常大的威力。它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、最小生成树Kruskal算法、求最近公共祖先(Least Common Ancestors, LCA)等。

每个集合有一个代表元素，对于给定的元素，可以很快的找到这个元素所在集合的代表元素。
并查集有三个基本操作：

1.makeSet(s): 建立一个新的并查集.

2.unionSet(x, y): 把元素x和元素y所在的集合合并。

3.find(x): 找到元素x所在集合的代表，该操作也可以用于判断两个元素是否在同一个集合。

该问题的解法

1.如果有n条记录，给每条记录一个编号0~n-1.

2.分别按照cookie A 和 cookie B排序，分别遍历两个排序后的结果，如果一条记录和它前一个记录cookie相同，合并之。

3.并查集就像一个森林，建立一个字典，key是森林中每个树的根编号（即是每个用户），value是该用户对应的所有cookie。扫描一次整个文件就可以完成Step 3.

相当于对数据做两次排序，三次线性扫描，时间复杂度是O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
def init_set(n):
    """
        初始化并查集, 每个元素一类，代表元素是其自身
    """
    father = [i for i in range(n)]
    return father

def find_set(father, x):
    """
        找出元素x的代表元素，并作路径压缩
    """
    if father[x] != x:
        father[x] = find_set(father, father[x])
    return father[x]

def union_set(father, x, y):
    """
        x的代表元素挂到y代表元素上
    """
    father[find_set(father, x)] = father[find_set(father, y)]

def find_user_cookie(cookie):
    """
        cookie是一个list, 其中每个元素是一个3维tuple，代表:编号, cookie A, cookie B 
        返回一个字典，key代表一个用户, value是该用户的所有cookie
    """
    # n条记录
    n = len(cookie)
    father = init_set(n)

    # sort cookie by cookie A
    sort_A = sorted(cookie, key = lambda c:c[1])

    # 上一个record
    pre = (-1, None, None)
    for record in sort_A:
        # 如果cookie A相同，合并
        if record[1] == pre[1]:
            union_set(father, record[0], pre[0])
        pre = record

    # sort cookie by cookie B
    sort_B = sorted(cookie, key = lambda c:c[2])

    pre = (-1, None, None)
    for record in sort_B:
        # 如果cookie B相同，合并
        if record[2] == pre[2]:
            union_set(father, record[0], pre[0])
        pre = record

    user_cookie = dict()
    for record in cookie:
        # 代表元素
        rep = find_set(father, record[0])
        # 如果rep不是字典的key
        if rep not in user_cookie:
            user_cookie[rep] = (set(), set())

        user_cookie[rep][0].add(record[1])
        user_cookie[rep][1].add(record[2])

    return user_cookie

如果输入cookie就是上文举的例子:

1
2
3
4
5
6
7
8
9
if __name__ == '__main__':
    cookie = [
        (0, 'a', 'b'),
        (1, 'a', 'd'),
        (2, 'c', 'e'),
        (3, 'f', 'd'),
        (4, 'c', 'g'),
    ]
    print find_user_cookie(cookie)

则运行结果为:

1
{0: (set(['a', 'f']), set(['b', 'd'])), 2: (set(['c']), set(['e', 'g']))}