检查两个数组是否具有相同成员的最佳方法
我有一个字符串数组，我需要将它与另一个字符串数组进行比较，但它们的顺序可能不同。比较这两个数组的最佳方法是什么？
这是我到目前为止所拥有的，只是想知道我是否缺少一种更简单/更有效的方法。
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
}
慕哥9229398浏览 126回答 5
5回答
-
幕布斯6054654
鉴于您正在进行长度检查，我将假设它们是 1:1，只是顺序不同。您可以在一次通过（每次）中执行此操作，使用 amap[string]bool检查两者是否存在。这利用了这样一个事实，即当键不存在时，map返回 a 的零值bool，即。false免责声明：从技术上讲，这是 O(n)*O(map) 的顺序。Go Programming Language Specification不对地图类型做任何性能保证。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}如果你想对内存使用挑剔，你可以bool通过使用 a map[string]struct{}（空结构）来保存一堆 s （通常可以忽略不计，但对每个 s 来说都是），你只需稍微不同地检查存在，如本例所示。放exists[value] = struct{}{}查看if _, ok := exists[value]; !ok { return false } -
POPMUISE
理想情况下，这将是一个评论，但 TLDR 是使用 Husain 的排序和比较更正确和更快。细节。对于查看上面 RayfenWindspear 答案（当前排名最高）的任何人，乍一看它看起来是正确的，但请注意它不检查完全相等性，而只是检查第二个列表中的每个元素都在第一个列表中. 反之亦然，但不通过此方法检查。因此它没有通过这个测试（bb重复）：assert.False(t, unorderedEqual([]string{"aa", "cc", "bb"}, []string{"aa", "bb", "bb"}))当然你可以只运行两次就得到正确的结果，这只是一个线性因素func DoubleUnorderedEqual(a, b []string) bool { return unorderedEqual(a, b) && unorderedEqual(b, a)}Husain 提出的先排序后检查的建议可能排名更高，因为它是正确的，而且对于较大的列表也更快。这是 Husain 在导出函数中的代码：func SortCompare(a, b []string) bool { if len(a) != len(b) { return false } sort.Strings(a) sort.Strings(b) for i, v := range a { if v != b[i] { return false } } return true}还有一些你可以在上面运行的测试（它通过了）func TestSortCompare(t *testing.T) { assert.True(t, SortCompare([]string{"aa"}, []string{"aa"})) assert.False(t, SortCompare([]string{"aa"}, []string{"bb"})) assert.False(t, SortCompare([]string{"aa"}, []string{"bb", "cc"})) assert.True(t, SortCompare([]string{"cc", "bb"}, []string{"bb", "cc"})) assert.True(t, SortCompare([]string{"aa", "cc", "bb"}, []string{"aa", "bb", "cc"})) assert.False(t, SortCompare([]string{"aa", "cc", "bb"}, []string{"aa", "bb", "bb"}))}这是一些示例基准测试....func getStrings() ([]string, []string) { a := []string{"a", "foo", "bar", "ping", "pong"} b := []string{"pong", "foo", "a", "bar", "ping"} return a, b}func BenchmarkSortCompare(b *testing.B) { s0, s1 := getStrings() var outcome bool for n := 0; n < b.N; n++ { outcome = SortCompare(s0, s1) } fmt.Println(outcome)}func BenchmarkDoubleUnorderedEqual(b *testing.B) { s0, s1 := getStrings() var outcome bool for n := 0; n < b.N; n++ { outcome = DoubleUnorderedEqual(s0, s1) } fmt.Println(outcome)}结果...BenchmarkSortCompare-32 2637952 498 ns/opBenchmarkDoubleUnorderedEqual-32 3060261 381 ns/op所以在这个小尺寸下运行两次 map 方法稍微快一些......但是添加更多的字符串并且 sort 方法胜出 10 倍。我没有考虑字符串中混乱程度的影响但是它们足够混乱，乍一看这并不是一个明显不公平的测试。func getStrings2() ([]string, []string) { a := []string{"a", "foo", "bar", "ping", "pong", "b", "c", "g", "e", "f", "d", "h", "i", "j", "q", "l", "n", "o", "p", "k", "r", "s", "t", "u", "v", "w", "x", "y", "z"} b := []string{"pong", "foo", "a", "bar", "ping", "p", "r", "q", "s", "u", "t", "v", "j", "x", "y", "z", "b", "e", "d", "c", "h", "g", "f", "i", "w", "k", "l", "n", "o"} return a, b}func BenchmarkSortCompare2(b *testing.B) { s0, s1 := getStrings2() var outcome bool for n := 0; n < b.N; n++ { outcome = SortCompare(s0, s1) } fmt.Println(outcome)}func BenchmarkDoubleUnorderedEqual2(b *testing.B) { s0, s1 := getStrings2() var outcome bool for n := 0; n < b.N; n++ { outcome = DoubleUnorderedEqual(s0, s1) } fmt.Println(outcome)}结果：BenchmarkSortCompare2-32 454641 2797 ns/opBenchmarkDoubleUnorderedEqual2-32 44420 26714 ns/op结论 - 我将使用 Husain 的排序和比较...... -
慕桂英546537
通用的，与语言无关的：用最快的可用算法对两者进行排序遍历表 A 并与 B[currentIndexFromA] 进行比较第一次发现差异时，您知道它们持有不同的数据 - 抛出！你遍历了整个A？- 他们是一样的我不知道 GO，但您似乎天真地在 B 中搜索 A 中的每个元素。在最坏的情况下，您会在 B 上进行多次迭代。使用高性能算法进行排序似乎更有效，即使它是额外的操作。不幸的是，我不会提供代码示例，因为我不知道 GO。 -
婷婷同学_
您将不得不使用[]interface{}而不是[]stringthen proceed as suchpackage mainimport ( "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} -
慕姐4208626
您可以先对数组进行排序，然后按索引检查：package mainimport ( "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")}排序的想法是它使比较更容易和更快。排序然后按索引比较是 O(n log n)，而 2 循环检查需要 O(n^2)。
随时随地看视频慕课网APP
相关分类
Go