du4822
2018-09-21 21:44
浏览 201
已采纳

如何在golang中对定长数组进行排序?

I have the following multivariate array:

x := [2][3]int{
    {3, 2, 1},
    {3, 2, 1},
}

Both rows and columns are fixed-size.

I'm trying to check that the rows are sorted, and I undertand the sort function requires arrays without a known size. How can I ask the go to treat the item with a fixed-, known size as if it had an unknown size?

var allTrue bool = true
for i := range x {
  t := sort.Ints(x[i]) == []int{1, 2, 3}
  allTrue = allTrue && t
}

I get:

./main.go:xx:yy: sort.Ints(x[i]) used as value
./main.go:xx:yy: cannot use x[i] (type [3]int) as type []int in argument to sort.Ints

Am I reading this error message correctly?

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • dsgffz2579 2018-09-21 23:10
    已采纳

    Notwithstanding this other answer, which provides guidance regarding appropriate slicing to use the sort package, I have added this answer to provide more description on some further issues with the code you have posted. I hope this aids your understanding of the Go language.


    Introduction to Slices

    I undertand the sort function requires arrays without a known size [sic]

    As others have said, this is not the terminology to describe this concept in Go. All Go arrays are of fixed size, as defined by the language spec. As you know, arrays are of type [N]T for an array which contains some non-negative number N of elements of type T. This is fixed at compile time and never changes during runtime of your program.

    "Arrays without a known size" most closely maps to slices. Slices are distinct types in Go which allow for representation of sequences of data of a particular type, where their length is managed dynamically by the Go runtime. They are of type []T for elements of type T. In particular, their size is not part of their type definition and can change at runtime. For some slice variable x []T, the implementation provides:

    • an internal backing array of similar elemental type, where the implementation manages the allocation of memory and expansion of the array as the slice length increases
    • its length len(x) – denoting the number of elements the slice currently contains
    • its capacity cap(x) – the total length of the slice plus the additional extent of the backing array, which may extend beyond the length due to slicing operations restricting the view on the array or a larger array being allocated by the runtime to allow for appending more items to the slice.

    See the Tour of Go and the language spec on slices for more details.


    Resolving the problem with the code

    As noted above, slices are of distinct type to arrays, so you cannot use something of type [N]T for some N and T where something of type []T is required.

    sort.Ints sorts a slice of integers in-place – it has type signature func Ints(a []int). Your call sort.Ints(x[i]) indexes the array x at index i, which will return an array of type [3]int. This is incompatible with the sort function and leads to the compile-time error you observe.

    To obtain a slice from an array, you use a slice expression. Such expressions allow arrays, slices and some other types to be used to construct new slices.

    Slice expressions are given in the form a[low : high] where low and high are optional integers providing indices into the backing array or slice which specify the range to return in the new slice. The language spec link above has more details which I recommend you read; suffice to say the simplest slice expression a[:] for some array or slice a is syntactic sugar to mean a[0:len(a)-1], i.e. transform the array/slice into a slice of the same length.

    Using this trick, obtain a slice of type []int from your multi-dimensional array by slicing: x[i][:]:

    • x[i] returns an array of type [3]int, as before
    • slicing the returned array returns a slice of type []int, which is compatible with sort.Ints.

    sort.Ints does not return a value, and slices are not comparable

    Even if you fix these issues with your code, there remain two issues with the following line:

    t := sort.Ints(x[i]) == []int{1, 2, 3}
    
    1. sort.Ints sorts in-place; it does not return a value, so the equality test is meaningless.
    2. sort.Ints operates on slices, which are not comparable. It is not possible to call A == B where either A or B is a slice, unless either A or B is the special identifier nil. This is a subtle point which is covered in the language spec. (Aside: read that page, as you will note arrays are comparable.)

    As you cannot compare slices directly using the == equality operator, verifying element-wise equality of slices requires:

    • Slices to be of the same length (dissimilar lengths implies one slice has more elements than the other)
    • Elements at each index of one slice are identical to other slices.

    (I am ignoring the fact that one slice may have a dissimilar capacity to another, as we only care about the element-wise equality.)

    This can be verified by looping through one of the slices and verifying elements at each index correspond at the same index in the other slice. This example code provides an example of that (playground link):

    package main
    
    import (
        "fmt"
    )
    
    func CheckEquality(a, b []int) bool {
        // Slices of dissimilar length are not equal
        if len(a) != len(b) {
            return false
        }
    
        for i, el := range a {
            if b[i] != el {
                return false
            }
        }
    
        return true
    }
    
    func main() {
        var mySlice = []int{1, 2, 3, 4, 5}
        var mySlice2 = []int{1, 2, 3, 4, 5}   // same as mySlice
        var otherSlice = []int{5, 6, 7, 8, 9} // dissimilar slice
        var longSlice = []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
    
        fmt.Println(CheckEquality(mySlice, mySlice2))   // Expect true
        fmt.Println(CheckEquality(mySlice, otherSlice)) // Expect false
        fmt.Println(CheckEquality(mySlice, longSlice))  // Expect false
    }
    
    点赞 评论
  • doubu1853 2018-09-21 22:03

    You have to slice the array with the [:] operator before you can use it with the sort package. See: A Tour of Go: Slices and the "sort" package godoc.

    Also, you can check whether the slice is sorted more efficiently than sorting it, using sort.IntsAreSorted([]int), like this.

    var allTrue bool = true
    for i := range x {
        if !sort.IntsAreSorted(x[i][:]) {
            allTrue = false
            break
        }
    }
    
    点赞 评论
  • dqlxtv1452 2018-09-24 16:33

    You can get a slice from an array by using the [:] operator, e.g.:

    arr := [3]int{1, 2, 3}
    slc := arr[:] // []int{1, 2, 3}, backed by arr
    

    As such, you could use the sort.Ints(...) function:

    sort.Ints(x[0][:])
    sort.Ints(x[1][:])
    // Now both elements of "x" are sorted.
    
    点赞 评论

相关推荐 更多相似问题