如何更快地获取两个列表的交集?

huangapple go评论85阅读模式
英文:

how to get intersection between 2 lists faster

问题

我有两个列表,一个列表的元素类型是structA,另一个列表的元素类型是structB,structA和structB之间有一个共同的字段string name。如何在两个列表之间获取具有相同name的交集元素,并且避免使用Golang的O(n^2)时间复杂度。

请注意:每个列表中的name字段不是唯一的,因此转换为映射方式不是一个解决方案。

英文:

I have 2 lists, one list element type is structA, the other list element type is structB, there's common field string name between structA and structB. how to get intersection element which has same name between 2 lists and avoid o(n^2) time complexity using golang.

type structA struct {
   name string
   ....
}
type structB struct {
   name string
   ..
}

noted: name field in each list is not unique, so convert map way is not a solution

答案1

得分: 0

具有非唯一列表并不妨碍您使用映射;您可以像下面这样做(playground):

package main

import (
	"fmt"
)

func main() {
	type structA struct {
		name       string
		otherfield int
	}
	type structB struct {
		name           string
		differentField bool
	}

	aSlice := []structA{
		{name: "foo", otherfield: 1},
		{name: "foo", otherfield: 2},
		{name: "unique", otherfield: 3},
		{name: "one", otherfield: 4},
	}
	bSlice := []structB{
		{name: "foo", differentField: true},
		{name: "foo", differentField: false},
		{name: "noIntersection", differentField: true},
		{name: "one", differentField: false},
	}

	inA := make(map[string][]interface{})
	for _, a := range aSlice {
		inA[a.name] = append(inA[a.name], a)
	}

	intersect := make(map[string][]interface{})
	for _, b := range bSlice {
		if _, ok := intersect[b.name]; ok {
			intersect[b.name] = append(intersect[b.name], b)
			continue
		}
		if a, ok := inA[b.name]; ok {
			intersect[b.name] = append(a, b)
			continue
		}

	}
	fmt.Println(intersect)
}

英文:

Having lists that are not unique does not prevent you from using a map; you can do something like the following (playground):

package main

import (
	"fmt"
)

func main() {
	type structA struct {
		name       string
		otherfield int
	}
	type structB struct {
		name           string
		differentField bool
	}

	aSlice := []structA{
		{name: "foo", otherfield: 1},
		{name: "foo", otherfield: 2},
		{name: "unique", otherfield: 3},
		{name: "one", otherfield: 4},
	}
	bSlice := []structB{
		{name: "foo", differentField: true},
		{name: "foo", differentField: false},
		{name: "noIntersection", differentField: true},
		{name: "one", differentField: false},
	}

	inA := make(map[string][]interface{})
	for _, a := range aSlice {
		inA[a.name] = append(inA[a.name], a)
	}

	intersect := make(map[string][]interface{})
	for _, b := range bSlice {
		if _, ok := intersect[b.name]; ok {
			intersect[b.name] = append(intersect[b.name], b)
			continue
		}
		if a, ok := inA[b.name]; ok {
			intersect[b.name] = append(a, b)
			continue
		}

	}
	fmt.Println(intersect)
}

答案2

得分: 0

我认为你可以尝试在Golang中使用Maps。平均时间复杂度为O(n),因为Golang中的Map是基于哈希表实现的。

示例代码:

aMap := make(map[string][]*structA)
for _, a := range aList {
    aMap[a.name] = append(aMap[a.name], a)
}

bMap := make(map[string][]*structB)
for _, b := range bList {
    bMap[b.name] = append(bMap[b.name], b)
}

// 获取aList和bList的交集
intersections := make([]*structB, 0, len(aList))
for k, v := range aMap {
    if b, ok := bMap[k]; ok {
        intersections = append(intersections, b...)
    }
}

这段代码创建了两个Map,分别是aMapbMap。然后,通过遍历aListbList,将它们的元素按照名称进行分组,并存储在对应的Map中。

最后,通过遍历aMap,检查bMap中是否存在相同的键,如果存在,则将对应的值添加到intersections中。

希望对你有帮助!

英文:

I think you can try to use Maps in Golang. The average complexity time is O(n) because a Map in golang base on a Hash table.
Example Code:

aMap := make(map[string][]*structA)
for _,a := range aList {
	aMap[a.name] = append(aMap[a.name], a)
}
bMap := make(map[string][]*structB)
for _,b := range bList {
	bMap[b.name] = append(bMap[b.name], b)
}
//get an intersection of aList and bList
itersections := make([]*structB, 0, len(aList))
for k,v := range aMap {
	if b, ok := bMap[k];ok {
		itersections = append(intersections, b...)
	}
}

huangapple
  • 本文由 发表于 2021年9月23日 12:24:46
  • 转载请务必保留本文链接:https://go.coder-hub.com/69294017.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定