英文:
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,分别是aMap
和bMap
。然后,通过遍历aList
和bList
,将它们的元素按照名称进行分组,并存储在对应的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...)
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论