Created
November 20, 2019 03:46
-
-
Save zhangmingkai4315/d6df22f632395f22534f65a04785250b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
test code