int_member_test.go

package set_test

import (
	"math/rand"
	"testing"
)

func BenchmarkIntMap_2key(b *testing.B)       { benchIntMapMembers(b, 2) }
func BenchmarkIntMap_3key(b *testing.B)       { benchIntMapMembers(b, 3) }
func BenchmarkIntMap_4key(b *testing.B)       { benchIntMapMembers(b, 4) }
func BenchmarkIntMap_5key(b *testing.B)       { benchIntMapMembers(b, 5) }
func BenchmarkIntMap_6key(b *testing.B)       { benchIntMapMembers(b, 6) }
func BenchmarkIntMap_7key(b *testing.B)       { benchIntMapMembers(b, 7) }
func BenchmarkIntMap_8key(b *testing.B)       { benchIntMapMembers(b, 8) }
func BenchmarkIntMap_9key(b *testing.B)       { benchIntMapMembers(b, 9) }
func BenchmarkIntMap_10key(b *testing.B)      { benchIntMapMembers(b, 10) }
func BenchmarkIntMap_100key(b *testing.B)     { benchIntMapMembers(b, 100) }
func BenchmarkIntMap_1000key(b *testing.B)    { benchIntMapMembers(b, 1000) }
func BenchmarkIntMap_10000key(b *testing.B)   { benchIntMapMembers(b, 10000) }
func BenchmarkIntMap_100000key(b *testing.B)  { benchIntMapMembers(b, 100000) }
func BenchmarkIntMap_1000000key(b *testing.B) { benchIntMapMembers(b, 1000000) }

func BenchmarkIntSlice_2key(b *testing.B)       { benchIntSliceMembers(b, 2) }
func BenchmarkIntSlice_3key(b *testing.B)       { benchIntSliceMembers(b, 3) }
func BenchmarkIntSlice_4key(b *testing.B)       { benchIntSliceMembers(b, 4) }
func BenchmarkIntSlice_5key(b *testing.B)       { benchIntSliceMembers(b, 5) }
func BenchmarkIntSlice_6key(b *testing.B)       { benchIntSliceMembers(b, 6) }
func BenchmarkIntSlice_7key(b *testing.B)       { benchIntSliceMembers(b, 7) }
func BenchmarkIntSlice_8key(b *testing.B)       { benchIntSliceMembers(b, 8) }
func BenchmarkIntSlice_9key(b *testing.B)       { benchIntSliceMembers(b, 9) }
func BenchmarkIntSlice_10key(b *testing.B)      { benchIntSliceMembers(b, 10) }
func BenchmarkIntSlice_100key(b *testing.B)     { benchIntSliceMembers(b, 100) }
func BenchmarkIntSlice_1000key(b *testing.B)    { benchIntSliceMembers(b, 1000) }
func BenchmarkIntSlice_10000key(b *testing.B)   { benchIntSliceMembers(b, 10000) }
func BenchmarkIntSlice_100000key(b *testing.B)  { benchIntSliceMembers(b, 100000) }
func BenchmarkIntSlice_1000000key(b *testing.B) { benchIntSliceMembers(b, 1000000) }

func BenchmarkIntMapNot_10key(b *testing.B)      { benchIntMapNotMembers(b, 10) }
func BenchmarkIntMapNot_1000key(b *testing.B)    { benchIntMapNotMembers(b, 1000) }
func BenchmarkIntMapNot_1000000key(b *testing.B) { benchIntMapNotMembers(b, 1000000) }

func BenchmarkIntSliceNot_10key(b *testing.B)      { benchIntSliceNotMembers(b, 10) }
func BenchmarkIntSliceNot_10000key(b *testing.B)   { benchIntSliceNotMembers(b, 10000) }
func BenchmarkIntSliceNot_1000000key(b *testing.B) { benchIntSliceNotMembers(b, 1000000) }

// Helpers

func benchIntMapMembers(b *testing.B, size int) {
	m := makeRandomIntMap(size)
	samples := sampleFromIntMap(m, b.N)
	var member int
	var ok bool
	// b.Log("starting")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		member = samples[i]
		ok = isIntMapMember(m, member)
	}
	_ = ok
}

func benchIntMapNotMembers(b *testing.B, size int) {
	m := makeRandomIntMap(size)
	samples := sampleNotInIntMap(m, b.N)

	var member int
	var ok bool
	// b.Log("starting")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		member = samples[i]
		ok = isIntMapMember(m, member)
	}
	_ = ok
}

