使用Go求两个切片的差集
前言
刚刚参见工作，逐渐的适用了工作节奏。笔者受公司大佬们的影响，也决定开始写博客（老板博客）。但是，限于本人目前能力原因，无法写出更有深度的博客，再接再厉。
场景
目前，本人从事基础平台研发工作，在做一款tools的时候，需要对CMDB和Prometheus两个平台数据比对。Meanwhile, 触发了两个for循环的条件反射，不到一分钟写出了经典for循环，结果计算了下时间复杂度M x N，将近1亿次的计算，空间复杂度倒是可以使用Builder来进行优化。因为是一款运维工具，所以重点是代码的健壮性，对于时间，空间复杂度考虑会相对少些，但是笔者是一个“急躁”的人，这种“慢”简直无法忍受。In one word, 如何优化时间复杂度问题。
问题
当运行该工具的时候，效果是一直停顿在这个数据比对的过程中，这怎么可以忍受？上网搜资料，抹油啊，怎么办？别慌，相信自己！
思考
- 两个数据集合是切片，其中instance是struct类型。这是一种检索的问题，hashmap？树？
- 使用树，小题大做了吧，使用hash表吧
- Go中map是这种数据结构
- 记得刷过一道题：217. 存在重复元素 虽然这个题很简单，但是这种思路较巧妙
- 要是尝试不来，我就罗盘生成文件，使用牛牛的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
=== RUN TestSubtraciton subtraction_test.go:28: [4] --- PASS: TestSubtraciton (0.00s) PASS
总结
虽然这是一个小的trick，但是体现了算法的美妙，以及遇到事情，要开动脑筋，将理论为我所用！ 在线上环境测试，快的一笔。。。 （要是有更好的优化方案，欢迎留言！）
