使用Go求两个切片的差集

前言

刚刚参见工作，逐渐的适用了工作节奏。笔者受公司大佬们的影响，也决定开始写博客（老板博客）。但是，限于本人目前能力原因，无法写出更有深度的博客，再接再厉。

场景

目前，本人从事基础平台研发工作，在做一款tools的时候，需要对CMDB和Prometheus两个平台数据比对。Meanwhile, 触发了两个for循环的条件反射，不到一分钟写出了经典for循环，结果计算了下时间复杂度M x N，将近1亿次的计算，空间复杂度倒是可以使用Builder来进行优化。因为是一款运维工具，所以重点是代码的健壮性，对于时间，空间复杂度考虑会相对少些，但是笔者是一个“急躁”的人，这种“慢”简直无法忍受。In one word, 如何优化时间复杂度问题。

问题

当运行该工具的时候，效果是一直停顿在这个数据比对的过程中，这怎么可以忍受？上网搜资料，抹油啊，怎么办？别慌，相信自己！

思考

1. 两个数据集合是切片，其中instance是struct类型。这是一种检索的问题，hashmap？树？
2. 使用树，小题大做了吧，使用hash表吧
3. Go中map是这种数据结构
4. 记得刷过一道题：217. 存在重复元素 虽然这个题很简单，但是这种思路较巧妙
5. 要是尝试不来，我就罗盘生成文件，使用牛牛的shell sort -> 求差集 A B -> sort A B B | uniq -u

Coding

func SubtrDemo(a []string, b []string) []string{

var c []string
temp := map[string]struct{}{}  // map[string]struct{}{}创建了一个key类型为String值类型为空struct的map，Equal -> make(map[string]struct{})

for _, val := range b{
	if _, ok := temp[val]; !ok{
		temp[val] = struct{}{}  // 空struct 不占内存空间
	}
}

for _, val := range a{
	if _, ok := temp[val]; !ok{
		c = append(c, val)
	}
}

return c
}

• 原理很简单，慢慢体会吧。
• 不仅优化了时间，在空间上使用struct{}{}进行了优化。

Testing

package subtraction

import "testing"

//
// 求 A B 差集 -> A - B
//
func TestSubtraciton(t *testing.T){

//Data. Predict: ["4"]
a := []string{"1","2","3","4"}
b := []string{"0","1","2","3"}

res := SubtrDemo(a, b)
t.Log(res)

}

Result

总结

虽然这是一个小的trick，但是体现了算法的美妙，以及遇到事情，要开动脑筋，将理论为我所用！ 在线上环境测试，快的一笔。。。 （要是有更好的优化方案，欢迎留言！）