我刚开始学习 golang，并决定实现一些基本的排序算法(冒泡排序、选择排序和插入排序)来尝试使用包、 slice 和测试基础设施。
实现如下:
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)
}
最佳答案
观察到的效果与您的排序代码、 slice 或其他任何东西无关。您根本没有正确使用 b testing.B:您应该执行代码 b.N 次。
看看标准排序包如何进行基准测试:http://golang.org/src/pkg/sort/sort_test.go
关于go - Go 中 slice 排序的意外基准测试结果，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22500407/