func benchIntSliceMembers(b *testing.B, size int) {
	s := makeRandomIntSlice(size)
	samples := sampleFromIntSlice(s, b.N)
	var member int
	var ok bool
	// b.Log("starting")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		member = samples[i]
		ok = isIntSliceMember(s, member)
	}
	_ = ok
}

func benchIntSliceNotMembers(b *testing.B, size int) {

	s := makeRandomIntSlice(size)

	samples := sampleNotInIntSlice(s, b.N)
	var member int
	var ok bool
	// b.Log("starting")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		member = samples[i]
		ok = isIntSliceMember(s, member)
	}
	_ = ok
}

// Membership tests

func isIntMapMember(m map[int]bool, key int) bool {
	_, ok := m[key]
	return ok
}

func isIntSliceMember(s []int, key int) bool {
	for _, entry := range s {
		if key == entry {
			return true
		}
	}
	return false
}

// Maps

func makeRandomIntMap(n int) map[int]bool {
	set := make(map[int]bool, n)
	var i int
	for len(set) != n {
		i = rand.Int()
		if _, ok := set[i]; !ok {
			set[i] = true
		}
	}
	return set
}

func sampleFromIntMap(m map[int]bool, size int) (samples []int) {
	var keys []int
	for key := range m {
		keys = append(keys, key)
	}
	for i := 0; i < size; i++ {
		idx := rand.Intn(len(keys))
		samples = append(samples, keys[idx])
	}
	return
}

func sampleNotInIntMap(m map[int]bool, size int) (samples []int) {
	var i int
	for len(samples) != size {
		i = rand.Int()
		if !m[i] {
			samples = append(samples, i)
		}
	}
	return
}

// Slices

func makeRandomIntSlice(size int) (uniques []int) {
	set := make(map[int]bool, size)
	var i int
	for len(uniques) != size {
		i = rand.Int()
		if _, ok := set[i]; !ok {
			set[i] = true
			uniques = append(uniques, i)
		}
	}
	return
}

func sampleFromIntSlice(s []int, size int) (samples []int) {
	for i := 0; i < size; i++ {
		idx := rand.Intn(len(s))
		samples = append(samples, s[idx])
	}
	return
}

func sampleNotInIntSlice(s []int, size int) (samples []int) {
	set := make(map[int]bool, size)
	for _, key := range s {
		set[key] = true
	}

	var i int
	for len(samples) != size {
		i = rand.Int()
		if _, ok := set[i]; !ok {
			samples = append(samples, i)
		}
	}
	return
}

string_member_test.go

package set_test

import (
	"math/rand"
	"testing"
)

