张子阳的博客

首页 读书 技术 店铺 关于
张子阳的博客 首页 读书 技术 店铺 关于

技巧:快速求并集交集和差集

2019-1-30 作者: 张子阳 分类: 数据结构和算法

在做一个文件同步工具的时候,有这样一个需求:假设有source和target两个文件夹,确保两个文件夹中的文件一致。即当source中添加了新文件时,自动拷贝到target; 当source文件夹删除某个文件时,target中的文件也要删除。(实际上文件改动也要进行同步,但和这个例子没有关系)。这样就需要求两个集合的差集,这篇文章演示如何快速实现这一过程。

下面这幅图可以说明要执行的操作:

要执行的运算

直观上,最容易想到的方法就是嵌套两个for循环来遍历这两个集合,但这样的时间复杂度是O(n^2)。一个更好的办法,是借助Hash表的快速访问能力来将嵌套的for循环改为单个的for循环。

下面是go语言的实现:

package main

import (
    "fmt"
    "strings"
)

func main() {
    source := []string{"apple", "banana", "pear", "watermelon", "strawberry"}
    target := []string{"pear", "watermelon", "strawberry", "orange", "litchi"}

    set := getSetDiff(source, target)
    all := []string{}  // 并集
    add := []string{}  // source和target的差集
    del := []string{}  // target和source的差集
    both := []string{} // 交集

    for k, v := range set {
        if v == 1 {
            add = append(add, k)
        }
        if v == 0 {
            both = append(both, k)
        }
        if v == -1 {
            del = append(del, k)
        }
        all = append(all, k)
    }

    fmt.Printf("并集: %v\n", strings.Join(all[:], ","))
    fmt.Printf("交集: %v\n", strings.Join(both[:], ","))
    fmt.Printf("source和target的差集: %v\n", strings.Join(add[:], ","))
    fmt.Printf("target和source的差集: %v\n", strings.Join(del[:], ","))
}

func getSetDiff(source, target []string) map[string]int {
    var m = make(map[string]int)

    for _, item := range source {
        m[item] = 1 // 差集 source-target
    }

    for _, item := range target {
        if _, ok := m[item]; ok {
            m[item] = 0 // source 和 target中都有的
        } else {
            m[item] = -1 // 差集 target-source
        }
    }

    return m
}

输出的结果如下:

并集: apple,banana,pear,watermelon,strawberry,orange,litchi
交集: pear,watermelon,strawberry
source和target的差集: apple,banana
target和source的差集: orange,litchi

在需要反复进行集合遍历的操作时,都可以考虑下是否有使用hash表的替代方案,使用hash表的速度往往要快很多,它存取数据的时间复杂度是:O(1),而使用for循环对列表进行线性查找的时间复杂度是O(n)。

感谢阅读,希望这篇文章能给你带来帮助!