Golang：基準基數樹查找

我一直在嘗試使用Golang爲實踐而寫的基數樹實現進行基準測試。Golang：基準基數樹查找

但是我遇到了一個問題，「我應該如何對它進行基準測試？」。在下面的代碼中顯示了兩種情況，或者說我想用不同的方式來對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", 
     ... 
    } 
}

結果案例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

來源

2016-05-16 David Lavieri

如果您的基準測試是隨機的，那麼很難比較一次運行和另一次運行的不同實現之間的性能。

相反，靜態執行幾個不同的基準情況，強調算法的不同區域。這些情況應該表示不同的情況，例如沒有匹配的情況（如你已經有的情況），源數據中有很多項目將在查找中返回，這種情況下有很多項目和只返回1個項目等等

來源

2016-05-16 06:23:08 ctcherry

返回的項目不多，只返回'（node，error）'，如果匹配'（node，nil）'否則'（nil，error）'。爲了使用像一個httprouter，我會做一個自動完成func或其他lookups func –

我從來沒有使用過golang，但至少在C++/Java中，隨機生成器可以被'植入'一個常量（'0'在上面的代碼？），這使測試可重複。 – TilmannZ

Golang：基準基數樹查找

回答

相關問題