func BenchmarkMap_2key_10bytes(b *testing.B)        { benchMapMembers(b, 2, 10) }
func BenchmarkMap_3key_10bytes(b *testing.B)        { benchMapMembers(b, 3, 10) }
func BenchmarkMap_4key_10bytes(b *testing.B)        { benchMapMembers(b, 4, 10) }
func BenchmarkMap_5key_10bytes(b *testing.B)        { benchMapMembers(b, 5, 10) }
func BenchmarkMap_6key_10bytes(b *testing.B)        { benchMapMembers(b, 6, 10) }
func BenchmarkMap_7key_10bytes(b *testing.B)        { benchMapMembers(b, 7, 10) }
func BenchmarkMap_8key_10bytes(b *testing.B)        { benchMapMembers(b, 8, 10) }
func BenchmarkMap_9key_10bytes(b *testing.B)        { benchMapMembers(b, 9, 10) }
func BenchmarkMap_10key_10bytes(b *testing.B)       { benchMapMembers(b, 10, 10) }
func BenchmarkMap_100key_10bytes(b *testing.B)      { benchMapMembers(b, 100, 10) }
func BenchmarkMap_1000key_10bytes(b *testing.B)     { benchMapMembers(b, 1000, 10) }
func BenchmarkMap_10000key_10bytes(b *testing.B)    { benchMapMembers(b, 10000, 10) }
func BenchmarkMap_100000key_10bytes(b *testing.B)   { benchMapMembers(b, 100000, 10) }
func BenchmarkMap_1000000key_10bytes(b *testing.B)  { benchMapMembers(b, 1000000, 10) }
func BenchmarkMap_2key_100bytes(b *testing.B)       { benchMapMembers(b, 2, 100) }
func BenchmarkMap_3key_100bytes(b *testing.B)       { benchMapMembers(b, 3, 100) }
func BenchmarkMap_4key_100bytes(b *testing.B)       { benchMapMembers(b, 4, 100) }
func BenchmarkMap_5key_100bytes(b *testing.B)       { benchMapMembers(b, 5, 100) }
func BenchmarkMap_6key_100bytes(b *testing.B)       { benchMapMembers(b, 6, 100) }
func BenchmarkMap_7key_100bytes(b *testing.B)       { benchMapMembers(b, 7, 100) }
func BenchmarkMap_8key_100bytes(b *testing.B)       { benchMapMembers(b, 8, 100) }
func BenchmarkMap_9key_100bytes(b *testing.B)       { benchMapMembers(b, 9, 100) }
func BenchmarkMap_10key_100bytes(b *testing.B)      { benchMapMembers(b, 10, 100) }
func BenchmarkMap_100key_100bytes(b *testing.B)     { benchMapMembers(b, 100, 100) }
func BenchmarkMap_1000key_100bytes(b *testing.B)    { benchMapMembers(b, 1000, 100) }
func BenchmarkMap_10000key_100bytes(b *testing.B)   { benchMapMembers(b, 10000, 100) }
func BenchmarkMap_100000key_100bytes(b *testing.B)  { benchMapMembers(b, 100000, 100) }
func BenchmarkMap_1000000key_100bytes(b *testing.B) { benchMapMembers(b, 1000000, 100) }

func BenchmarkSlice_2key_10bytes(b *testing.B)        { benchSliceMembers(b, 2, 10) }
func BenchmarkSlice_3key_10bytes(b *testing.B)        { benchSliceMembers(b, 3, 10) }
func BenchmarkSlice_4key_10bytes(b *testing.B)        { benchSliceMembers(b, 4, 10) }
func BenchmarkSlice_5key_10bytes(b *testing.B)        { benchSliceMembers(b, 5, 10) }
func BenchmarkSlice_6key_10bytes(b *testing.B)        { benchSliceMembers(b, 6, 10) }
func BenchmarkSlice_7key_10bytes(b *testing.B)        { benchSliceMembers(b, 7, 10) }
func BenchmarkSlice_8key_10bytes(b *testing.B)        { benchSliceMembers(b, 8, 10) }
func BenchmarkSlice_9key_10bytes(b *testing.B)        { benchSliceMembers(b, 9, 10) }
func BenchmarkSlice_10key_10bytes(b *testing.B)       { benchSliceMembers(b, 10, 10) }
func BenchmarkSlice_100key_10bytes(b *testing.B)      { benchSliceMembers(b, 100, 10) }
func BenchmarkSlice_1000key_10bytes(b *testing.B)     { benchSliceMembers(b, 1000, 10) }
func BenchmarkSlice_10000key_10bytes(b *testing.B)    { benchSliceMembers(b, 10000, 10) }
func BenchmarkSlice_100000key_10bytes(b *testing.B)   { benchSliceMembers(b, 100000, 10) }
func BenchmarkSlice_1000000key_10bytes(b *testing.B)  { benchSliceMembers(b, 1000000, 10) }
func BenchmarkSlice_2key_100bytes(b *testing.B)       { benchSliceMembers(b, 2, 100) }
func BenchmarkSlice_3key_100bytes(b *testing.B)       { benchSliceMembers(b, 3, 100) }
func BenchmarkSlice_4key_100bytes(b *testing.B)       { benchSliceMembers(b, 4, 100) }
func BenchmarkSlice_5key_100bytes(b *testing.B)       { benchSliceMembers(b, 5, 100) }
func BenchmarkSlice_6key_100bytes(b *testing.B)       { benchSliceMembers(b, 6, 100) }
func BenchmarkSlice_7key_100bytes(b *testing.B)       { benchSliceMembers(b, 7, 100) }
func BenchmarkSlice_8key_100bytes(b *testing.B)       { benchSliceMembers(b, 8, 100) }
func BenchmarkSlice_9key_100bytes(b *testing.B)       { benchSliceMembers(b, 9, 100) }
func BenchmarkSlice_10key_100bytes(b *testing.B)      { benchSliceMembers(b, 10, 100) }
func BenchmarkSlice_100key_100bytes(b *testing.B)     { benchSliceMembers(b, 100, 100) }
func BenchmarkSlice_1000key_100bytes(b *testing.B)    { benchSliceMembers(b, 1000, 100) }
func BenchmarkSlice_10000key_100bytes(b *testing.B)   { benchSliceMembers(b, 10000, 100) }
func BenchmarkSlice_100000key_100bytes(b *testing.B)  { benchSliceMembers(b, 100000, 100) }
func BenchmarkSlice_1000000key_100bytes(b *testing.B) { benchSliceMembers(b, 1000000, 100) }

