issubset-problem.go

package main

import (
	"flag"
	"fmt"
	"log"
	"math/rand"
	"os"
	"runtime/pprof"
	"sort"
	"strconv"
)

var cpuprofile = flag.String("cpuprofile", "", "cpu profile file path")

func isSubsetWithLoop(originalSet []int, newSet []int) bool {
	sizeOfOriginal := len(originalSet)
	sizeOfNewSet := len(newSet)
	found := 0
	if sizeOfNewSet == 0 || sizeOfOriginal < sizeOfNewSet {
		return false
	}
	for _, i := range newSet {
	inner:
		for _, j := range originalSet {
			// println(i, j)
			if i == j {
				found++
				break inner
			}
		}
	}
	return sizeOfNewSet == found
}

func isSubsetWithMap(originalSet []int, newSet []int) bool {
	sizeOfOriginal := len(originalSet)
	sizeOfNewSet := len(newSet)
	if sizeOfNewSet == 0 || sizeOfOriginal < sizeOfNewSet {
		return false
	}
	mapOfArray := make(map[int]bool, sizeOfOriginal)
	for _, v := range originalSet {
		mapOfArray[v] = true
	}
	for _, i := range newSet {
		if !mapOfArray[i] {
			return false
		}
	}
	return true
}

func binarySearch(item int, sortedArray []int, size int) bool {
	left := 0
	right := size - 1
	for left <= right {
		middle := (right + left) / 2
		if item > sortedArray[middle] {
			left = middle + 1
		} else if item < sortedArray[middle] {
			right = middle - 1
		} else {
			return true
		}
	}
	return false
}

func isSubsetWithSortAndBinarySearch(originalSet []int, newSet []int) bool {
	sizeOfOriginal := len(originalSet)
	sizeOfNewSet := len(newSet)
	if sizeOfNewSet == 0 || sizeOfOriginal < sizeOfNewSet {
		return false
	}
	sort.Ints(originalSet)
	for _, v := range newSet {
		if binarySearch(v, originalSet, sizeOfOriginal) != true {
			return false
		}
	}
	return true
}

func isSubsetWithSort(originalSet []int, newSet []int) bool {
	sizeOfOriginal := len(originalSet)
	sizeOfNewSet := len(newSet)
	if sizeOfNewSet == 0 || sizeOfOriginal < sizeOfNewSet {
		return false
	}
	sort.Ints(originalSet)
	sort.Ints(newSet)
	pointer := 0
	counter := 0
	for _, v := range newSet {
		for v1 := pointer; v1 < sizeOfOriginal; v1++ {
			if originalSet[v1] == v {
				counter++
				pointer = v1 + 1
			}
		}
	}
	return counter == sizeOfNewSet
}

func getRandomArr(size int, limit int) []int {
	arr := []int{}
	for i := 0; i < size; i++ {
		arr = append(arr, rand.Int()%limit)
	}
	return arr
}

func getOrderArr(size int, start int) []int {
	arr := []int{}
	for i := 0; i < size; i++ {
		arr = append(arr, start+i)
	}
	return arr
}
func arrayToString(arr []int) string {
	size := len(arr)
	s := "["
	for i := 0; i < size; i++ {
		if i != size-1 {
			s = s + strconv.Itoa(arr[i]) + ","
		} else {
			s = s + strconv.Itoa(arr[i])
		}
	}
	s = s + "]"
	return s
}

func shufferArray(arr []int) []int {
	rand.Shuffle(len(arr), func(i, j int) { arr[i], arr[j] = arr[j], arr[i] })
	return arr
}

func getSubsetFromArray(arr []int, size int) []int {
	if size >= len(arr) {
		return arr
	}
	temp := make([]int, size)
	copy(temp, arr)

	return temp
}

func main() {
	flag.Parse()
	arr := getOrderArr(20, 0)
	subsetOfArr := getSubsetFromArray(arr, 5)
	bigArray := shufferArray(arr)
	if *cpuprofile != "" {
		f, err := os.Create(*cpuprofile)
		if err != nil {
			log.Fatal(err)
		}
		fmt.Println("enable profile for cpu")
		pprof.StartCPUProfile(f)
		defer pprof.StopCPUProfile()
	}
	isSubsetWithLoop(bigArray, subsetOfArr)
	isSubsetWithMap(bigArray, subsetOfArr)
	isSubsetWithSort(bigArray, subsetOfArr)
	isSubsetWithSortAndBinarySearch(bigArray, subsetOfArr)

}

test code

package main

import (
	"fmt"
	"math"
	"testing"
)

