Golang：基数树查找基准

Question

我一直在尝试对我为使用 Golang 练习而编写的 Radix Tree 实现进行基准测试。但是我在“我应该如何对其进行基准测试？”上遇到了一个问题。在下面的代码中显示了两种情况，或者说我想对 LookUp 函数进行基准测试的不同方式。案例1：使用树上存在的一个字节片，这意味着它将通过所有子节点等成功查找...案例 2：使用 func 从树中的现有数据生成随机切片，这意味着它也将成功查找...我知道时间花费将取决于树的深度......我认为案例 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",        ...    }}结果案例一：PASSBenchmarkLookUp-4       10000000               146 ns/opok      github.com/falmar/goradix       2.068sPASSBenchmarkLookUp-4       10000000               149 ns/opok      github.com/falmar/goradix       2.244s结果案例2：PASSBenchmarkLookUp-4        3000000               546 ns/opok      github.com/falmar/goradix       3.094sPASSBenchmarkLookUp-4        3000000               538 ns/opok      github.com/falmar/goradix       4.481s不匹配时的结果：PASSBenchmarkLookUp-4       10000000               194 ns/opok      github.com/falmar/goradix       3.189sPASSBenchmarkLookUp-4       10000000               191 ns/opok      github.com/falmar/goradix       3.243s

Answer 1

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

相反，静态实现一些不同的基准案例，这些案例强调算法的不同领域。这些案例应该代表不同的场景，例如没有匹配项的情况（就像您已经拥有的那样），源数据中有很多项目将在查找中返回的情况，有很多项目的情况和只有 1 件商品将被退回，等等。