提高两个列表交集计算的效率

在IT行业这个发展更新速度很快的行业，只有不停止的学习，才不会被行业所淘汰。如果你是Golang学习者，那么本文《提高两个列表交集计算的效率》就很适合你！本篇内容主要包括##content_title##，希望对大家的知识积累有所帮助，助力实战开发！

我有2个列表，一个列表元素类型是structa，另一个列表元素类型是structb，structa和structb之间有公共字段字符串名称。如何使用golang获取两个列表之间具有相同name的交集元素并避免o(n^2)时间复杂度。

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

注意到：每个列表中的 name 字段不是唯一的，因此转换地图方式不是解决方案

正确答案

拥有不唯一的列表并不妨碍您使用地图；您可以执行以下操作（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)
}

我想你可以尝试在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)
}
//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...)
    }
}

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《提高两个列表交集计算的效率》文章吧，也可关注golang学习网公众号了解相关技术文章。