func BenchmarkMapNot_10key_10bytes(b *testing.B)      { benchMapNotMembers(b, 10, 10) }
func BenchmarkMapNot_1000key_10bytes(b *testing.B)    { benchMapNotMembers(b, 1000, 10) }
func BenchmarkMapNot_1000000key_10bytes(b *testing.B) { benchMapNotMembers(b, 1000000, 10) }

func BenchmarkSliceNot_10key_10bytes(b *testing.B)      { benchSliceNotMembers(b, 10, 10) }
func BenchmarkSliceNot_10000key_10bytes(b *testing.B)   { benchSliceNotMembers(b, 10000, 10) }
func BenchmarkSliceNot_1000000key_10bytes(b *testing.B) { benchSliceNotMembers(b, 1000000, 10) }

// Helpers

func benchMapMembers(b *testing.B, size int, keySize int) {
	// b.Logf("making rand map, size %d, key sized %d", size, keySize)
	m := makeRandomMap(size, keySize)
	// b.Logf("taking %d rand sample in map, key sized %d", b.N)
	samples := sampleFromMap(m, b.N)
	var member string
	var ok bool
	// b.Log("starting")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		member = samples[i]
		ok = isMapMember(m, member)
	}
	_ = ok
}

func benchMapNotMembers(b *testing.B, size int, keySize int) {
	// b.Logf("making rand map, size %d, key sized %d", size, keySize)
	m := makeRandomMap(size, keySize)
	// b.Logf("taking %d rand sample not in map, key sized %d", b.N, keySize)
	samples := sampleNotInMap(m, b.N, keySize)

	var member string
	var ok bool
	// b.Log("starting")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		member = samples[i]
		ok = isMapMember(m, member)
	}
	_ = ok
}

func benchSliceMembers(b *testing.B, size int, keySize int) {
	// b.Logf("making rand slice, size %d, key sized %d", size, keySize)
	s := makeRandomSlice(size, keySize)
	// b.Logf("taking %d rand sample in slice", b.N)
	samples := sampleFromSlice(s, b.N)
	var member string
	var ok bool
	// b.Log("starting")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		member = samples[i]
		ok = isSliceMember(s, member)
	}
	_ = ok
}

func benchSliceNotMembers(b *testing.B, size int, keySize int) {
	// b.Logf("making rand slice, size %d, key sized %d", size, keySize)
	s := makeRandomSlice(size, keySize)
	// b.Logf("taking %d rand sample not in slice, key sized %d", b.N, keySize)
	samples := sampleNotInSlice(s, b.N, keySize)
	var member string
	var ok bool
	// b.Log("starting")
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		member = samples[i]
		ok = isSliceMember(s, member)
	}
	_ = ok
}

// Membership tests

func isMapMember(m map[string]bool, key string) bool {
	_, ok := m[key]
	return ok
}

func isSliceMember(s []string, key string) bool {
	for _, entry := range s {
		if key == entry {
			return true
		}
	}
	return false
}

// Maps

func makeRandomMap(n, valSize int) map[string]bool {
	set := make(map[string]bool, n)
	var str string
	for len(set) != n {
		str = makeRandomString(valSize)
		if _, ok := set[str]; !ok {
			set[str] = true
		}
	}
	return set
}

func sampleFromMap(m map[string]bool, size int) (samples []string) {
	var keys []string
	for key := range m {
		keys = append(keys, key)
	}
	for i := 0; i < size; i++ {
		idx := rand.Intn(len(keys))
		samples = append(samples, keys[idx])
	}
	return
}

