Golang自定义排序比原生排序更快

Question

我刚刚在golang中尝试了排序，发现stackoverflow上有一个qsort函数。它的运行速度似乎比golang本地的sort函数快约两倍。我尝试了不同的输入大小并测试了它的可行性。

有人可以解释一下为什么会这样吗？

以下是你可以在电脑上测试的代码：

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[right] = a[right], 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("--- ", time.Since(start), " ---")

    // Sort using custom qsort
    start = time.Now()
    qsort(array2)

    fmt.Println("Sorting with custom qsort...")
    fmt.Println("--- ", time.Since(start), " ---")

}

- ktsakas

---

内置函数使用qsort吗？qsort可能会更快，但也可能会非常慢（例如，当对已经排序或几乎已经排序的数组进行排序时（这在实践中很常见））。 qsort的最坏情况是O（N ^ 2），但对于许多其他排序来说，它是O（N log N）。请参见[此帖子]（http://www.perlmonks.org/?node_id=1082954）以获取有关Perl中类似实验的信息。 - ikegami

你应该在println之前计算时间差，并打印它，因为println可能会干扰你的时间结果。 - solgar

我现在正在编写一个真正的基准测试来尝试回答这个问题。首先让我感到惊讶的是，sort使用了sort.Interface，因此必须在许多你使用内置函数的地方调用方法。 - Linear

Answer 1

区别很大程度上是因为您的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, right := 0, 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的基准测试功能（在可能的情况下，应始终使用该功能进行基准测试）。

为了参考和透明度，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.Interface。因此，通用性可能是一个函数速度较慢的原因。

编辑：由于排序的开销较大，样本数量并不多，以下是使用-benchtime 10s得到的结果，以使结果更具代表性。

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

- Linear

---

sort.Sort 在我看来不是归并排序的变体，而是快速排序/插入排序的组合。 - Volker

@Volker 是这样吗？我记得文档上说它是归并排序。完全有可能我记错了。 - Linear

@Volker 我一定是疯了。我刚才看了一下源代码，你是对的。我已经在答案中删除了关于归并排序的内容。 - Linear

快速排序。请参见http://tip.golang.org/src/pkg/sort/sort.go?s=4433:4458#L182。稳定排序是通过归并排序完成的。 - Volker

Golang标准库使用Intro sort，这是一种混合排序算法，根据条件从快速排序切换到堆排序。 - Supreet Sethi

Answer 2

它似乎比golang本地的排序函数快两倍左右。

请注意，切片的本地排序将随着Go 1.19（2022年第四季度）的推出而发展。详情请见：

• 问题50154
• CL 399315
• 提交记录72e77a7 by ZhangYunHao。

翻译如下：

排序：使用 pdqsort

• 在所有基准测试中，pdqsort 从未比先前的算法慢。
• 在常见模式中，pdqsort 常常更快（即在已排序的片段中快10倍）。

pdqsort 的描述可参考 Pattern-defeating Quicksort (pdf)，作者为 Orson R. L. Peters。

(摘自)
Pattern-defeating quicksort 通常是小到中等输入大小或数据类型大小的最佳算法选择。
它和其他快速排序变体在无法适应缓存的大型数据集上表现不佳，而 is4o 则表现出色。
然而，后者在较小的数据集上性能不佳，未来的研究可能将这两种算法的优点结合起来。

此 CL 受到 C++ 实现和 Rust 实现的启发。

• C++ 实现
• Rust 实现

- VonC