为什么我的红黑树实现基准测试显示线性时间复杂度？

Question

这是我实现基准测试的方法，在本例中，它是基准测试Put操作：

func BenchmarkRBTree(b *testing.B) {

    for size := 0; size < 1000; size += 100 {

        b.Run(fmt.Sprintf("size-%d", size), func(b *testing.B) {

            tree := NewRBTree(func(a, b interface{}) bool {

                if a.(int) < b.(int) {

                    return true

                }

                return false

            })

            for i := 0; i < b.N; i++ {

                for n := 0; n < size; n++ {

                    tree.Put(n, n)

                }

            }

        })

    }

}

基准测试结果：

BenchmarkRBTree/size-0-8              2000000000              0.49 ns/op               0 B/op          0 allocs/op

BenchmarkRBTree/size-100-8                200000             11170 ns/op            7984 B/op        298 allocs/op

BenchmarkRBTree/size-200-8                100000             26450 ns/op           15984 B/op        598 allocs/op

BenchmarkRBTree/size-300-8                 50000             38838 ns/op           23984 B/op        898 allocs/op

BenchmarkRBTree/size-400-8                 30000             55460 ns/op           31984 B/op       1198 allocs/op

BenchmarkRBTree/size-500-8                 20000             62654 ns/op           39984 B/op       1498 allocs/op

BenchmarkRBTree/size-600-8                 20000             80317 ns/op           47984 B/op       1798 allocs/op

BenchmarkRBTree/size-700-8                 20000             91308 ns/op           55984 B/op       2098 allocs/op

BenchmarkRBTree/size-800-8                 10000            106180 ns/op           63984 B/op       2398 allocs/op

BenchmarkRBTree/size-900-8                 10000            121026 ns/op           71984 B/op       2698 allocs/op

视觉折线图ns/op：

Answer 1

基准测试执行错误，正确版本：func BenchmarkRBTree_Put(b *testing.B) {&nbsp; &nbsp; count := 0&nbsp; &nbsp; grow := 1&nbsp; &nbsp; for size := 0; size < 100000; size += 1 * grow {&nbsp; &nbsp; &nbsp; &nbsp; if count%10 == 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count = 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; grow *= 10&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; b.Run(fmt.Sprintf("size-%d", size), func(b *testing.B) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // prepare problem size&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tree := NewRBTree(func(a, b interface{}) bool {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if a.(int) < b.(int) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; })&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for n := 0; n < size-1; n++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tree.Put(n, n)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b.ResetTimer()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for i := 0; i < b.N; i++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tree.Put(size, size) // only measure the last operation&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; })&nbsp; &nbsp; &nbsp; &nbsp; count++&nbsp; &nbsp; }}