性能:使用Sort实现对Slice与Sorting Type(Slice)进行排序

Question

我正在玩一些代码挑战,发现自定义排序(排序接口的实现)比单独的切片原始结构更快.这是为什么？切片转换为类型是否做了一些megic(比如转换为指向结构的指针)？

我做了一些代码来测试我的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

很明显,对一片指针进行排序会更快,但为什么自定义排序实现更快？有没有我能读到的资源？

Answer 1

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

相反,当您sort.Interface自己实现该类型时,在您的实现中您可以访问切片的静态类型,并且您可以提供sort.Interface不重复的实现,这将使它更快.

因此,如果性能至关重要/重要,请始终自行提供sort.Interface实施.如果切片很小或性能不重要,您可以使用更方便的sort.Slice()功能.