I was just playing around with sorting in golang and I found a qsort function on stackoverflow. It seems to run about twice as fast as the native sort function in golang. I've tried it with different input sizes and tested that it works.
Could anyone explain why this happens?
Here is the code you can test it on your pc:
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), " ---")
}
The difference seems to largely be due to the fact that your Quicksort uses builtins. It slices and uses len
. Keep in mind that sort.Sort
takes in a sort.Interface
. So every time you call len
it calls slice.Len
and every time you do array[i],array[j] = array[j],array[i]
it has to call Swap(i,j)
.
I wrote a comparable version that works on an arbitrary 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
}
Then I used Go's benchmark functionality (which you should always use for Benchmarks where possible).
For reference and transparency, qsort.Interface
is defined as:
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)
}
The actual IntSlice
implementation for qsort
is:
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:])
}
Finally, here's the qsort_test.go
file:
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))
}
}
The results (formatting mine):
PASS
BenchmarkQsort 5 513629360 ns/op
BenchmarkNativeQsort 10 160609180 ns/op
BenchmarkSort 5 292416760 ns/op
As you can see, the standard library's sort massively outperforms your qsort on average with random data. NativeQsort
refers to the qsort
functions you posted in your actual question, and it outperforms both. The only thing that's changed between that and Qsort
is that I swapped the builtin functions for qsort.Interface
. It follows, then, that genericity is likely the reason one is slower than the other.
Edit: There aren't many samples because of how expensive sorting is, so here are the results with -benchtime 10s
just for slightly more representative results.
BenchmarkQsort 50 524389994 ns/op
BenchmarkNativeQsort 100 161199217 ns/op
BenchmarkSort 50 302037284 ns/op