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

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