Golang: Benchmark Radix Tree Lookup

Question

Ich habe versucht, eine Radix Tree-Implementierung zu benchmarken, die ich aus Gründen der Übung mit Golang geschrieben habe.

Aber ich stieß auf ein Problem auf "Wie sollte ich es Benchmark?". In dem unten stehenden Code werden zwei Fälle gezeigt oder sagen wir verschiedene Möglichkeiten, die LookUp-Funktion zu benchmarken.

• Fall 1: eine einzige Scheibe Bytes verwenden, die auf dem Baum existieren bedeutet, dass es erfolgreich LookUp durch alle Kinderknoten etc ...

• Fall 2 sein wird: Verwenden Sie eine func, dass zufällige zu erzeugen Scheibe aus den vorhandenen Daten im Baum bedeutet, dass es auch erfolgreich LookUp sein ...

ich weiß, dass die Zeit aufwenden auf der Baumtiefe abhängen wird ... ich glaube, Fall 2 ist in der Nähe einer realen Welt Implementierung oder nicht?

FRAGE: Welcher Fall ist effizienter oder nützlicher zum 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", 
     ... 
    } 
} 

Ergebnis Fall 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 

Ergebnis Fall 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 

Ergebnisse, wenn es keine Übereinstimmung gibt:

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

Wenn Ihr Benchmark zufällig ist, würde es sehr schwierig sein, die Leistung verschiedener Implementierungen von einem Lauf zum nächsten zu vergleichen.

Stattdessen implementieren Sie statisch einige verschiedene Benchmark-Fälle, die verschiedene Bereiche Ihres Algorithmus betonen. Die Fälle sollten verschiedene Szenarios darstellen, z. B. wenn keine Übereinstimmungen vorhanden sind (wie Sie bereits haben), der Fall, in dem viele Elemente in den Quelldaten enthalten sind, die bei einer Suche zurückgegeben werden, der Fall, in dem viele Elemente vorhanden sind nur 1 Artikel wird zurückgegeben, etc etc.