对切片进行排序：利用排序方法实现切片排序

目前golang学习网上已经有很多关于Golang的文章了，自己在初次阅读这些文章中，也见识到了很多学习思路；那么本文《对切片进行排序：利用排序方法实现切片排序》，也希望能帮助到大家，如果阅读完后真的对你学习Golang有帮助，欢迎动动手指，评论留言并分享~

我正在尝试一些代码挑战，发现自定义排序（排序接口的实现）比仅针对切片的原始结构要快得多。这是为什么？切片到类型的转换是否有一些魔力（例如转换为结构体指针的切片）？

我编写了一些代码来测试我的hipotesis

package sortingexample

import (
    "sort"
    "testing"
)

// example of struct we going to sort.

type point struct {
    x, y int
}

// --- struct / raw data
var testcases = []point{
    {10, 3},
    {10, 4},
    {10, 35},
    {10, 5},
    {10, 51},
    {10, 25},
    {10, 59},
    {10, 15},
    {10, 22},
    {10, 91},
}

// example one - sorting slice directly
// somehow - slowest way to sort it.
func sortslice(points []point) {
    sort.slice(points, func(i, j int) bool {
        return points[i].y < points[j].y
    })
}

func benchmarkslice(b *testing.b) {
    tmp := make([]point, len(testcases))
    for i := 0; i < b.n; i++ {
        copy(tmp, testcases)
        sortslice(tmp)
    }
}

// example two - sorting slice directly
// much faster performance
type points []point

// sort interface implementation
func (p points) less(i, j int) bool { return p[i].y < p[j].y }
func (p points) len() int           { return len(p) }
func (p points) swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func sortstruct(points []point) {
    sort.sort(points(points))
}

func benchmarkstruct(b *testing.b) {
    tmp := make([]point, len(testcases))
    for i := 0; i < b.n; i++ {
        copy(tmp, testcases)
        sortstruct(tmp)
    }
}

// --- pointers
var testcasespoints = []*point{
    &point{10, 3},
    &point{10, 4},
    &point{10, 35},
    &point{10, 5},
    &point{10, 51},
    &point{10, 25},
    &point{10, 59},
    &point{10, 15},
    &point{10, 22},
    &point{10, 91},
}

// example three - sorting slice of pointers

func sortslicepointers(points []*point) {
    sort.slice(points, func(i, j int) bool {
        return points[i].y < points[j].y
    })
}

func benchmarkslicepointers(b *testing.b) {
    tmp := make([]*point, len(testcasespoints))
    for i := 0; i < b.n; i++ {
        copy(tmp, testcasespoints)
        sortslicepointers(tmp)
    }
}

// example four - sorting struct (with slice of pointers beneath it)
type pointspointer []*point

func (pp pointspointer) less(i, j int) bool { return pp[i].y < pp[j].y }
func (pp pointspointer) len() int           { return len(pp) }
func (pp pointspointer) swap(i, j int)      { pp[i], pp[j] = pp[j], pp[i] }

func sortstructofslicepointers(points []*point) {
    sort.sort(pointspointer(points))
}

func benchmarkstructofslicepointers(b *testing.b) {
    tmp := make([]*point, len(testcasespoints))

    for i := 0; i < b.n; i++ {
        copy(tmp, testcasespoints)
        sortstructofslicepointers(tmp)
    }
}

这是结果...

> go test -bench=.
goos: darwin
goarch: amd64
BenchmarkSlice-4                     3000000           542 ns/op
BenchmarkStruct-4                    5000000           318 ns/op
BenchmarkSlicePointers-4             5000000           280 ns/op
BenchmarkStructOfSlicePointers-4     5000000           321 ns/op

很明显，对指针切片进行排序会更快，但为什么自定义排序实现更快呢？我可以阅读有关它的任何资源吗？

解决方案

通用 sort.Slice() 和 sort.SliceStable() 函数适用于任何切片。您必须将切片值作为 interface{} 值传递，并且实现必须使用反射（reflect 包）来访问其元素和长度，并执行元素交换。

相反，当您自己实现 sort.Interface 类型时，在您的实现中您可以访问切片的静态类型，并且您可以提供 sort.interface 的实现而无需反射，这将使其更快。

因此，如果性能至关重要/重要，请始终自行提供 sort.interface 实现。如果切片很小或者性能不重要，您可以使用更方便的 sort.slice() 函数。

通过分配添加运行输出看起来接口/结构方法也更好。

❯ go version
go version go1.17.1 darwin/amd64
❯ go test -bench=. -benchmem
goos: darwin
goarch: amd64
pkg: github.com/timescale/promscale/pkg/api/parser/json/test
cpu: Intel(R) Core(TM) i9-8950HK CPU @ 2.90GHz
BenchmarkSlice-12                        3533616               319.6 ns/op            88 B/op          3 allocs/op
BenchmarkStruct-12                       9157018               126.0 ns/op            24 B/op          1 allocs/op
BenchmarkSlicePointers-12                6643446               167.1 ns/op            56 B/op          2 allocs/op
BenchmarkStructOfSlicePointers-12        9004021               124.1 ns/op            24 B/op          1 allocs/op
PASS
ok      github.com/timescale/promscale/pkg/api/parser/json/test 5.425s

本篇关于《对切片进行排序：利用排序方法实现切片排序》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！