sorting - 性能 : Sorting Slice vs Sorting Type (of Slice) with Sort implementation

Question

我在玩一些代码挑战时发现自定义排序(排序接口(interface)的实现)比仅针对 slice 的原始结构要快得多。这是为什么？将 slice 转换为类型是否会产生一些魔力(例如转换为指向结构的指针 slice )？

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

很明显，对指针 slice 进行排序会更快，但为什么自定义排序实现会更快？是否有任何我可以阅读的资源？

Answer 1

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

相比之下，当您实现 sort.Interface键入自己，在您的实现中您可以访问 slice 的静态类型，并且您可以提供 sort.Interface 的实现而无需 refection，这将使它更快。

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