Golang:基准根树查找

Question

我一直在尝试对我为练习Golang而编写的Radix Tree实现进行基准测试。

但我遇到了一个问题，"我应该如何对它进行基准测试？"。在下面的代码中，显示了两种情况，或者说我想用不同的方式对LookUp函数进行基准测试。

• 案例1：使用树上存在的一个字节片，这意味着它将通过所有子节点等成功查找…

• 案例2：使用func从树中的现有数据生成随机切片，这意味着它也将是成功的LookUp。。。

我知道花费的时间将取决于树的深度。。。我认为案例2是否接近真实世界的实现？

问题：哪种情况对基准测试更有效或更有用？

基准：

func BenchmarkLookUp(b *testing.B) {
    radix := New()
    insertData(radix, sampleData2)
    textToLookUp := randomBytes()
    for i := 0; i < b.N; i++ {
        radix.LookUp(textToLookUp) // Case 1 
        //radix.LookUp(randomBytes()) // Case 2
    }
}
func randomBytes() []byte {
    strings := sampleData2()
    return []byte(strings[random(0, len(strings))])
}
func sampleData2() []string {
    return []string{
        "romane",
        "romanus",
        "romulus",
        ...
    }
}

结果案例1:

PASS
BenchmarkLookUp-4       10000000               146 ns/op
ok      github.com/falmar/goradix       2.068s
PASS
BenchmarkLookUp-4       10000000               149 ns/op
ok      github.com/falmar/goradix       2.244s

结果案例2：

PASS
BenchmarkLookUp-4        3000000               546 ns/op
ok      github.com/falmar/goradix       3.094s
PASS
BenchmarkLookUp-4        3000000               538 ns/op
ok      github.com/falmar/goradix       4.481s

不匹配时的结果：

PASS
BenchmarkLookUp-4       10000000               194 ns/op
ok      github.com/falmar/goradix       3.189s
PASS
BenchmarkLookUp-4       10000000               191 ns/op
ok      github.com/falmar/goradix       3.243s

Answer 1

如果您的基准测试是随机的，那么从一次运行到下一次运行，将很难比较不同实现之间的性能。

相反，静态地实现几个不同的基准案例，这些案例强调了算法的不同领域。案例应该代表不同的场景，例如没有匹配的情况（正如您已经拥有的），源数据中有许多项目将在查找中返回的情况，有许多项目但只返回一个项目的情况，等等。