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

Question

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

原始可以是一个非常大的列表,可以作为目标

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