排序 – Golang自定义排序比本机排序更快

概述我只是在golang中进行排序,我在stackoverflow上找到了一个qsort函数.它的运行速度似乎是golang中本机排序函数的两倍.我尝试过不同的输入尺寸并测试它的工作原理. 谁能解释为什么会这样？ 以下是您可以在PC上测试的代码： package mainimport ( "fmt" "math/rand" "sort" "time")func 我只是在golang中进行排序,我在stackoverflow上找到了一个qsort函数.它的运行速度似乎是golang中本机排序函数的两倍.我尝试过不同的输入尺寸并测试它的工作原理.

谁能解释为什么会这样？

以下是您可以在PC上测试的代码：

package mainimport (    "fmt"    "math/rand"    "sort"    "time")func qsort(a []int) []int {    if len(a) < 2 {        return a    }    left,right := 0,len(a)-1    // Pick a pivot    pivotIndex := rand.Int() % len(a)    // Move the pivot to the right    a[pivotIndex],a[right] = a[right],a[pivotIndex]    // Pile elements smaller than the pivot on the left    for i := range a {        if a[i] < a[right] {            a[i],a[left] = a[left],a[i]            left++        }    }    // Place the pivot after the last smaller element    a[left],a[left]    // Go down the rabbit hole    qsort(a[:left])    qsort(a[left+1:])    return a}func main() {    // Create an array with random integers    rand.Seed(30)    size := 1000000    array1 := make([]int,size)    start := time.Now()    for i,_ := range array1 {        array1[i] = rand.Int()    }    fmt.Println("Creating array with ",size," elements...")    fmt.Println("--- ",time.Since(start)," ---")    // Create a copy of the unsorted array    array2 := make([]int,size)    copy(array2,array1)    // Short using native function    start = time.Now()    sort.Ints(array1)    fmt.Println("Sorting with the native sort...")    fmt.Println("--- "," ---")    // Sort using custom qsort    start = time.Now()    qsort(array2)    fmt.Println("Sorting with custom qsort...")    fmt.Println("--- "," ---")}

差异似乎主要是因为您的Quicksort使用内置函数.它切片并使用len.请记住,sort.sort接受sort.Interface.因此,每次调用len时,都会调用slice.Len,每次执行array [i],array [j] = array [j],array [i]时都必须调用Swap(i,j).

我写了一个可比较的版本,适用于任意qsort.Interface：

func Qsort(a Interface,prng *rand.Rand) Interface {    if a.Len() < 2 {        return a    }    left,a.Len()-1    // Pick a pivot    pivotIndex := prng.Int() % a.Len()    // Move the pivot to the right    a.Swap(pivotIndex,right)    // Pile elements smaller than the pivot on the left    for i := 0; i < a.Len(); i++ {        if a.Less(i,right) {            a.Swap(i,left)            left++        }    }    // Place the pivot after the last smaller element    a.Swap(left,right)    // Go down the rabbit hole    leftSIDe,rightSIDe := a.Partition(left)    Qsort(leftSIDe,prng)    Qsort(rightSIDe,prng)    return a}

然后我使用了Go’s benchmark functionality(你应该尽可能使用基准测试).

对于参考和透明度,qsort.Interface定义为：

type Interface interface {    sort.Interface    // Partition returns slice[:i] and slice[i+1:]    // These should references the original memory    // since this does an in-place sort    Partition(i int) (left Interface,right Interface)}

qsort的实际IntSlice实现是：

type IntSlice []intfunc (is IntSlice) Less(i,j int) bool {    return is[i] < is[j]}func (is IntSlice) Swap(i,j int) {    is[i],is[j] = is[j],is[i]}func (is IntSlice) Len() int {    return len(is)}func (is IntSlice) Partition(i int) (left Interface,right Interface) {    return IntSlice(is[:i]),IntSlice(is[i+1:])}

最后,这是qsort_test.go文件：

package qsort_testimport (    "math/rand"    "qsort"    "sort"    "testing"    "time")const size int = 1000000var List = make([]int,size)var prng = rand.New(rand.NewSource(int64(time.Now().Nanosecond())))func BenchmarkQsort(b *testing.B) {    for n := 0; n < b.N; n++ {        b.StopTimer()        for i := range List {            List[i] = prng.Int()        }        b.StartTimer()        qsort.Qsort(qsort.IntSlice(List),prng)    }}func BenchmarkNativeQsort(b *testing.B) {    for n := 0; n < b.N; n++ {        b.StopTimer()        for i := range List {            List[i] = prng.Int()        }        b.StartTimer()        qsort.NativeQsort(List,prng)    }}func BenchmarkSort(b *testing.B) {    for n := 0; n < b.N; n++ {        b.StopTimer()        for i := range List {            List[i] = prng.Int()        }        b.StartTimer()        sort.sort(sort.IntSlice(List))    }}

结果(格式化我的)：

PASSBenchmarkQsort             5     513629360 ns/opBenchmarkNativeQsort       10    160609180 ns/opBenchmarkSort              5     292416760 ns/op

正如您所看到的,标准库的排序在随机数据上平均优于您的qsort. NativeQsort是指您在实际问题中发布的qsort函数,它优于两者.在Qsort和Qsort之间唯一改变的是我交换了qsort.Interface的内置函数.因此,通用性可能是一个比另一个慢的原因.

编辑：由于排序的成本很高,所以样本数量不多,所以这里的结果是-benchtime 10s只是为了更具代表性的结果.

BenchmarkQsort                50     524389994 ns/opBenchmarkNativeQsort         100     161199217 ns/opBenchmarkSort                 50     302037284 ns/op

总结

以上是内存溢出为你收集整理的排序 – Golang自定义排序比本机排序更快全部内容，希望文章能够帮你解决排序 – Golang自定义排序比本机排序更快所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。