In Go, I am using ints to represent elements of a set, sorted []int to represent a subset, and [][]int to represent a set of subsets. A two identical []int slices (subsets) should not be allowed. Thus given some var setOfSubets [][]int, I would like to detect duplicate []int slices in setOfSubets. What is an efficient idomatic way to detect these duplicates?
We can assume that the elements of the subset are sorted.
For my program, I will return an error when the first duplicate is detected.
As an example, a user could create setOfSubsets
setOfSubsets := make([][]int, 0)
subSetA := []int{0, 1} // 0 and 1 are elements
subSetB := []int{0, 2} // 0 and 2 are elements
subSetADuplicate := []int{0, 1} // 0 and 1 are elements
setOfSubsets = append(setOfSubsets, subSetA)
setOfSubsets = append(setOfSubsets, subSetB)
setOfSubsets = append(setOfSubsets, subSetADuplicate)
// many more subsets added before the client calls
check(setOfSubets)
then my code check(setOfSubsets [][]int) error should detect that {0, 1} is duplicated. In the real program, there could be thousands of elements and perhaps millions of subsets. To be clear, my question is how to best write check(setOfSubsets [][]int)
I thought of using a map with []int as the key but I realized that is not allowed in Go. I also considered sorting the set of subsets and then checking adjacent subsets []int slices but I am not sure that is idiomatic or efficient.
4
You could write your check() function like this:
func check(sos [][]int) error {
for i, arr1 := range sos {
for j, arr2 := range sos {
// no point in comparing an array to itself
// or repeating a comparison that was already made
if i <= j {
continue
}
if slices.Compare(arr1, arr2) == 0 {
return fmt.Errorf("arrays %d and %d are the same: %v", i, j, arr1)
}
}
}
return nil
}
Playgound: https://go.dev/play/p/lyxpgtXF4OX
2
One simple approach is to sort subsets []][]int which will make duplicate subsets adjacent to each other (there can several groups of duplicate elements). Then duplicate subsets can be found by checking if adjacent subsets are equal. The code example below returns nil if there are no duplicates (all subsets are unique) or an error about one duplicate found (there could be more).
func checkSubsetsForDuplicates(subsets [][]int) error {
subsetsCopy := make([][]int, len(subsets))
// This copy could be omitted if it is ok to change the order of subsets
copy(subsetsCopy, subsets)
slices.SortFunc(subsetsCopy, slices.Compare)
prevSubset := subsetsCopy[0]
for _, subset := range subsetsCopy[1:] {
if slices.Equal(prevSubset, subset) {
return fmt.Errorf(
"duplicate subsets are not allowed. The subset %v was found twice",
subset)
}
prevSubset = subset
}
return nil
}
I’ve benchmarked this approach using
func BenchmarkCheckSubsetsForDuplicates(b *testing.B) {
// Use combinations to get unique subsets.
subsets := combin.Combinations(25, 10) // "gonum.org/v1/gonum/stat/combin"
assert.Assert(b, len(subsets) == 3268760) // expected number of combinations
b.ResetTimer()
for i := 0; i < b.N; i++ {
b.StopTimer()
// Shuffle for an unbiased order of the subsets
rand.Shuffle(len(subsets), func(i, j int) { subsets[i], subsets[j] = subsets[j], subsets[i] })
b.StartTimer()
err := checkSubsetsForDuplicates(subsets)
assert.NilError(b, err)
}
getting results
cpu: Intel(R) Processor 5Y10 CPU @ 0.80GHz
BenchmarkCheckSubsetsForDuplicates-4 1 4126782886 ns/op
BenchmarkCheckSubsetsForDuplicates-4 1 3947514637 ns/op
BenchmarkCheckSubsetsForDuplicates-4 1 3824476894 ns/op
BenchmarkCheckSubsetsForDuplicates-4 1 3805860089 ns/op
PASS
on my 8 year old laptop. For this data, checkSubsetsForDuplicates takes around 4 seconds. The timing results will depend of the specific data but I have satisfied “millions of subsets” as stated in the question.
For a map. You could sort and stringify each []int. I figure that’s the most straight-forward solution. A more elaborate hash would be assign to each value in an []int to the according prime number (e.g. if you only have positive numbers: 0->2, 1->3, 2->5 etc.), and multiply them. The product would be the key which directly tells you whether the two slices are equal or not. But ofc. this can get out of hands quickly if the length of an int slices is high, or if the range of possible int values is large and therefore demands high prime numbers.
If you’re fine with iterating over multiple sorted slices, then slices.BinarySearch is probably a good start. You’ld still have to iterate over all (possible millions) of slices and check whether the a given number is present, but the time for each check would “only” be O(log n). You can compare slice lenghts first to speed up this process. To speed this up even further you could sort the [][]int by the highest value in each []int, and therefore apply some “meta” binary search by singling out []int slices which can’t possibly contain your lookup slice. Here, you need a way to find out quickly what the highest number in an []int actually is, for example by sorting them or by replacing them with a struct IntSlice {Highest int, Values []int}.
Like almost(?) always, the faster the lookup is supposed to be, the longer writing into the structure will actually take, so you should be careful when you’re overdoing it. It’s hard to tell which approach is the best, b/c it depends on the size of each slice, the range of numbers in each slice, the number of reads compared to the number of writes/updates of the [][]int, the distribution etc.