graph/path: clean up AStar benchmarks with subtests
MODIFY
graph/path/bench_test.go
graph/path/bench_test.go
@@ -19,6 +19,11 @@ var (
gnpUndirected_10_half = gnpUndirected(10, 0.5)
gnpUndirected_100_half = gnpUndirected(100, 0.5)
gnpUndirected_1000_half = gnpUndirected(1000, 0.5)
+
+ nswUndirected_10_2_2_2 = navigableSmallWorldUndirected(10, 2, 2, 2)
+ nswUndirected_10_2_5_2 = navigableSmallWorldUndirected(10, 2, 5, 2)
+ nswUndirected_100_5_10_2 = navigableSmallWorldUndirected(100, 5, 10, 2)
+ nswUndirected_100_5_20_2 = navigableSmallWorldUndirected(100, 5, 20, 2)
)
func gnpUndirected(n int, p float64) graph.Undirected {
@@ -27,48 +32,18 @@ func gnpUndirected(n int, p float64) graph.Undirected {
return g
}
-func benchmarkAStarNilHeuristic(b *testing.B, g graph.Undirected) {
- var expanded int
- for i := 0; i < b.N; i++ {
- _, expanded = AStar(simple.Node(0), simple.Node(1), g, nil)
- }
- if expanded == 0 {
- b.Fatal("unexpected number of expanded nodes")
- }
-}
-
-func BenchmarkAStarGnp_10_tenth(b *testing.B) {
- benchmarkAStarNilHeuristic(b, gnpUndirected_10_tenth)
-}
-func BenchmarkAStarGnp_100_tenth(b *testing.B) {
- benchmarkAStarNilHeuristic(b, gnpUndirected_100_tenth)
-}
-func BenchmarkAStarGnp_1000_tenth(b *testing.B) {
- benchmarkAStarNilHeuristic(b, gnpUndirected_1000_tenth)
-}
-func BenchmarkAStarGnp_10_half(b *testing.B) {
- benchmarkAStarNilHeuristic(b, gnpUndirected_10_half)
-}
-func BenchmarkAStarGnp_100_half(b *testing.B) {
- benchmarkAStarNilHeuristic(b, gnpUndirected_100_half)
-}
-func BenchmarkAStarGnp_1000_half(b *testing.B) {
- benchmarkAStarNilHeuristic(b, gnpUndirected_1000_half)
-}
-
-var (
- nswUndirected_10_2_2_2 = navigableSmallWorldUndirected(10, 2, 2, 2)
- nswUndirected_10_2_5_2 = navigableSmallWorldUndirected(10, 2, 5, 2)
- nswUndirected_100_5_10_2 = navigableSmallWorldUndirected(100, 5, 10, 2)
- nswUndirected_100_5_20_2 = navigableSmallWorldUndirected(100, 5, 20, 2)
-)
-
func navigableSmallWorldUndirected(n, p, q int, r float64) graph.Undirected {
g := simple.NewUndirectedGraph()
gen.NavigableSmallWorld(g, []int{n, n}, p, q, r, nil)
return g
}
+func manhattan(size int) func(x, y graph.Node) float64 {
+ return func(x, y graph.Node) float64 {
+ return manhattanBetween(coordinatesForID(x, size, size), coordinatesForID(y, size, size))
+ }
+}
+
func coordinatesForID(n graph.Node, c, r int) [2]int {
id := n.ID()
if id >= int64(c*r) {
@@ -93,51 +68,40 @@ func abs(a int) int {
return a
}
-func benchmarkAStarHeuristic(b *testing.B, g graph.Undirected, h Heuristic) {
+func BenchmarkAStarUndirected(b *testing.B) {
+ benchmarks := []struct {
+ name string
+ graph graph.Undirected
+ h Heuristic
+ }{
+ {"GNP Undirected 10 tenth", gnpUndirected_10_tenth, nil},
+ {"GNP Undirected 100 tenth", gnpUndirected_100_tenth, nil},
+ {"GNP Undirected 1000 tenth", gnpUndirected_1000_tenth, nil},
+ {"GNP Undirected 10 half", gnpUndirected_10_half, nil},
+ {"GNP Undirected 100 half", gnpUndirected_100_half, nil},
+ {"GNP Undirected 1000 half", gnpUndirected_1000_half, nil},
+
+ {"NSW Undirected 10 2 2 2", nswUndirected_10_2_2_2, nil},
+ {"NSW Undirected 10 2 2 2 heuristic", nswUndirected_10_2_2_2, manhattan(10)},
+ {"NSW Undirected 10 2 5 2", nswUndirected_10_2_5_2, nil},
+ {"NSW Undirected 10 2 5 2 heuristic", nswUndirected_10_2_5_2, manhattan(10)},
+ {"NSW Undirected 100 5 10 2", nswUndirected_100_5_10_2, nil},
+ {"NSW Undirected 100 5 10 2 heuristic", nswUndirected_100_5_10_2, manhattan(100)},
+ {"NSW Undirected 100 5 20 2", nswUndirected_100_5_20_2, nil},
+ {"NSW Undirected 100 5 20 2 heuristic", nswUndirected_100_5_20_2, manhattan(100)},
+ }
+
+ for _, bm := range benchmarks {
+ b.Run(bm.name, func(b *testing.B) {
var expanded int
for i := 0; i < b.N; i++ {
- _, expanded = AStar(simple.Node(0), simple.Node(1), g, h)
+ _, expanded = AStar(simple.Node(0), simple.Node(1), bm.graph, bm.h)
}
if expanded == 0 {
b.Fatal("unexpected number of expanded nodes")
}
+ })
}
-
-func BenchmarkAStarUndirectedmallWorld_10_2_2_2(b *testing.B) {
- benchmarkAStarHeuristic(b, nswUndirected_10_2_2_2, nil)
-}
-func BenchmarkAStarUndirectedmallWorld_10_2_2_2_Heur(b *testing.B) {
- h := func(x, y graph.Node) float64 {
- return manhattanBetween(coordinatesForID(x, 10, 10), coordinatesForID(y, 10, 10))
- }
- benchmarkAStarHeuristic(b, nswUndirected_10_2_2_2, h)
-}
-func BenchmarkAStarUndirectedmallWorld_10_2_5_2(b *testing.B) {
- benchmarkAStarHeuristic(b, nswUndirected_10_2_5_2, nil)
-}
-func BenchmarkAStarUndirectedmallWorld_10_2_5_2_Heur(b *testing.B) {
- h := func(x, y graph.Node) float64 {
- return manhattanBetween(coordinatesForID(x, 10, 10), coordinatesForID(y, 10, 10))
- }
- benchmarkAStarHeuristic(b, nswUndirected_10_2_5_2, h)
-}
-func BenchmarkAStarUndirectedmallWorld_100_5_10_2(b *testing.B) {
- benchmarkAStarHeuristic(b, nswUndirected_100_5_10_2, nil)
-}
-func BenchmarkAStarUndirectedmallWorld_100_5_10_2_Heur(b *testing.B) {
- h := func(x, y graph.Node) float64 {
- return manhattanBetween(coordinatesForID(x, 100, 100), coordinatesForID(y, 100, 100))
- }
- benchmarkAStarHeuristic(b, nswUndirected_100_5_10_2, h)
-}
-func BenchmarkAStarUndirectedmallWorld_100_5_20_2(b *testing.B) {
- benchmarkAStarHeuristic(b, nswUndirected_100_5_20_2, nil)
-}
-func BenchmarkAStarUndirectedmallWorld_100_5_20_2_Heur(b *testing.B) {
- h := func(x, y graph.Node) float64 {
- return manhattanBetween(coordinatesForID(x, 100, 100), coordinatesForID(y, 100, 100))
- }
- benchmarkAStarHeuristic(b, nswUndirected_100_5_20_2, h)
}
var (

graph/path: clean up AStar benchmarks with subtests