I have an array of strings, I need to compare this to another array of strings, but they may be in a different order. What's the best way to compare the two arrays?
This is what I have so far, just wondering if there is a simpler / more efficient way I'm missing.
func unorderedEqual(first, second []string) bool {
if len(first) != len(second) {
return false
}
for _, value := range first {
if !contains(value, second) {
return false
}
}
return true
}
func contains(needle string, haystack []string) bool {
for _, matchValue := range haystack {
if matchValue == needle {
return true
}
}
return false
}
Given that you are doing a length check, I'm going to go with the assumption that implies that they are 1:1, just ordered differently.
You can do this in one pass (each) using a map[string]bool to check existence in both. This utilizes the fact that the map returns the zero value of a bool, which is false, when the key is not present.
Disclaimer: Technically this is order O(n)*O(map). The Go Programming Language Specification does not make any performance guarantees for map types.
https://play.golang.org/p/2LUjN5LkXLL
func unorderedEqual(first, second []string) bool {
if len(first) != len(second) {
return false
}
exists := make(map[string]bool)
for _, value := range first {
exists[value] = true
}
for _, value := range second {
if !exists[value] {
return false
}
}
return true
}
If you want to get nit-picky about memory usage, you could save yourself storing a bunch of bools (which is usually negligible, but to each their own) by using a map[string]struct{} (the empty struct), and you just check existence a little differently, as in this example.
https://play.golang.org/p/MjwP_wCtYZV
Set
exists[value] = struct{}{}
Check
if _, ok := exists[value]; !ok {
return false
}
Using this dedicated package, you would have to use []interface{} instead of []string then proceed as such
package main
import (
"fmt"
"github.com/deckarep/golang-set"
)
func main() {
some := []interface{}{"a", "b", "c"}
other := []interface{}{"a", "b", "d"}
fmt.Println(
mapset.NewThreadUnsafeSetFromSlice(some).
Difference(mapset.NewThreadUnsafeSetFromSlice(other)).Cardinality() == 0,
)
// Output: false
}
Generic, language agnostic:
I don't know GO, but you seem to be naively searching for each element from A in B. In worst case scenario you get many many iterations over B. Sorting with performant algorithm seems to be way more efficient even though it's additional operation.
I unfortunately will not provide code sample, as I don't know GO.
You can sort the arrays first and then check by index:
package main
import (
"fmt"
"sort"
)
func main() {
s1 := []string{"first", "second", "third"}
s2 := []string{"third", "first", "second"}
if len(s1) != len(s2) {
fmt.Println("not equal")
}
sort.Strings(s1)
sort.Strings(s2)
for i := 0; i < len(s1); i++ {
if s1[i] != s2[i] {
fmt.Println("not equal")
return
}
}
fmt.Println("equal")
}
Or in playground.
The idea with sorting is that it makes the comparison easier and faster. Sorting and then comparing index-wise is O(n log n), while 2-loop checking takes O(n^2).