Skip to content

Instantly share code, notes, and snippets.

@donovanhide
Last active December 11, 2015 01:29
Show Gist options
  • Save donovanhide/4524254 to your computer and use it in GitHub Desktop.
Save donovanhide/4524254 to your computer and use it in GitHub Desktop.
Test to see if copy and pasted sort routine is faster than sort.Sort using interfaces
go test -bench=.*
testing: warning: no tests to run
PASS
BenchmarkSort 5000000 707 ns/op
BenchmarkShellSort 5000000 603 ns/op
package main
import (
"math/rand"
"sort"
"testing"
)
type Inverted struct {
Hash uint32
Position int
}
type InvertedSlice []Inverted
func (s *InvertedSlice) Len() int { return len(*s) }
func (s *InvertedSlice) Swap(i, j int) { (*s)[i], (*s)[j] = (*s)[j], (*s)[i] }
func (s *InvertedSlice) Less(i, j int) bool {
return (*s)[i].Hash < (*s)[j].Hash || ((*s)[i].Hash == (*s)[j].Hash && (*s)[i].Position < (*s)[j].Position)
}
func Greater(l, r Inverted) bool {
return l.Hash > r.Hash || (l.Hash == r.Hash && l.Position > r.Position)
}
func (s InvertedSlice) ShellSort() {
for inc := len(s) / 2; inc > 0; inc = (inc + 1) * 5 / 11 {
for i := inc; i < len(s); i++ {
j, temp := i, s[i]
for ; j >= inc && Greater(s[j-inc], temp); j -= inc {
s[j] = s[j-inc]
}
s[j] = temp
}
}
}
func buildData(n int) InvertedSlice {
rand.Seed(12345)
s := make(InvertedSlice, n)
for i := 0; i < n; i++ {
s[i] = Inverted{rand.Uint32(), n - i}
}
return s
}
func BenchmarkSort(b *testing.B) {
data := buildData(b.N)
b.ResetTimer()
sort.Sort(&data)
}
func BenchmarkShellSort(b *testing.B) {
data := buildData(b.N)
b.ResetTimer()
data.ShellSort()
b.StopTimer()
if !sort.IsSorted(&data) {
b.Error("Bad shellsort!")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment