如何在golang中获得两个切片的交集?

有什么有效的方法让Go的两个切片相交吗?

我想避免嵌套的类似循环的解决方案。
slice1 := []string{"foo", "bar","hello"}
slice2 := []string{"foo", "bar"}

intersection(slice1, slice2)
=> ["foo", "bar"]
字符串的顺序不重要。
dotymq4217
dotymq4217 看起来您正在寻找此设置库:github.com/deckarep/golang-set
大约 3 年之前 回复

5个回答

Yes there are a few different ways to go about it.. Here's an example that can be optimized.

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
", intersection(slice1, slice2))
}

Now the intersection method defined above will only operate on slices of strings, like your example.. You can in theory create a definition that looks like this func intersection(a []interface, b []interface) (inter []interface), however you would be relying on reflection and type casting so that you can compare, which will add latency and make your code harder to read. It's probably easier to maintain and read to write a separate function for each type you care about.

func intersectionString(a []string, b []string) (inter []string),

func intersectionInt(a []int, b []int) (inter []int),

func intersectionFloat64(a []Float64, b []Float64) (inter []Float64), ..ect

You can then create your own package and reuse once you settle how you want to implement it.

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)



https://github.com/viant/toolbox/blob/master/collections.go </ p>

另一个使用O(m + n)时间复杂度的解决方案 哈希图。

与此处讨论的其他解决方案相比,有两个区别。</ p>


  • 将目标切片作为参数传递,而不是返回新的切片</ li>
  • 更快地用于诸如string / int之类的常用类型,而不是对所有类型的反射</ li>
    </ ul>
    </ div>

展开原文

原文

https://github.com/viant/toolbox/blob/master/collections.go

Another O(m+n) Time Complexity solution that uses a hashmap. It has two differences compared to the other solutions discussed here.

  • Passing the target slice as a parameter instead of new slice returned
  • Faster to use for commonly used types like string/int instead of reflection for all



如果您的 [] string </ code>中没有空格,也许您需要以下简单代码:</ p >

  func filter(src [] string)(res [] string){
表示_,s:= range src {
newStr:= strings.Join(res,“” )
if!strings.Contains(newStr,s){
res = append(res,s)
}
}
return
}

func交集(section1,section2 [] string)( 交集[] string){
str1:= strings.Join(filter(section1),“”)
表示_,s:=范围filter(section2){
如果是string.Contains(str1,s){\ n交集= append(intersection,s)
}
}
返回
}
</ code> </ pre>
</ div>

展开原文

原文

if there exists no blank in your []string, maybe you need this simple code:

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
}

dongxin1999
dongxin1999 这是一种奇怪的方法。 我会对Contains vs hash的基准感兴趣
一年多之前 回复



如何获取两个数组之间的交集作为新数组? </ p>


  • 简单交集:比较 A </ code>中的每个元素与 B </ code>中的每个元素( O(n ^ 2)</ code>)</ li>
  • 哈希交集:将它们放入哈希表( O(n)</ code>)</ li>
  • 排序交集:对 A </ code>进行排序并进行优化交集(< code> O(n * log(n))</ code>)</ li>
    </ ul>

    所有这些都在此处实现</ p>

    https://github.com/juliangruber/go-intersect </ p>
    </ DIV>

展开原文

原文

How do I get the intersection between two arrays as a new array?

  • Simple Intersection: Compare each element in A to each in B (O(n^2))
  • Hash Intersection: Put them into a hash table (O(n))
  • Sorted Intersection: Sort A and do an optimized intersection (O(n*log(n)))

All of which are implemented here

https://github.com/juliangruber/go-intersect

dongqiao5573
dongqiao5573 只需运行go,即可获取“ github.com/juliangruber/go-intersect”。 然后,您可以使用相同的路径访问其代码。 不要忘了给那个家伙以谢意:)
大约 3 年之前 回复
dongxifu5009
dongxifu5009 我知道RP是谁,他的话跟其他人一样,不是福音。 仅仅因为算法更快,并不意味着它“花哨”。 我真正在说“规则2”-测试可用的选项,然后根据经验观察选择最适合该情况的选项。
大约 3 年之前 回复
dp518158
dp518158 告诉Rob Pike(en.wikipedia.org/wiki/Rob_Pike)。 在此处查看他的规则3:users.ece.utexas.edu/~adnan/pike.html
大约 3 年之前 回复
dongqiuwei8667
dongqiuwei8667 您无法基于“可能”具有更多开销的方式进行类似的概括。 最好选择最有效的方法,最好对每个方法进行实际测试,看看哪些方法可以满足特定情况的要求。
大约 3 年之前 回复
douju2599
douju2599 请记住,尽管对于大的$ n $,$ O(n)$解决方案比$ O(n ^ 2)$解决方案要好,但是如果$ n $小,则最好使用$ O(n ^ 2) $ O(n)$解决方案比$ O解决方案要多,因为后者可能会有更多开销。
大约 3 年之前 回复
duanhe1903
duanhe1903 否。为此,没有内置软件包。
大约 3 年之前 回复
drws65968272
drws65968272 我们可以在构建库中使用它吗?
大约 3 年之前 回复



这是使两个切片相交的最佳方法。 时间复杂度太低。</ p>

时间复杂度:O(m + n)</ p>

m =第一个切片的长度。</ p>

n =第二个切片的长度。</ p>

  func相交(s1,s2 [] string)(inter [] string){
hash:= make( map [string] bool)
表示_,e:=范围s1 {
hash [e] = true
}
表示_,e:=范围s2 {
//如果元素存在于哈希图中,则 附加交集列表。
if hash [e] {
inter = append(inter,e)
}
}
//从切片中删除公仔。
inter = removeDups(inter)
return
}

//从切片中删除复制项。
func removeDups(elements [] string)(nodups [] string){
遇到了:= make(map [string] bool)
为_,element:= range 元素{
如果!encountered [element] {
nodups = append(nodups,element)
遇到[element] = true
}
}
return
}
</ code> </ pre >
</ div>

展开原文

原文

It's a best method for intersection two slice. Time complexity is too low.

Time Complexity : O(m+n)

m = length of first slice.

n = length of second slice.

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
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