无序检查切片是否相等

Question

我正在尝试找到一种解决方案来检查 2 个切片是否相等。不幸的是，我找到的答案要求切片中的值具有相同的顺序。例如，http://play.golang.org/p/yV0q1_u3xR 将相等性评估为 false。
我想要一个让 []string{"a","b","c"} == []string{"b","a","c"} 评估为 true.
的解决方案 更多示例
[]string{"a","a","c"} == []string{"c","a","c"} >>> false
[]string{"z","z","x"} == []string{"x","z","z"} >>> true

Answer 1

这是一个替代解决方案，虽然可能有点冗长：

func sameStringSlice(x, y []string) bool {
    if len(x) != len(y) {
        return false
    }
    // create a map of string -> int
    diff := make(map[string]int, len(x))
    for _, _x := range x {
        // 0 value for int is 0, so just increment a counter for the string
        diff[_x]++
    }
    for _, _y := range y {
        // If the string _y is not in diff bail out early
        if _, ok := diff[_y]; !ok {
            return false
        }
        diff[_y] -= 1
        if diff[_y] == 0 {
            delete(diff, _y)
        }
    }
    return len(diff) == 0
}

在 Go Playground

上试用

Answer 2

我认为最简单的方法是将每个 array/slice 中的元素映射到它们的出现次数，然后比较映射：

func main() {
    x := []string{"a","b","c"}
    y := []string{"c","b","a"}

    xMap := make(map[string]int)
    yMap := make(map[string]int)

    for _, xElem := range x {
        xMap[xElem]++
    }
    for _, yElem := range y {
        yMap[yElem]++
    }

    for xMapKey, xMapVal := range xMap {
        if yMap[xMapKey] != xMapVal {
            return false
        }
    }
    return true
}

如果您的 arrays/slices 包含不同类型或不同长度的元素，您将需要添加一些额外的尽职调查，例如短路。

Answer 3

