Golang中找到两个数组的交点哪个更快？

Question

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

Original can be a very large list, as can 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
    }
}

OR

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

As was pointed out in the comments, you are not finding an intersection rather you are finding if a single entity of original is present in target. That being said, your first example is O(N) because the range is O(N) and the map lookup is O(1). Your second example is O(N^2) because of the nested range loops. Without any benchmarking I can tell you the first method will be far superior time wise (in worst case.)

I benchmarked it just to show. With 5000 items in original, and 500 in target - running both functions above, and testing with all matching and no matching elements in target:

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

This is the benchmarking code:

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