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

package main

import (
    "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 []int

func (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_test

import (
    "math/rand"
    "qsort"
    "sort"
    "testing"
    "time"
)

const size int = 1000000

var 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))
    }
}

结果(格式化我的)：

PASS

BenchmarkQsort             5     513629360 ns/op
BenchmarkNativeQsort       10    160609180 ns/op
BenchmarkSort              5     292416760 ns/op

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

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

BenchmarkQsort                50     524389994 ns/op
BenchmarkNativeQsort         100     161199217 ns/op
BenchmarkSort                 50     302037284 ns/op