Skip to content

Instantly share code, notes, and snippets.

@icub3d
Created December 4, 2013 19:59
Show Gist options
  • Save icub3d/7794453 to your computer and use it in GitHub Desktop.
Save icub3d/7794453 to your computer and use it in GitHub Desktop.
Interface Performance
package mysort
func min(a, b int) int {
if a < b {
return a
}
return b
}
func insertionSort(data []int, a, b int) {
for i := a + 1; i < b; i++ {
for j := i; j > a && (data[j] < data[j-1]); j-- {
data[j], data[j-1] = data[j-1], data[j]
}
}
}
func siftDown(data []int, lo, hi, first int) {
root := lo
for {
child := 2*root + 1
if child >= hi {
break
}
if child+1 < hi && (data[first+child] < data[first+child+1]) {
child++
}
if !(data[first+root] < data[first+child]) {
return
}
data[first+root], data[first+child] = data[first+child], data[first+root]
root = child
}
}
func heapSort(data []int, a, b int) {
first := a
lo := 0
hi := b - a
for i := (hi - 1) / 2; i >= 0; i-- {
siftDown(data, i, hi, first)
}
for i := hi - 1; i >= 0; i-- {
data[first], data[first+i] = data[first+i], data[first]
siftDown(data, lo, i, first)
}
}
func medianOfThree(data []int, a, b, c int) {
m0 := b
m1 := a
m2 := c
if data[m1] < data[m0] {
data[m1], data[m0] = data[m0], data[m1]
}
if data[m2] < data[m1] {
data[m2], data[m1] = data[m1], data[m2]
}
if data[m1] < data[m0] {
data[m1], data[m0] = data[m0], data[m1]
}
}
func swapRange(data []int, a, b, n int) {
for i := 0; i < n; i++ {
data[a+i], data[b+i] = data[b+i], data[a+i]
}
}
func doPivot(data []int, lo, hi int) (midlo, midhi int) {
m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
if hi-lo > 40 {
s := (hi - lo) / 8
medianOfThree(data, lo, lo+s, lo+2*s)
medianOfThree(data, m, m-s, m+s)
medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
}
medianOfThree(data, lo, m, hi-1)
pivot := lo
a, b, c, d := lo+1, lo+1, hi, hi
for {
for b < c {
if data[b] < data[pivot] { // data[b] < pivot
b++
} else if !(data[pivot] < data[b]) { // data[b] = pivot
data[a], data[b] = data[b], data[a]
a++
b++
} else {
break
}
}
for b < c {
if data[pivot] < data[c-1] { // data[c-1] > pivot
c--
} else if !(data[c-1] < data[pivot]) { // data[c-1] = pivot
data[c-1], data[d-1] = data[d-1], data[c-1]
c--
d--
} else {
break
}
}
if b >= c {
break
}
data[b], data[c-1] = data[c-1], data[b]
b++
c--
}
n := min(b-a, a-lo)
swapRange(data, lo, b-n, n)
n = min(hi-d, d-c)
swapRange(data, c, hi-n, n)
return lo + b - a, hi - (d - c)
}
func quickSort(data []int, a, b, maxDepth int) {
for b-a > 7 {
if maxDepth == 0 {
heapSort(data, a, b)
return
}
maxDepth--
mlo, mhi := doPivot(data, a, b)
if mlo-a < b-mhi {
quickSort(data, a, mlo, maxDepth)
a = mhi // i.e., quickSort(data, mhi, b)
} else {
quickSort(data, mhi, b, maxDepth)
b = mlo // i.e., quickSort(data, a, mlo)
}
}
if b-a > 1 {
insertionSort(data, a, b)
}
}
func MyIntSort(data []int) {
n := len(data)
maxDepth := 0
for i := n; i > 0; i >>= 1 {
maxDepth++
}
maxDepth *= 2
quickSort(data, 0, n, maxDepth)
}
package mysort
func insertionSortFunc(data []int, a, b int) {
for i := a + 1; i < b; i++ {
for j := i; j > a && Less(data, j, j-1); j-- {
Swap(data, j, j-1)
}
}
}
func siftDownFunc(data []int, lo, hi, first int) {
root := lo
for {
child := 2*root + 1
if child >= hi {
break
}
if child+1 < hi && Less(data, first+child, first+child+1) {
child++
}
if !Less(data, first+root, first+child) {
return
}
Swap(data, first+root, first+child)
root = child
}
}
func heapSortFunc(data []int, a, b int) {
first := a
lo := 0
hi := b - a
for i := (hi - 1) / 2; i >= 0; i-- {
siftDownFunc(data, i, hi, first)
}
for i := hi - 1; i >= 0; i-- {
Swap(data, first, first+i)
siftDownFunc(data, lo, i, first)
}
}
func medianOfThreeFunc(data []int, a, b, c int) {
m0 := b
m1 := a
m2 := c
if Less(data, m1, m0) {
Swap(data, m1, m0)
}
if Less(data, m2, m1) {
Swap(data, m2, m1)
}
if Less(data, m1, m0) {
Swap(data, m1, m0)
}
}
func swapRangeFunc(data []int, a, b, n int) {
for i := 0; i < n; i++ {
Swap(data, a+i, b+i)
}
}
func doPivotFunc(data []int, lo, hi int) (midlo, midhi int) {
m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
if hi-lo > 40 {
s := (hi - lo) / 8
medianOfThreeFunc(data, lo, lo+s, lo+2*s)
medianOfThreeFunc(data, m, m-s, m+s)
medianOfThreeFunc(data, hi-1, hi-1-s, hi-1-2*s)
}
medianOfThreeFunc(data, lo, m, hi-1)
pivot := lo
a, b, c, d := lo+1, lo+1, hi, hi
for {
for b < c {
if Less(data, b, pivot) { // data[b] < pivot
b++
} else if !Less(data, pivot, b) { // data[b] = pivot
Swap(data, a, b)
a++
b++
} else {
break
}
}
for b < c {
if Less(data, pivot, c-1) { // data[c-1] > pivot
c--
} else if !Less(data, c-1, pivot) { // data[c-1] = pivot
Swap(data, c-1, d-1)
c--
d--
} else {
break
}
}
if b >= c {
break
}
Swap(data, b, c-1)
b++
c--
}
n := min(b-a, a-lo)
swapRangeFunc(data, lo, b-n, n)
n = min(hi-d, d-c)
swapRangeFunc(data, c, hi-n, n)
return lo + b - a, hi - (d - c)
}
func quickSortFunc(data []int, a, b, maxDepth int) {
for b-a > 7 {
if maxDepth == 0 {
heapSortFunc(data, a, b)
return
}
maxDepth--
mlo, mhi := doPivotFunc(data, a, b)
if mlo-a < b-mhi {
quickSortFunc(data, a, mlo, maxDepth)
a = mhi // i.e., quickSort(data, mhi, b)
} else {
quickSortFunc(data, mhi, b, maxDepth)
b = mlo // i.e., quickSort(data, a, mlo)
}
}
if b-a > 1 {
insertionSortFunc(data, a, b)
}
}
func MyIntSortFunc(data []int) {
n := Len(data)
maxDepth := 0
for i := n; i > 0; i >>= 1 {
maxDepth++
}
maxDepth *= 2
quickSortFunc(data, 0, n, maxDepth)
}
func Len(data []int) int {
return len(data)
}
func Less(data []int, i, j int) bool {
return data[i] < data[j]
}
func Swap(data []int, i, j int) {
data[i], data[j] = data[j], data[i]
}
package mysort
type IntSlicePtr struct {
data []int
}
func (is *IntSlicePtr) Len() int {
return len(is.data)
}
func (is *IntSlicePtr) Less(i, j int) bool {
return is.data[i] < is.data[j]
}
func (is *IntSlicePtr) Swap(i, j int) {
is.data[i], is.data[j] = is.data[j], is.data[i]
}
func insertionSortPtr(data *IntSlicePtr, a, b int) {
for i := a + 1; i < b; i++ {
for j := i; j > a && data.Less(j, j-1); j-- {
data.Swap(j, j-1)
}
}
}
func siftDownPtr(data *IntSlicePtr, lo, hi, first int) {
root := lo
for {
child := 2*root + 1
if child >= hi {
break
}
if child+1 < hi && data.Less(first+child, first+child+1) {
child++
}
if !data.Less(first+root, first+child) {
return
}
data.Swap(first+root, first+child)
root = child
}
}
func heapSortPtr(data *IntSlicePtr, a, b int) {
first := a
lo := 0
hi := b - a
for i := (hi - 1) / 2; i >= 0; i-- {
siftDownPtr(data, i, hi, first)
}
for i := hi - 1; i >= 0; i-- {
data.Swap(first, first+i)
siftDownPtr(data, lo, i, first)
}
}
func medianOfThreePtr(data *IntSlicePtr, a, b, c int) {
m0 := b
m1 := a
m2 := c
if data.Less(m1, m0) {
data.Swap(m1, m0)
}
if data.Less(m2, m1) {
data.Swap(m2, m1)
}
if data.Less(m1, m0) {
data.Swap(m1, m0)
}
}
func swapRangePtr(data *IntSlicePtr, a, b, n int) {
for i := 0; i < n; i++ {
data.Swap(a+i, b+i)
}
}
func doPivotPtr(data *IntSlicePtr, lo, hi int) (midlo, midhi int) {
m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
if hi-lo > 40 {
s := (hi - lo) / 8
medianOfThreePtr(data, lo, lo+s, lo+2*s)
medianOfThreePtr(data, m, m-s, m+s)
medianOfThreePtr(data, hi-1, hi-1-s, hi-1-2*s)
}
medianOfThreePtr(data, lo, m, hi-1)
pivot := lo
a, b, c, d := lo+1, lo+1, hi, hi
for {
for b < c {
if data.Less(b, pivot) { // data[b] < pivot
b++
} else if !data.Less(pivot, b) { // data[b] = pivot
data.Swap(a, b)
a++
b++
} else {
break
}
}
for b < c {
if data.Less(pivot, c-1) { // data[c-1] > pivot
c--
} else if !data.Less(c-1, pivot) { // data[c-1] = pivot
data.Swap(c-1, d-1)
c--
d--
} else {
break
}
}
if b >= c {
break
}
data.Swap(b, c-1)
b++
c--
}
n := min(b-a, a-lo)
swapRangePtr(data, lo, b-n, n)
n = min(hi-d, d-c)
swapRangePtr(data, c, hi-n, n)
return lo + b - a, hi - (d - c)
}
func quickSortPtr(data *IntSlicePtr, a, b, maxDepth int) {
for b-a > 7 {
if maxDepth == 0 {
heapSortPtr(data, a, b)
return
}
maxDepth--
mlo, mhi := doPivotPtr(data, a, b)
if mlo-a < b-mhi {
quickSortPtr(data, a, mlo, maxDepth)
a = mhi // i.e., quickSort(data, mhi, b)
} else {
quickSortPtr(data, mhi, b, maxDepth)
b = mlo // i.e., quickSort(data, a, mlo)
}
}
if b-a > 1 {
insertionSortPtr(data, a, b)
}
}
func MyIntSortPtr(data *IntSlicePtr) {
n := data.Len()
maxDepth := 0
for i := n; i > 0; i >>= 1 {
maxDepth++
}
maxDepth *= 2
quickSortPtr(data, 0, n, maxDepth)
}
package mysort
type IntSlice struct {
data []int
}
func (is IntSlice) Len() int {
return len(is.data)
}
func (is IntSlice) Less(i, j int) bool {
return is.data[i] < is.data[j]
}
func (is IntSlice) Swap(i, j int) {
is.data[i], is.data[j] = is.data[j], is.data[i]
}
func insertionSortStruct(data IntSlice, a, b int) {
for i := a + 1; i < b; i++ {
for j := i; j > a && data.Less(j, j-1); j-- {
data.Swap(j, j-1)
}
}
}
func siftDownStruct(data IntSlice, lo, hi, first int) {
root := lo
for {
child := 2*root + 1
if child >= hi {
break
}
if child+1 < hi && data.Less(first+child, first+child+1) {
child++
}
if !data.Less(first+root, first+child) {
return
}
data.Swap(first+root, first+child)
root = child
}
}
func heapSortStruct(data IntSlice, a, b int) {
first := a
lo := 0
hi := b - a
for i := (hi - 1) / 2; i >= 0; i-- {
siftDownStruct(data, i, hi, first)
}
for i := hi - 1; i >= 0; i-- {
data.Swap(first, first+i)
siftDownStruct(data, lo, i, first)
}
}
func medianOfThreeStruct(data IntSlice, a, b, c int) {
m0 := b
m1 := a
m2 := c
if data.Less(m1, m0) {
data.Swap(m1, m0)
}
if data.Less(m2, m1) {
data.Swap(m2, m1)
}
if data.Less(m1, m0) {
data.Swap(m1, m0)
}
}
func swapRangeStruct(data IntSlice, a, b, n int) {
for i := 0; i < n; i++ {
data.Swap(a+i, b+i)
}
}
func doPivotStruct(data IntSlice, lo, hi int) (midlo, midhi int) {
m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
if hi-lo > 40 {
s := (hi - lo) / 8
medianOfThreeStruct(data, lo, lo+s, lo+2*s)
medianOfThreeStruct(data, m, m-s, m+s)
medianOfThreeStruct(data, hi-1, hi-1-s, hi-1-2*s)
}
medianOfThreeStruct(data, lo, m, hi-1)
pivot := lo
a, b, c, d := lo+1, lo+1, hi, hi
for {
for b < c {
if data.Less(b, pivot) { // data[b] < pivot
b++
} else if !data.Less(pivot, b) { // data[b] = pivot
data.Swap(a, b)
a++
b++
} else {
break
}
}
for b < c {
if data.Less(pivot, c-1) { // data[c-1] > pivot
c--
} else if !data.Less(c-1, pivot) { // data[c-1] = pivot
data.Swap(c-1, d-1)
c--
d--
} else {
break
}
}
if b >= c {
break
}
data.Swap(b, c-1)
b++
c--
}
n := min(b-a, a-lo)
swapRangeStruct(data, lo, b-n, n)
n = min(hi-d, d-c)
swapRangeStruct(data, c, hi-n, n)
return lo + b - a, hi - (d - c)
}
func quickSortStruct(data IntSlice, a, b, maxDepth int) {
for b-a > 7 {
if maxDepth == 0 {
heapSortStruct(data, a, b)
return
}
maxDepth--
mlo, mhi := doPivotStruct(data, a, b)
if mlo-a < b-mhi {
quickSortStruct(data, a, mlo, maxDepth)
a = mhi // i.e., quickSort(data, mhi, b)
} else {
quickSortStruct(data, mhi, b, maxDepth)
b = mlo // i.e., quickSort(data, a, mlo)
}
}
if b-a > 1 {
insertionSortStruct(data, a, b)
}
}
func MyIntSortStruct(data IntSlice) {
n := data.Len()
maxDepth := 0
for i := n; i > 0; i >>= 1 {
maxDepth++
}
maxDepth *= 2
quickSortStruct(data, 0, n, maxDepth)
}
package mysort
import (
"sort"
"testing"
)
var ints = [...]int{
74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586,
}
func TestMyIntSort(t *testing.T) {
data := ints
a := data[0:]
MyIntSort(a)
if !sort.IsSorted(sort.IntSlice(a)) {
t.Errorf("sorted %v", ints)
t.Errorf(" got %v", data)
}
}
func TestMyIntSortFunc(t *testing.T) {
data := ints
a := data[0:]
MyIntSortFunc(a)
if !sort.IsSorted(sort.IntSlice(a)) {
t.Errorf("sorted %v", ints)
t.Errorf(" got %v", data)
}
}
func TestMyIntSortStruct(t *testing.T) {
data := ints
a := data[0:]
MyIntSortStruct(IntSlice{a})
if !sort.IsSorted(sort.IntSlice(a)) {
t.Errorf("sorted %v", ints)
t.Errorf(" got %v", data)
}
}
func TestMyIntSortPtr(t *testing.T) {
data := ints
a := data[0:]
MyIntSortPtr(&IntSlicePtr{a})
if !sort.IsSorted(sort.IntSlice(a)) {
t.Errorf("sorted %v", ints)
t.Errorf(" got %v", data)
}
}
func BenchmarkSortInt1K(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
data := make([]int, 1<<10)
for i := 0; i < len(data); i++ {
data[i] = i ^ 0x2cc
}
d := sort.IntSlice(data)
b.StartTimer()
sort.Sort(d)
b.StopTimer()
}
}
func BenchmarkMyIntSort1K(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
data := make([]int, 1<<10)
for i := 0; i < len(data); i++ {
data[i] = i ^ 0x2cc
}
b.StartTimer()
MyIntSort(data)
b.StopTimer()
}
}
func BenchmarkMyIntSortFunc1K(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
data := make([]int, 1<<10)
for i := 0; i < len(data); i++ {
data[i] = i ^ 0x2cc
}
b.StartTimer()
MyIntSortFunc(data)
b.StopTimer()
}
}
func BenchmarkMyIntSortStruct1k(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
data := make([]int, 1<<10)
for i := 0; i < len(data); i++ {
data[i] = i ^ 0x2cc
}
d := IntSlice{data}
b.StartTimer()
MyIntSortStruct(d)
b.StopTimer()
}
}
func BenchmarkMyIntSortPtr1k(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
data := make([]int, 1<<10)
for i := 0; i < len(data); i++ {
data[i] = i ^ 0x2cc
}
d := &IntSlicePtr{data}
b.StartTimer()
MyIntSortPtr(d)
b.StopTimer()
}
}
$ go test -bench .
PASS
BenchmarkSortInt1K-8 10000 150809 ns/op
BenchmarkMyIntSort1K-8 50000 34777 ns/op
BenchmarkMyIntSortFunc1K-8 50000 51170 ns/op
BenchmarkMyIntSortStruct1k-8 10000 143204 ns/op
BenchmarkMyIntSortPtr1k-8 50000 56585 ns/op
ok _/home/jmarsh/sort_test/mysort 13.993s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment