Go中获取两个切片交集的六种实现方式

目录

• 基础方法回顾
• 1. 双重循环法（O(n²)，简单但低效）
• 2. Map 查表法（O(n+m)，推荐通用解）
• 3. 排序双指针法（O(n log n)，内存友好）
• 高级方法
• 4. 【泛型通用版】交集函数（Go 1.18+）
• 5. 【结构体交集】自定义等价判断
• 6. 【多集交集】保留重复次数的交集
• 性能对比（ 10k 元素 string slice）
• 实战建议

func intersectLoop[T comparable](a, b []T) []T {
	var res []T
	for _, x := range a {
		for _, y := range b {
			if x == y {
				res = append(res, x)
				break // 防止重复添加同一元素（若 a 有重复）
			}
		}
	}
	return res
}

✅ 优点：无额外内存，逻辑直观
❌ 缺点：n=10⁴ 时性能急剧下降

func intersectMap[T comparable](a, b []T) []T {
	set := make(map[T]struct{}, len(a))
	for _, v := range a {
		set[v] = struct{}{}
	}

	var res []T
	for _, v := range b {
		if _, ok := set[v]; ok {
			res = append(res, v)
			delete(set, v) // ← 关键：防止 b 中重复导致结果重复
		}
	}
	return res
}

注意：

• 默认保留 b 中元素顺序
• 用 delete 可实现结果去重（若只需首次匹配）
• 若需保留所有重复（多集交集），则不要 delete

import "sort"

func intersectSorted[T comparable](a, b []T) []T {
	// 创建副本避免修改原 slice
	aa, bb := make([]T, len(a)), make([]T, len(b))
	copy(aa, a)
	copy(bb, b)

	sort.Slice(aa, func(i, j int) bool { return aa[i] < aa[j] })
	sort.Slice(bb, func(i, j int) bool { return bb[i] < bb[j] })

	var res []T
	i, j := 0, 0
	for i < len(aa) && j < len(bb) {
		switch {
		case aa[i] == bb[j]:
			res = append(res, aa[i])
			i++
			j++
		case aa[i] < bb[j]:
			i++
		default:
			j++
		}
	}
	return res
}

✅ 适合大内存受限场景（如嵌入式）
❌ 破坏原顺序，且 T 必须可排序

结合 map 法 + 泛型，写出生产级工具函数：

// Intersection returns the intersection of two slices.
// Result preserves the order of elements in `a`, and removes duplicates.
// T must be comparable.
func Intersection[T comparable](a, b []T) []T {
	if len(a) == 0 || len(b) == 0 {
		return nil
	}

	// Step 1: Build lookup set from b (smaller one for memory efficiency)
	if len(b) < len(a) {
		a, b = b, a // ensure `a` is the smaller slice
	}
	set := make(map[T]struct{}, len(a))
	for _, v := range a {
		set[v] = struct{}{}
	}

	// Step 2: Iterate b, collect matches while preserving order & dedup
	seen := make(map[T]struct{}) // track emitted items
	var res []T
	for _, v := range b {
		if _, inA := set[v]; inA {
			if _, emitted := seen[v]; !emitted {
				res = append(res, v)
				seen[v] = struct{}{}
			}
		}
	}
	return res
}

✅ 优势：

• 自动选小切片建 map → 节省内存
• 保留 b 的出现顺序
• 天然去重（结果每个元素唯一）
• 泛型支持 int, string, struct{}（只要 comparable）

当元素是结构体，且仅部分字段需参与比较时（如 User{ID, Name} 只按 ID 比较）：

type User struct {
	ID   int
	Name string
}

// Key returns a comparable key for equality comparison
func (u User) Key() int { return u.ID }

// IntersectionBy extracts intersection using a key function
func IntersectionBy[T any, K comparable](a, b []T, key func(T) K) []T {
	keySet := make(map[K]struct{})
	for _, v := range a {
		keySet[key(v)] = struct{}{}
	}

	var res []T
	seen := make(map[K]struct{})
	for _, v := range b {
		k := key(v)
		if _, ok := keySet[k]; ok {
			if _, dup := seen[k]; !dup {
				res = append(res, v)
				seen[k] = struct{}{}
			}
		}
	}
	return res
}

// Usage
usersA := []User{{1, "Alice"}, {2, "Bob"}, {3, "Carol"}}
usersB := []User{{2, "Bob2"}, {4, "David"}, {1, "Alice2"}}

common := IntersectionBy(usersA, usersB, User.Key)
// → [{1 "Alice"}, {2 "Bob"}] （按 ID 匹配，保留 usersB 中的完整结构）

适用场景：

• 数据库记录对比（按 ID）
• API 响应去重（按唯一键）
• 忽略时间戳/版本字段的结构体同步

若需数学意义上的多重集交集（如 A=[1,1,2], B=[1,2,2] → 交集为 [1,2]，各取 min(count)）：

func IntersectionMultiset[T comparable](a, b []T) []T {
	// Count frequency in a
	freqA := make(map[T]int)
	for _, v := range a {
		freqA[v]++
	}

	// For each in b, take min(count)
	var res []T
	for _, v := range b {
		if cnt, ok := freqA[v]; ok && cnt > 0 {
			res = append(res, v)
			freqA[v]-- // consume one occurrence
		}
	}
	return res
}

// Example:
a := []int{1, 1, 2, 3}
b := []int{1, 2, 2, 4}
fmt.Println(IntersectionMultiset(a, b)) // → [1, 2]

goos: linux
goarch: amd64
pkg: example
cpu: Intel(R) Core(TM) i7-10700K
BenchmarkIntersectLoop-16      	     3	 452,123,840 ns/op
BenchmarkIntersectMap-16       	  1000	   1,021,344 ns/op
BenchmarkIntersectSorted-16    	  1000	   1,241,892 ns/op
BenchmarkIntersectionGeneric-16	  1000	   1,045,217 ns/op

结论：

• Map 法/泛型通用版 最快（~1ms）
• 循环法慢 400+ 倍，仅适用于 n < 100
• 排序法略慢于 map，但内存稳定（无 hash 表开销）

实际建议：优先用 Intersection[T comparable] 泛型函数，兼顾性能、可读性、去重、顺序。

场景	推荐方案
快速原型 / 小数据（<100）	双重循环 + break
通用场景（string/int）	泛型 Intersection[T]
结构体按字段比较	IntersectionBy + key 函数
需保留重复次数（多集）	IntersectionMultiset
内存极其受限	排序双指针法
需要稳定顺序 + 去重	泛型版（内置顺序+去重）

以上就是Go中获取两个切片交集的六种实现方式的详细内容，更多关于Go获取两个切片交集的资料请关注风君子博客其它相关文章！

您可能感兴趣的文章:

• Golang语言中切片的长度和容量的概念和使用
• Golang 二维切片代码示例
• Go语言中切片展开操作符的实现示例
• go语言之数组和切片使用及说明
• 深入理解Go语言中二维切片的使用