1 Preface

最近在一直采用 go 语言进行项目开发，遇到一个比较有意思的问题：

多个集合，计算交集，哪种计算方法最高效？

假定集合采用 HashMap 来实现，那么每次查询的时间复杂度为 O(1)

考虑最简单的情况，假定有2个集合A和B，A 的元素个数为2, B 的元素个数为10。

计算A和B的交集有 2 个方案：
方案一：先遍历A，在B中查找是否存在，时间复杂度为 2*O(1)
方案二：时间复杂度为 10*O(1)

于是得出结论：

每次遍历最小的集合去计算交集，总的时间复杂度最小。

2 寻找已有的轮子

由于 go 标准库，并不提供 set 数据结构；先尝试用 google 搜索，fatih/set 出镜率比较高。 于是简单看了下交集实现：先求 2 遍并集(Union)，真是简单粗暴，果断弃之。(PS 目前这个库已Archive，也不再维护了)

继续尝试在 github 上搜索 go-set，忽然眼前一亮，发现 scylladb 实现了一个(scylladb出品，必属精品)； 确认过眼神，正是我想要的。

search-go-set

3 源码实现 (go语言)

下面是 scylladb 的 go-set 实现, 和前面总结的思路一致。

 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

// Intersection returns a new set which contains items that only exist in all
// given sets.
func Intersection(sets ...*Set) *Set {
    minPos := -1
    minSize := math.MaxInt64
    for i, set := range sets {
        if l := set.Size(); l < minSize {
            minSize = l
            minPos = i
        }
    }
    // 如果传入的 sets 集合为空，或者存在一个大小为 0 的集合
    // 那么交集就是: 空集合
    if minSize == math.MaxInt64 || minSize == 0 {
        return New()
    }
    // 依次遍历所有集合
    t := sets[minPos].Copy()
    for i, set := range sets {
        if i == minPos {
            continue
        }
        // 每次遍历最小的集合，去检查
        for item := range t.m {
            if _, has := set.m[item]; !has {
                delete(t.m, item)
            }
        }
    }
    return t
}

4 总结

开源的时代，虽然开箱即用，也需要根据实际需求，加以斟酌，寻找真正适合的轮子哈。

5 更上一层楼

Q: 如果是求多个集合的并集(Union)呢？
A: 同样的思路，我们还是要遍历元素较小的集合；
也就是说：我们就把元素最多的那个集合单独拿出来，每次只往里面添加元素即可。

References