doucha5080 2016-05-16 01:43
浏览 39
已采纳

Golang:基准基数树查找

I've been trying to benchmark a Radix Tree implementation I wrote for sake of practice with Golang.

But I encountered a problem on "How should I benchmark it?". In the code below shows two cases or lets say different ways I would like to benchmark the LookUp func.

  • Case 1: Use one single slice of bytes which exist on the tree meaning it will be successful LookUp through all children nodes etc...

  • Case 2: Use a func to generate that random slice from the existing data in the tree meaning it will be successful LookUp as well...

I know the time expend will depend on the tree depth... I think Case 2 is close to a real world implementation or not?

QUESTION: Which case is more efficient or useful to benchmark?

Benchmark:

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",
        ...
    }
}

Result Case 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

Result Case 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

Results when there is no match:

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
  • 写回答

1条回答 默认 最新

  • dsg41888 2016-05-16 06:23
    关注

    If your benchmark is random, that would make it very difficult to compare the performance between different implementations from one run to the next.

    Instead, statically implement a few different benchmark cases that stress different areas of your algorithm. The cases should represent different scenarios, such as the case when there are no matches (as you already have), the case where there are many items in the source data that will be returned in a lookup, the case where there are many items and only 1 item will be returned, etc etc.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面