Go中切片排序的意外基准测试结果

Question

我刚开始学习golang，并决定实现一些基本的排序算法(气泡排序、选择排序和插入排序)来尝试处理包、片和测试基础设施。

实现如下:

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)
}

Answer 1

观察到的效果与排序代码、切片等无关。你只是没有正确地使用b testing.B:你应该执行你的代码b.N次。

看看标准排序包是如何进行基准测试的:http://golang.org/src/pkg/sort/sort_test.go