algorithm - Golang:基准基数树查找

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

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

情况1:使用树上存在的单个 byte slice 意味着通过所有子节点等将成功执行Lookup ...

情况2:使用func从树中的现有数据生成随机 slice ，这意味着它也将成功执行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

最佳答案

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

取而代之的是，静态实现一些不同的基准测试案例，这些案例会强调算法的不同领域。这些案例应该代表不同的场景，例如没有匹配项的情况(如您已经拥有的情况)，源数据中有很多项目将在查找中返回的情况，有很多项目且仅退回一件商品，依此类推。

关于algorithm - Golang:基准基数树查找，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37245579/