时间戳

首页 > 解决方案 > 性能：使用排序实现对切片进行排序与​​（切片的）排序类型

sorting - 性能：使用排序实现对切片进行排序与​​（切片的）排序类型

问题描述

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

我做了一些代码来测试我的臀部

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

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

标签： sortinggoslice

解决方案

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

相比之下，当您sort.Interface自己实现类型时，在您的实现中您可以访问切片的静态类型，并且您可以提供sort.Interface不相关的实现，这将使其更快。

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

推荐阅读