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

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 {

    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/op

BenchmarkDoubleUnorderedEqual-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/op

BenchmarkDoubleUnorderedEqual2-32          44420         26714 ns/op

结论 - 我将使用 Husain 的排序和比较......

Answer 3

通用的，与语言无关的：

1. 用最快的可用算法对两者进行排序

2. 遍历表 A 并与 B[currentIndexFromA] 进行比较

3. 第一次发现差异时，您知道它们持有不同的数据 - 抛出！

4. 你遍历了整个A？- 他们是一样的

我不知道 GO，但您似乎天真地在 B 中搜索 A 中的每个元素。在最坏的情况下，您会在 B 上进行多次迭代。使用高性能算法进行排序似乎更有效，即使它是额外的操作。

不幸的是，我不会提供代码示例，因为我不知道 GO。

Answer 4

您将不得不使用[]interface{}而不是[]stringthen 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

}

Answer 5

您可以先对数组进行排序，然后按索引检查：

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")

}

排序的想法是它使比较更容易和更快。排序然后按索引比较是 O(n log n)，而 2 循环检查需要 O(n^2)。