检查两个数组是否具有相同成员的最佳方法

Question

我有一个字符串数组，我需要将它与另一个字符串数组进行比较，但它们的顺序可能不同。比较这两个数组的最佳方法是什么？

这是我到目前为止所拥有的，只是想知道我是否缺少一种更简单/更有效的方法。

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

}

Answer 1

鉴于您正在进行长度检查，我将假设它们是 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    }

Answer 2

理想情况下，这将是一个评论，但 TLDR 是使用 Husain 的排序和比较更正确和更快。细节。对于查看上面 RayfenWindspear 答案（当前排名最高）的任何人，乍一看它看起来是正确的，但请注意它不检查完全相等性，而只是检查第二个列表中的每个元素都在第一个列表中. 反之亦然，但不通过此方法检查。因此它没有通过这个测试（bb重复）：assert.False(t, unorderedEqual([]string{"aa", "cc", "bb"}, []string{"aa", "bb", "bb"}))当然你可以只运行两次就得到正确的结果，这只是一个线性因素func DoubleUnorderedEqual(a, b []string) bool {&nbsp; &nbsp; return unorderedEqual(a, b) && unorderedEqual(b, a)}Husain 提出的先排序后检查的建议可能排名更高，因为它是正确的，而且对于较大的列表也更快。这是 Husain 在导出函数中的代码：func SortCompare(a, b []string) bool {&nbsp; &nbsp; if len(a) != len(b) {&nbsp; &nbsp; &nbsp; &nbsp; return false&nbsp; &nbsp; }&nbsp; &nbsp; sort.Strings(a)&nbsp; &nbsp; sort.Strings(b)&nbsp; &nbsp; for i, v := range a {&nbsp; &nbsp; &nbsp; &nbsp; if v != b[i] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return true}还有一些你可以在上面运行的测试（它通过了）func TestSortCompare(t *testing.T) {&nbsp; &nbsp; assert.True(t, SortCompare([]string{"aa"}, []string{"aa"}))&nbsp; &nbsp; assert.False(t, SortCompare([]string{"aa"}, []string{"bb"}))&nbsp; &nbsp; assert.False(t, SortCompare([]string{"aa"}, []string{"bb", "cc"}))&nbsp; &nbsp; assert.True(t, SortCompare([]string{"cc", "bb"}, []string{"bb", "cc"}))&nbsp; &nbsp; assert.True(t, SortCompare([]string{"aa", "cc", "bb"}, []string{"aa", "bb", "cc"}))&nbsp; &nbsp; assert.False(t, SortCompare([]string{"aa", "cc", "bb"}, []string{"aa", "bb", "bb"}))}这是一些示例基准测试....func getStrings() ([]string, []string) {&nbsp; &nbsp; a := []string{"a", "foo", "bar", "ping", "pong"}&nbsp; &nbsp; b := []string{"pong", "foo", "a", "bar", "ping"}&nbsp; &nbsp; return a, b}func BenchmarkSortCompare(b *testing.B) {&nbsp; &nbsp; s0, s1 := getStrings()&nbsp; &nbsp; var outcome bool&nbsp; &nbsp; for n := 0; n < b.N; n++ {&nbsp; &nbsp; &nbsp; &nbsp; outcome = SortCompare(s0, s1)&nbsp; &nbsp; }&nbsp; &nbsp; fmt.Println(outcome)}func BenchmarkDoubleUnorderedEqual(b *testing.B) {&nbsp; &nbsp; s0, s1 := getStrings()&nbsp; &nbsp; var outcome bool&nbsp; &nbsp; for n := 0; n < b.N; n++ {&nbsp; &nbsp; &nbsp; &nbsp; outcome = DoubleUnorderedEqual(s0, s1)&nbsp; &nbsp; }&nbsp; &nbsp; fmt.Println(outcome)}结果...BenchmarkSortCompare-32&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 2637952&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;498 ns/opBenchmarkDoubleUnorderedEqual-32&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;3060261&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;381 ns/op所以在这个小尺寸下运行两次 map 方法稍微快一些......但是添加更多的字符串并且 sort 方法胜出 10 倍。我没有考虑字符串中混乱程度的影响但是它们足够混乱，乍一看这并不是一个明显不公平的测试。func getStrings2() ([]string, []string) {&nbsp; &nbsp; 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"}&nbsp; &nbsp; 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"}&nbsp; &nbsp; return a, b}func BenchmarkSortCompare2(b *testing.B) {&nbsp; &nbsp; s0, s1 := getStrings2()&nbsp; &nbsp; var outcome bool&nbsp; &nbsp; for n := 0; n < b.N; n++ {&nbsp; &nbsp; &nbsp; &nbsp; outcome = SortCompare(s0, s1)&nbsp; &nbsp; }&nbsp; &nbsp; fmt.Println(outcome)}func BenchmarkDoubleUnorderedEqual2(b *testing.B) {&nbsp; &nbsp; s0, s1 := getStrings2()&nbsp; &nbsp; var outcome bool&nbsp; &nbsp; for n := 0; n < b.N; n++ {&nbsp; &nbsp; &nbsp; &nbsp; outcome = DoubleUnorderedEqual(s0, s1)&nbsp; &nbsp; }&nbsp; &nbsp; fmt.Println(outcome)}结果：BenchmarkSortCompare2-32&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 454641&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 2797 ns/opBenchmarkDoubleUnorderedEqual2-32&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 44420&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;26714 ns/op结论 - 我将使用 Husain 的排序和比较......

Answer 3

通用的，与语言无关的：用最快的可用算法对两者进行排序遍历表 A 并与 B[currentIndexFromA] 进行比较第一次发现差异时，您知道它们持有不同的数据 - 抛出！你遍历了整个A？- 他们是一样的我不知道 GO，但您似乎天真地在 B 中搜索 A 中的每个元素。在最坏的情况下，您会在 B 上进行多次迭代。使用高性能算法进行排序似乎更有效，即使它是额外的操作。不幸的是，我不会提供代码示例，因为我不知道 GO。

Answer 4

您将不得不使用[]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}

Answer 5

您可以先对数组进行排序，然后按索引检查：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)。