0
我剛開始學習golang並決定實施一些基本的排序算法(冒泡排序,選擇排序和插入排序),以嘗試使用包,切片和測試基礎結構進行工作。Go中片段排序的意外基準測試結果
這裏的實現:
package child_sort
func SortBubble(xs []int) {
for i := range xs {
swapped := false
for j := 1; j < len(xs)-i; j++ {
if xs[j-1] > xs[j] {
xs[j-1], xs[j] = xs[j], xs[j-1]
swapped = true
}
}
if !swapped {
break
}
}
}
func SortSelection(xs []int) {
for i := range xs {
min_i := i
for j := i + 1; j < len(xs); j++ {
if xs[j] < xs[min_i] {
min_i = j
}
}
if min_i != i {
xs[i], xs[min_i] = xs[min_i], xs[i]
}
}
}
func SortInsertion(xs []int) {
for i := 1; i < len(xs); i++ {
for j := i; j > 0; j-- {
if xs[j] < xs[j-1] {
xs[j], xs[j-1] = xs[j-1], xs[j]
}
}
}
}
單元測試似乎很好地工作,但是當我創建基準這些,我得到了奇怪的結果,像這樣的:
go test --bench . --benchmem
PASS
BenchmarkBubble 1 2258469081 ns/op 241664 B/op 1 allocs/op
BenchmarkSelection 1000000000 0.60 ns/op 0 B/op 0 allocs/op
BenchmarkInsertion 1 1180026827 ns/op 241664 B/op 1 allocs/op
ok .../go/src/child_sort 12.976s
我是什麼臭蟲選擇排序幾乎立即運行併產生零分配。如果我減小數組的大小,其他排序算法也會發生同樣的情況。而事實恰恰相反,即如果我增加規模,選擇排序就會開始行爲健全。
這裏的測試文件:
package child_sort
import (
"math/rand"
"testing"
"time"
)
func generate(size int, min, max int) []int {
rand.Seed(time.Now().UTC().UnixNano())
var xs = make([]int, size, size)
for i := range xs {
xs[i] = min + rand.Intn(max-min)
}
return xs
}
func TestSortBubble(t *testing.T) {
xs := []int{9, 8, 7, 6, 5}
ys := []int{5, 6, 7, 8, 9}
SortBubble(xs)
for i, v := range xs {
if v != ys[i] {
t.Errorf("fail")
}
}
}
func TestSortSelection(t *testing.T) {
xs := []int{1, 2, 9, 6, 2}
ys := []int{1, 2, 2, 6, 9}
SortSelection(xs)
for i, v := range xs {
if v != ys[i] {
t.Errorf("fail")
}
}
}
func TestSortInsertion(t *testing.T) {
xs := []int{1, 2, 9, 6, 2}
ys := []int{1, 2, 2, 6, 9}
SortInsertion(xs)
for i, v := range xs {
if v != ys[i] {
t.Errorf("fail")
}
}
}
func BenchmarkBubble(b *testing.B) {
xs := generate(10000, -100, 100)
/* b.ResetTimer() */
SortBubble(xs)
}
func BenchmarkSelection(b *testing.B) {
xs := generate(10000, -100, 100)
/* b.ResetTimer() */
SortSelection(xs)
}
func BenchmarkInsertion(b *testing.B) {
xs := generate(10000, -100, 100)
/* b.ResetTimer() */
SortInsertion(xs)
}