func sampleNotInMap(m map[string]bool, size, keySize int) (samples []string) {
	var str string
	for len(samples) != size {
		str = makeRandomString(keySize)
		if !m[str] {
			samples = append(samples, str)
		}
	}
	return
}

// Slices

func makeRandomSlice(size, strSize int) (uniques []string) {
	set := make(map[string]bool, size)
	var str string
	for len(uniques) != size {
		str = makeRandomString(strSize)
		if _, ok := set[str]; !ok {
			set[str] = true
			uniques = append(uniques, str)
		}
	}
	return
}

func sampleFromSlice(s []string, size int) (samples []string) {
	for i := 0; i < size; i++ {
		idx := rand.Intn(len(s))
		samples = append(samples, s[idx])
	}
	return
}

func sampleNotInSlice(s []string, size, keySize int) (samples []string) {
	set := make(map[string]bool, size)
	for _, key := range s {
		set[key] = true
	}

	var str string
	for len(samples) != size {
		str = makeRandomString(keySize)
		if _, ok := set[str]; !ok {
			samples = append(samples, str)
		}
	}
	return
}

// Strings

func makeRandomString(size int) string {
	raw := make([]rune, size)
	for i := range raw {
		raw[i] = randRune()
	}
	return string(raw)
}

func randRune() rune {
	const runeString = `01234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()`
	i := rand.Intn(len(runeString))
	return []rune(runeString)[i]
}

Int map/slice membership benchmark:

BenchmarkIntMap_2key    100000000           11.3 ns/op
BenchmarkIntMap_3key    100000000           14.0 ns/op
BenchmarkIntMap_4key    100000000           16.0 ns/op
BenchmarkIntMap_5key    100000000           16.4 ns/op
BenchmarkIntMap_6key    100000000           17.4 ns/op
BenchmarkIntMap_7key    100000000           19.4 ns/op
BenchmarkIntMap_8key    100000000           20.5 ns/op
BenchmarkIntMap_9key    50000000            29.9 ns/op
BenchmarkIntMap_10key   50000000            29.9 ns/op
BenchmarkIntMap_20key   50000000            29.8 ns/op
BenchmarkIntMap_30key   50000000            28.5 ns/op
BenchmarkIntMap_40key   50000000            31.6 ns/op
BenchmarkIntMap_50key   50000000            30.7 ns/op
BenchmarkIntMap_100key  50000000            30.6 ns/op
BenchmarkIntMap_1000key 50000000            29.8 ns/op
BenchmarkIntMap_10000key    50000000            32.6 ns/op
BenchmarkIntMap_100000key   50000000            40.4 ns/op
BenchmarkIntMap_1000000key  50000000            74.7 ns/op
BenchmarkIntSlice_2key  200000000            9.02 ns/op
BenchmarkIntSlice_3key  100000000           11.1 ns/op
BenchmarkIntSlice_4key  100000000           12.3 ns/op
BenchmarkIntSlice_5key  100000000           13.2 ns/op
BenchmarkIntSlice_6key  100000000           13.7 ns/op
BenchmarkIntSlice_7key  100000000           14.5 ns/op
BenchmarkIntSlice_8key  100000000           15.1 ns/op
BenchmarkIntSlice_9key  100000000           16.0 ns/op
BenchmarkIntSlice_10key 100000000           16.7 ns/op
BenchmarkIntSlice_20key 100000000           24.6 ns/op
BenchmarkIntSlice_30key 50000000            31.1 ns/op
BenchmarkIntSlice_40key 50000000            35.3 ns/op
BenchmarkIntSlice_50key 50000000            39.5 ns/op
BenchmarkIntSlice_100key    50000000            56.2 ns/op
BenchmarkIntSlice_1000key    5000000           340 ns/op
BenchmarkIntSlice_10000key    500000          3212 ns/op
BenchmarkIntSlice_100000key    50000         31051 ns/op
BenchmarkIntSlice_1000000key        5000        331630 ns/op
BenchmarkIntMapNot_10key    100000000           25.4 ns/op
BenchmarkIntMapNot_1000key  100000000           25.5 ns/op
BenchmarkIntMapNot_1000000key   20000000            80.7 ns/op
BenchmarkIntSliceNot_10key  100000000           18.0 ns/op
BenchmarkIntSliceNot_10000key     500000          6220 ns/op
BenchmarkIntSliceNot_1000000key     5000        718006 ns/op