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