在 golang 中，哪个更快地找到两个数组的交集？

Question

在 golang 中寻找两个数组的交集哪个更快？

Original 可以是一个非常大的列表，target 也可以

original := []string{"test", "test2", "test3"} // n amount of items

target := map[string]bool{
    "test": true,
    "test2": true,
}

for _, val := range original {
    if target[val] {
        return true
    }
}

或

original := []string{"test", "test2", "test3"} // n amount of items
target := []string{"test", "test2"}

for _, i := range original {
    for _, x := range target {
        if i == x {
            return true
        }
    }
}

Answer 1

正如评论中所指出的，您不是在寻找交集，而是在寻找 original 中是否存在 target 中的单个实体。也就是说，您的第一个示例是 O(N)，因为范围是 O(N)，地图查找是 O(1)。你的第二个例子是 O(N^2) 因为嵌套的范围循环。在没有任何基准测试的情况下，我可以告诉你第一种方法在时间上要好得多（在最坏的情况下。）

我对它进行了基准测试只是为了展示。原始项目有 5000 个项目，目标项目有 500 个项目 - 运行以上两个功能，并在目标项目中使用所有匹配和无匹配元素进行测试：

BenchmarkMapLookup             50000         39756 ns/op
BenchmarkNestedRange             300       4508598 ns/op
BenchmarkMapLookupNoMatch      10000        103441 ns/op
BenchmarkNestRangeNoMatch        300       4528756 ns/op
ok      so  7.072s

这是基准测试代码：

package main

import (
    "math/rand"
    "testing"
    "time"
)

var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func randSeq(n int) string {
    b := make([]rune, n)
    for i := range b {
        b[i] = letters[rand.Intn(len(letters))]
    }
    return string(b)
}

var (
    original         = []string{}
    target           = []string{}
    targetMap        = map[string]bool{}
    targetNoMatch    = []string{}
    targetMapNoMatch = map[string]bool{}
)

func init() {
    rand.Seed(time.Now().UTC().UnixNano())
    numItems := 5000
    for i := 0; i < numItems; i++ {
        original = append(original, randSeq(10))
    }

    i := rand.Intn(numItems)
    if i >= 4500 {
        i = 4499
    }
    stop := i + 500
    for ; i < stop; i++ {
        target = append(target, original[i])
        targetMap[original[i]] = true
        noMatch := randSeq(9)
        targetNoMatch = append(target, noMatch)
        targetMapNoMatch[noMatch] = true
    }

}

func ON(orig []string, tgt map[string]bool) bool {
    for _, val := range orig {
        if tgt[val] {
            return true
        }
    }
    return false
}

func ON2(orig, tgt []string) bool {
    for _, i := range orig {
        for _, x := range tgt {
            if i == x {
                return true
            }
        }
    }
    return false
}

func BenchmarkMapLookup(b *testing.B) {
    for i := 0; i < b.N; i++ {
        ON(original, targetMap)
    }
}

func BenchmarkNestedRange(b *testing.B) {
    for i := 0; i < b.N; i++ {
        ON2(original, target)
    }
}

func BenchmarkMapLookupNoMatch(b *testing.B) {
    for i := 0; i < b.N; i++ {
        ON(original, targetMapNoMatch)
    }
}

func BenchmarkNestRangeNoMatch(b *testing.B) {
    for i := 0; i < b.N; i++ {
        ON2(original, targetNoMatch)
    }
}

在 golang 中，哪个更快地找到两个数组的交集？

Which is faster in golang for finding intersection of two arrays?

intersection

set

go