其他答案的时间复杂度更好 O(N) vs (O(N log(N))，在我的答案中，如果切片中的元素频繁重复，我的解决方案也会占用更多内存，但我想要添加它，因为我认为这是最直接的方法：

package main

import (
    "fmt"
    "sort"
    "reflect"
)

func array_sorted_equal(a, b []string) bool {
    if len(a) != len(b) {return false }

    a_copy := make([]string, len(a))
    b_copy := make([]string, len(b))

    copy(a_copy, a)
    copy(b_copy, b)

    sort.Strings(a_copy)
    sort.Strings(b_copy)

    return reflect.DeepEqual(a_copy, b_copy)
}

func main() {
    a := []string {"a", "a", "c"}
    b := []string {"c", "a", "c"}
    c := []string {"z","z","x"} 
    d := []string {"x","z","z"}


    fmt.Println( array_sorted_equal(a, b))
    fmt.Println( array_sorted_equal(c, d))

}

结果：

false
true

Answer 4

我知道它已得到回答，但我仍然想添加我的答案。通过这里的代码 stretchr/testify 我们可以得到类似

的东西

  func Elementsmatch(listA, listB []string) (string, bool) {
    aLen := len(listA)
    bLen := len(listB)

    if aLen != bLen {
        return fmt.Sprintf("Len of the lists don't match , len listA %v, len listB %v", aLen, bLen), false
    }

    visited := make([]bool, bLen)

    for i := 0; i < aLen; i++ {
        found := false
        element := listA[i]
        for j := 0; j < bLen; j++ {
            if visited[j] {
                continue
            }
            if element == listB[j] {
                visited[j] = true
                found = true
                break
            }
        }
        if !found {
            return fmt.Sprintf("element %s appears more times in %s than in %s", element, listA, listB), false
        }
    }
    return "", true
}

现在我们来谈谈这个解决方案与基于地图的解决方案相比的性能。好吧，这实际上取决于您要比较的列表的大小，如果列表的大小很大（我会说大于 20），那么 map 方法更好，否则就足够了。

好的 Go PlayGround 它总是显示 0，但是运行这在本地系统上，你可以看到随着列表大小的增加所花费的时间的差异

所以我建议的解决方案是，从上面添加基于地图的比较

func Elementsmatch(listA, listB []string) (string, bool) {
    aLen := len(listA)
    bLen := len(listB)

    if aLen != bLen {
        return fmt.Sprintf("Len of the lists don't match , len listA %v, len listB %v", aLen, bLen), false
    }

    if aLen > 20 {
        return elementsMatchByMap(listA, listB)
    }else{
        return elementsMatchByLoop(listA, listB)
    }

}

func elementsMatchByLoop(listA, listB []string) (string, bool) {
    aLen := len(listA)
    bLen := len(listB)

    visited := make([]bool, bLen)

    for i := 0; i < aLen; i++ {
        found := false
        element := listA[i]
        for j := 0; j < bLen; j++ {
            if visited[j] {
                continue
            }
            if element == listB[j] {
                visited[j] = true
                found = true
                break
            }
        }
        if !found {
            return fmt.Sprintf("element %s appears more times in %s than in %s", element, listA, listB), false
        }
    }
    return "", true
}

func elementsMatchByMap(x, y []string) (string, bool) {
    // create a map of string -> int
    diff := make(map[string]int, len(x))
    for _, _x := range x {
        // 0 value for int is 0, so just increment a counter for the string
        diff[_x]++
    }
    for _, _y := range y {
        // If the string _y is not in diff bail out early
        if _, ok := diff[_y]; !ok {
            return fmt.Sprintf(" %v is not present in list b", _y), false
        }
        diff[_y] -= 1
        if diff[_y] == 0 {
            delete(diff, _y)
        }
    }
    if len(diff) == 0 {
        return "", true
    }
    return "", false
}

Answer 5

概括 testify ElementsMatch 的代码，比较任何类型对象的解决方案（在示例 []map[string]string 中）：

https://play.golang.org/p/xUS2ngrUWUl

Answer 6

由于我没有足够的声誉来发表评论，我不得不 post 另一个代码可读性更好的答案：

func AssertSameStringSlice(x, y []string) bool {
    if len(x) != len(y) {
        return false
    }

    itemAppearsTimes := make(map[string]int, len(x))
    for _, i := range x {
        itemAppearsTimes[i]++
    }

    for _, i := range y {
        if _, ok := itemAppearsTimes[i]; !ok {
            return false
        }

        itemAppearsTimes[i]--

        if itemAppearsTimes[i] == 0 {
            delete(itemAppearsTimes, i)
        }
    }

    if len(itemAppearsTimes) == 0 {
        return true
    }

    return false
}

逻辑同此

Answer 7

喜欢adrianlzt wrote in his , an implementation of assert.ElementsMatch from testify可以用来实现这一点。但是，当您只需要比较的 bool 结果时，重用实际的 testify 模块而不是复制该代码怎么样？ testify 中的实现用于测试代码，通常采用 testing.T 参数。

事实证明，在测试代码之外可以很容易地使用 ElementsMatch。它所需要的只是一个带有 ErrorF 方法的接口的虚拟实现：

type dummyt struct{}

func (t dummyt) Errorf(string, ...interface{}) {}

func elementsMatch(listA, listB interface{}) bool {
    return assert.ElementsMatch(dummyt{}, listA, listB)
}

或者在我从 adrianlzt 的示例改编而来的 The Go Playground 上进行测试。

Answer 8

您可以将 cmp.Diff 与 cmpopts.SortSlices 一起使用：

less := func(a, b string) bool { return a < b }
equalIgnoreOrder := cmp.Diff(x, y, cmpopts.SortSlices(less)) == ""

这是在 Go Playground:

上运行的完整示例

package main

import (
    "fmt"

    "github.com/google/go-cmp/cmp"
    "github.com/google/go-cmp/cmp/cmpopts"
)

func main() {
    x := []string{"a", "b", "c"}
    y := []string{"a", "c", "b"}
    
    less := func(a, b string) bool { return a < b }
    equalIgnoreOrder := cmp.Diff(x, y, cmpopts.SortSlices(less)) == ""
    fmt.Println(equalIgnoreOrder) // prints "true"

}

无序检查切片是否相等

check for equality on slices without order

equality

go

slice