how to get intersection between 2 lists faster-CodePudding

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

CodePudding user response：

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)
}

CodePudding user response：

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] = a
}
bMap := make(map[string]*strucB)
for _,b := range bList {
    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)
    }
}