func TestbinarySearch(t *testing.T) {
	testCases := []struct {
		arr1   []int
		key    int
		result bool
	}{
		{
			arr1:   []int{1, 2, 3, 4, 5, 6, 7},
			key:    1,
			result: true,
		},
		{
			arr1:   []int{1, 2, 3, 4, 5, 6, 7},
			key:    4,
			result: true,
		},
		{
			arr1:   []int{1, 2, 3, 4, 5, 6, 7},
			key:    7,
			result: true,
		},
		{
			arr1:   []int{1, 2, 3, 4, 5, 6, 7},
			key:    -4,
			result: false,
		},
		{
			arr1:   []int{1, 2, 3, 4, 5, 6, 7},
			key:    40,
			result: false,
		},
		{
			arr1:   []int{},
			key:    40,
			result: false,
		},
	}

	for _, testCase := range testCases {
		if binarySearch(testCase.key, testCase.arr1, len(testCase.arr1)) != testCase.result {
			t.Errorf(
				"binarySearch(key=%v, array=%v) \nexpect result=%v but got %v",
				testCase.key, testCase.arr1,
				testCase.result, binarySearch(testCase.key, testCase.arr1, len(testCase.arr1)),
			)
		}
	}
}

func TestIsSubsetWithMap(t *testing.T) {
	bigArray := getRandomArr(100, 10000)
	smallArray := append(getRandomArr(10, 1000), 10001)

	testCases := []struct {
		arr1   []int
		arr2   []int
		result bool
	}{
		{
			arr1:   bigArray,
			arr2:   getSubsetFromArray(shufferArray(bigArray), 5),
			result: true,
		},
		{
			arr1:   bigArray,
			arr2:   getSubsetFromArray(shufferArray(bigArray), 10),
			result: true,
		},
		{
			arr1:   bigArray,
			arr2:   getSubsetFromArray(shufferArray(bigArray), 20),
			result: true,
		},
		{
			arr1:   bigArray,
			arr2:   smallArray,
			result: false,
		},
		{
			arr1:   []int{1, 2, 3, 4, 5, 6, 7, 8},
			arr2:   []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
			result: false,
		},
		{
			arr1:   []int{},
			arr2:   []int{},
			result: false,
		},
		{
			arr1:   []int{1, 2, 3},
			arr2:   []int{},
			result: false,
		},
	}

	for _, testCase := range testCases {
		if isSubsetWithMap(testCase.arr1, testCase.arr2) != testCase.result {
			t.Errorf(
				"isSubsetWithMap(input=%v, subset=%v) \nexpect result=%v but got %v",
				testCase.arr1, testCase.arr2,
				testCase.result, isSubsetWithSort(testCase.arr1, testCase.arr2),
			)
		}
		if isSubsetWithLoop(testCase.arr1, testCase.arr2) != testCase.result {
			t.Errorf(
				"isSubsetWithLoop(input=%v, subset=%v) \nexpect result=%v but got %v",
				testCase.arr1, testCase.arr2, testCase.result,
				isSubsetWithSort(testCase.arr1, testCase.arr2),
			)
		}
		if isSubsetWithSort(testCase.arr1, testCase.arr2) != testCase.result {
			t.Errorf(
				"isSubsetWithSort(input=%v, subset=%v) \nexpect result=%v but got %v",
				testCase.arr1, testCase.arr2, testCase.result,
				isSubsetWithSort(testCase.arr1, testCase.arr2),
			)
		}
		if isSubsetWithSortAndBinarySearch(testCase.arr1, testCase.arr2) != testCase.result {
			t.Errorf(
				"isSubsetWithSortAndBinarySearch(input=%v, subset=%v) \nexpect result=%v but got %v",
				testCase.arr1, testCase.arr2, testCase.result,
				isSubsetWithSortAndBinarySearch(testCase.arr1, testCase.arr2),
			)
		}
	}
}

func BenchmarkIsSubset(b *testing.B) {
	subsetFuncs := []struct {
		name string
		fun  func(originalSet []int, newSet []int) bool
	}{

		{"map", isSubsetWithMap},
		// {"sortTwoArray", isSubsetWithSort},
		// {"sortWithBinarySearch", isSubsetWithSortAndBinarySearch},
		{"loop", isSubsetWithLoop},
	}

	for _, subsetFuncStruct := range subsetFuncs {
		subset := getRandomArr(3, 100)
		for k := 3.; k <= 10; k++ {
			max := int(math.Pow(2, k))
			arr := shufferArray(getRandomArr(max, max*2))
			b.Run(fmt.Sprintf("%s/%d/%d", subsetFuncStruct.name, len(subset), len(arr)), func(b *testing.B) {
				for i := 0; i < b.N; i++ {
					subsetFuncStruct.fun(arr, subset)
				}
			})
		}
	}
}

func BenchmarkIsSubsetWithSameTimes(b *testing.B) {
	arr := shufferArray(getRandomArr(20, 100))
	subset := getRandomArr(5, 100)
	for i := 0; i < b.N; i++ {
		isSubsetWithMap(arr, subset)
		isSubsetWithLoop(arr, subset)
	}
}