go - Go 中 slice 排序的意外基准测试结果

Question

我刚开始学习 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)
}

Answer 1

观察到的效果与您的排序代码、 slice 或其他任何东西无关。您根本没有正确使用 b testing.B:您应该执行代码 b.N 次。

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