有没有一种高效的方法在Go中获取两个切片的交集？
我想避免像嵌套for循环那样的解决方案。
slice1 := []string{"foo", "bar","hello"}
slice2 := []string{"foo", "bar"}
intersection(slice1, slice2)
=> ["foo", "bar"]
如何在golang中获取两个切片的交集？
33
- bandi shankar
1
2看起来您正在寻找这个集合库：https://github.com/deckarep/golang-set - Akavall
7个回答
40
- 简单交集：将
A中的每个元素与B中的每个元素进行比较（O(n^2)） - 哈希交集：将它们放入哈希表中（
O(n)） - 排序交集：对
A进行排序并进行优化的交集操作（O(n*log(n))）
这些方法都在这里实现了
https://github.com/juliangruber/go-intersect/blob/master/intersect.go
- KeksArmee
7
1在 Go 语言中，我们是否有任何内置库来处理这个问题？ - bandi shankar
1请记住，虽然 $O(n)$ 的解决方案对于大的 $n$ 比 $O(n^2)$ 的解决方案更好，但如果 $n$ 很小，则使用 $O(n^2)$ 的解决方案可能比使用 $O(n)$ 的解决方案更好，因为后者可能会有更多的开销。 - md2perpe
2@md2perpe，你不能根据“可能”有更多开销来做出这样的概括。最好选择最有效的方法，并且最好针对每种情况进行测试，看看哪种方法符合要求。 - Adrian
8@Adrian，请转告Rob Pike（https://en.wikipedia.org/wiki/Rob_Pike）这个信息。您可以在此处查看他的规则3：http://users.ece.utexas.edu/~adnan/pike.html - md2perpe
@bandishankar 只需运行
go get "github.com/juliangruber/go-intersect" 即可。然后您可以使用相同的路径访问其代码。别忘了给这个家伙点赞 :) - KeksArmee显示剩余2条评论
6
简单、通用和多片段（Go 1.18）
时间复杂度：可能是线性的。
时间复杂度：可能是线性的。
func interSection[T constraints.Ordered](pS ...[]T) []T {
hash := make(map[T]*int) // value, counter
result := make([]T, 0)
for _, slice := range pS {
duplicationHash := make(map[T]bool) // duplication checking for individual slice
for _, value := range slice {
if _, isDup := duplicationHash[value]; !isDup { // is not duplicated in slice
if counter := hash[value]; counter != nil { // is found in hash counter map
if *counter++; *counter >= len(pS) { // is found in every slice
result = append(result, value)
}
} else { // not found in hash counter map
i := 1
hash[value] = &i
}
duplicationHash[value] = true
}
}
}
return result
}
func main() {
slice1 := []string{"foo", "bar", "hello"}
slice2 := []string{"foo", "bar"}
fmt.Println(interSection(slice1, slice2))
// [foo bar]
ints1 := []int{1, 2, 3, 9, 8}
ints2 := []int{10, 4, 2, 4, 8, 9} // have duplicated values
ints3 := []int{2, 4, 8, 1}
fmt.Println(interSection(ints1, ints2, ints3))
// [2 8]
}
- Vivian K. Scott
4
这是一种最佳的方法，用于求两个切片的交集。时间复杂度非常低。
时间复杂度 : O(m+n)
m = 第一个切片的长度。
n = 第二个切片的长度。
func intersection(s1, s2 []string) (inter []string) {
hash := make(map[string]bool)
for _, e := range s1 {
hash[e] = true
}
for _, e := range s2 {
// If elements present in the hashmap then append intersection list.
if hash[e] {
inter = append(inter, e)
}
}
//Remove dups from slice.
inter = removeDups(inter)
return
}
//Remove dups from slice.
func removeDups(elements []string)(nodups []string) {
encountered := make(map[string]bool)
for _, element := range elements {
if !encountered[element] {
nodups = append(nodups, element)
encountered[element] = true
}
}
return
}
- Rajasankar S
1
1如果您使用哈希映射的布尔值作为指示器来表示是否已将相同元素添加到结果数组中，则无需使用
removeDups。 - Dan Markhasin2
如果您的[]string中不存在空格，则可以使用以下简单代码：
func filter(src []string) (res []string) {
for _, s := range src {
newStr := strings.Join(res, " ")
if !strings.Contains(newStr, s) {
res = append(res, s)
}
}
return
}
func intersections(section1, section2 []string) (intersection []string) {
str1 := strings.Join(filter(section1), " ")
for _, s := range filter(section2) {
if strings.Contains(str1, s) {
intersection = append(intersection, s)
}
}
return
}
- Nevercare
1
这是一种好奇的方法。我对包含 vs 哈希的基准测试很感兴趣。 - Kevin Ard
1
另外一个使用哈希表的O(m+n)时间复杂度解决方案。 与此处讨论的其他解决方案相比，有两个不同之处。
- 将目标切片作为参数传递而不是返回新的切片
- 对于常用类型（如字符串/整数），比反射更快
- Tejus Krishna
1
试一试
https://go.dev/play/p/eGGcyIlZD6y
first := []string{"one", "two", "three", "four"}
second := []string{"two", "four"}
result := intersection(first, second) // or intersection(second, first)
func intersection(first, second []string) []string {
out := []string{}
bucket := map[string]bool{}
for _, i := range first {
for _, j := range second {
if i == j && !bucket[i] {
out = append(out, i)
bucket[i] = true
}
}
}
return out
}
- Roman
2
逻辑是外层循环从第一个切片获取每个字符串，内层循环将第一个切片中的字符串与第二个切片中的每个字符串进行比较，如果是相同的字符串且哈希映射以该字符串为键不存在，则将该字符串添加到新切片中，将哈希映射以该字符串为键设置为true以避免重复。 - 99Linux
-8
是的，有几种不同的方法可以实现它。这里提供一个可以进行优化的示例。
package main
import "fmt"
func intersection(a []string, b []string) (inter []string) {
// interacting on the smallest list first can potentailly be faster...but not by much, worse case is the same
low, high := a, b
if len(a) > len(b) {
low = b
high = a
}
done := false
for i, l := range low {
for j, h := range high {
// get future index values
f1 := i + 1
f2 := j + 1
if l == h {
inter = append(inter, h)
if f1 < len(low) && f2 < len(high) {
// if the future values aren't the same then that's the end of the intersection
if low[f1] != high[f2] {
done = true
}
}
// we don't want to interate on the entire list everytime, so remove the parts we already looped on will make it faster each pass
high = high[:j+copy(high[j:], high[j+1:])]
break
}
}
// nothing in the future so we are done
if done {
break
}
}
return
}
func main() {
slice1 := []string{"foo", "bar", "hello", "bar"}
slice2 := []string{"foo", "bar"}
fmt.Printf("%+v\n", intersection(slice1, slice2))
}
现在上面定义的交集方法只能操作字符串的切片，就像你的例子一样。理论上，你可以创建一个看起来像这样的定义func intersection(a []interface{}, b []interface{}) (inter []interface{})，但是你将依赖反射和类型转换来进行比较，这将增加延迟并使您的代码更难阅读。为您关心的每种类型编写单独的函数可能更容易维护和阅读。
func intersectionString(a []string, b []string) (inter []string),
func intersectionInt(a []int, b []int) (inter []int),
func intersectionFloat64(a []float64, b []float64) (inter []float64)等等。
然后，您可以创建自己的包，并在解决如何实现它后重复使用它。
package intersection
func String(a []string, b []string) (inter []string)
func Int(a []int, b []int) (inter []int)
func Float64(a []Float64, b []Float64) (inter []Float64)
- reticentroot
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接