map_test.go

package phrasetrie

import (
	"math/rand"
	"sort"
	"testing"
)

type mp map[int]struct{}

func newMap(vs []int) mp {
	m := make(map[int]struct{}, len(vs))
	for _, k := range vs {
		m[k] = struct{}{}
	}
	return m
}

func (m mp) has(k int) bool {
	_, ok := m[k]
	return ok
}

type srange []int

func newSlice(vs []int) srange {
	item := make([]int, len(vs))
	copy(item, vs)
	sort.Sort(sort.IntSlice(item))
	return item
}

func (s srange) has(k int) bool {
	for _, v := range s {
		if k == v {
			return true
		}
		if k < v {
			return false
		}
	}
	return false
}

type smp []bool

func newSliceMap(vs []int) smp {
	max := 0
	for _, v := range vs {
		if max < v {
			max = v
		}
	}
	m := make([]bool, max+1)
	for _, v := range vs {
		m[v] = true
	}
	return m
}

func (s smp) has(k int) bool {
	return s[k]
}

func makeSlice(size, max int) []int {
	m := make([]int, size)
	e := make(map[int]bool, size)
	for i := range m {
		for m[i] > 0 {
			v := rand.Intn(max)
			if !e[v] {
				m[i] = v
				e[v] = true
			}
		}
	}
	if !e[max] {
		m[rand.Intn(size)] = max
	}
	return m
}

func BenchmarkMap(b *testing.B) {
	for _, c := range []struct {
		name string
		max  int
		data []int
	}{
		{"30_255", 255, makeSlice(30, 255)},
		{"100_255", 255, makeSlice(100, 255)},
		{"255_255", 255, makeSlice(255, 255)},
		// {"30_511", 511, makeSlice(30, 511)},
		// {"100_511", 511, makeSlice(100, 511)},
		// {"300_511", 511, makeSlice(200, 511)},
	} {
		b.Run("map-"+c.name, func(b *testing.B) {
			t := newMap(c.data)
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				v := rand.Intn(c.max)
				t.has(v)
			}
		})
		b.Run("slice-"+c.name, func(b *testing.B) {
			t := newSlice(c.data)
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				v := rand.Intn(c.max)
				t.has(v)
			}
		})

		b.Run("sliceMap-"+c.name, func(b *testing.B) {
			t := newSliceMap(c.data)
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				v := rand.Intn(c.max)
				t.has(v)
			}
		})
	}
}

goos: linux
goarch: amd64
BenchmarkMap/map-30_255-2               26184562                44.9 ns/op             0 B/op          0 allocs/op
BenchmarkMap/slice-30_255-2             16338622                67.8 ns/op             0 B/op          0 allocs/op
BenchmarkMap/sliceMap-30_255-2          38435748                31.0 ns/op             0 B/op          0 allocs/op
BenchmarkMap/map-100_255-2              25903686                45.8 ns/op             0 B/op          0 allocs/op
BenchmarkMap/slice-100_255-2             8872989               127 ns/op               0 B/op          0 allocs/op
BenchmarkMap/sliceMap-100_255-2         38703240                31.4 ns/op             0 B/op          0 allocs/op
BenchmarkMap/map-255_255-2              24418383                46.5 ns/op             0 B/op          0 allocs/op
BenchmarkMap/slice-255_255-2             4521410               259 ns/op               0 B/op          0 allocs/op
BenchmarkMap/sliceMap-255_255-2         34008592                31.9 ns/op             0 B/op          0 allocs/op