Skip to content

Instantly share code, notes, and snippets.

Created Oct 6, 2011
Embed
What would you like to do?
Slow generic sorting
package slowsort
import (
"reflect"
"sort"
)
func Sort(sl interface{}, less interface{}) {
rsl := reflect.ValueOf(sl)
if rsl.Kind() != reflect.Slice {
panic("first parameter must be a slice")
}
slt := rsl.Type()
lessfn := reflect.ValueOf(less)
if lessfn.Kind() != reflect.Func {
panic("second parameter must be a function")
}
fnt := lessfn.Type()
if fnt.NumIn() != 2 || fnt.NumOut() != 1 {
panic("must be a func(a,b) bool")
}
if fnt.Out(0) != reflect.TypeOf(true) {
panic("return value of less function must be a bool")
}
sorter := &slowSorter{
len: rsl.Len(),
sl: rsl,
lessfn: lessfn,
tmp: reflect.New(slt.Elem()).Elem(),
}
sort.Sort(sorter)
}
type slowSorter struct {
len int
lessfn reflect.Value
sl reflect.Value
tmp reflect.Value
}
func (ss *slowSorter) Len() int {
return ss.len
}
func (ss *slowSorter) Less(i, j int) bool {
iv, jv := ss.sl.Index(i), ss.sl.Index(j)
ret := ss.lessfn.Call([]reflect.Value{iv, jv})
return ret[0].Bool()
}
func (ss *slowSorter) Swap(i, j int) {
iv, jv := ss.sl.Index(i), ss.sl.Index(j)
ss.tmp.Set(jv)
jv.Set(iv)
iv.Set(ss.tmp)
}
package slowsort
import (
"testing"
"reflect"
"sort"
)
func TestInts(t *testing.T) {
x := []int{5, 3, 1, 9}
Sort(x, func(a, b int) bool {
return a < b
})
expected := []int{1, 3, 5, 9}
if !reflect.DeepEqual(expected, x) {
t.Errorf("Expected %v, got %v", expected, x)
}
}
func TestStrings(t *testing.T) {
x := []string{"foo", "bar", "Baz", "botz", "whuz"}
Sort(x, func(a, b string) bool {
return a < b
})
expected := append([]string(nil), x...)
sort.Strings(expected)
if !reflect.DeepEqual(expected, x) {
t.Errorf("Expected %v, got %v", expected, x)
}
}
type mystruct struct {
x int
y int
}
func TestStructs(t *testing.T) {
x := []mystruct{{5, 0}, {3, 0}, {1, 0}, {9, 0}}
Sort(x, func(a, b mystruct) bool {
return a.x < b.x
})
expected := []mystruct{{1, 0}, {3, 0}, {5, 0}, {9, 0}}
if !reflect.DeepEqual(expected, x) {
t.Errorf("Expected %v, got %v", expected, x)
}
}
func TestStructPtrs(t *testing.T) {
x := []*mystruct{&mystruct{5, 0}, &mystruct{3, 0}, &mystruct{1, 0}, &mystruct{9, 0}}
Sort(x, func(a, b *mystruct) bool {
return a.x < b.x
})
expected := []*mystruct{&mystruct{1, 0}, &mystruct{3, 0}, &mystruct{5, 0}, &mystruct{9, 0}}
if !reflect.DeepEqual(expected, x) {
t.Errorf("Expected %v, got %v", expected, x)
}
}
func TestFromMap(t *testing.T) {
m := map[string]int{
"A": 3,
"B": 2,
"C": 1,
"D": 4,
}
var keys []string
for k := range m {
keys = append(keys, k)
}
Sort(keys, func(a, b string) bool {
return m[a] < m[b]
})
expected := []string{"C", "B", "A", "D"}
if !reflect.DeepEqual(expected, keys) {
t.Errorf("TestFromMap: expected %v, got %v", expected, keys)
}
}
var unsorted = []int{-9, 9, 3, 1, 4, 2, 11, 66, 7, 0}
func BenchmarkSlowSort(b *testing.B) {
data := make([]int, len(unsorted))
for i := 0; i < b.N; i++ {
copy(data, unsorted)
Sort(data, func(a, b int) bool {
return a < b
})
}
}
func BenchmarkSlowSortBig(b *testing.B) {
data := make([]int, 2048)
for i := 0; i < b.N; i++ {
for i := range data {
data[i] = i
}
Sort(data, func(a, b int) bool {
return a < b
})
}
}
func BenchmarkSort(b *testing.B) {
data := make([]int, len(unsorted))
for i := 0; i < b.N; i++ {
copy(data, unsorted)
sort.Ints(data)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment