dougu2240
dougu2240
2015-02-27 21:26

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

  • set
已采纳

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
        }
    }
}
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • doushi3202 doushi3202 6年前

    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)
        }
    }
    
    点赞 评论 复制链接分享