better-dfs - Branch - evenfurther/pathfinding

feat(dfs): make DFS more efficient by using IndexMap rather than Vec

#553Closed

Comparing

better-dfs

(

3464e58

) with

main

(

e32db8c

)

-20%

Improvements: 3

Regressions: 1

Untouched: 30

Benchmarks

Failed

fill-corner_to_corner_dijkstra

benches/algos-fill.rs::benches::corner_to_corner_dijkstra

Regression

-20%

1.3 ms1.7 ms

Improved

corner_to_corner_dfs

benches/algos.rs::benches::corner_to_corner_dfs

×18

31.5 ms1.7 ms

fill-corner_to_corner_dfs

benches/algos-fill.rs::benches::corner_to_corner_dfs

×2.1

4.5 ms2.1 ms

corner_to_corner_dijkstra

benches/algos.rs::benches::corner_to_corner_dijkstra

+16%

1.9 ms1.6 ms

Passed

corner_to_corner_astar

benches/algos.rs::benches::corner_to_corner_astar

+8%

90.1 µs83.6 µs

no_path_dijkstra

benches/algos.rs::benches::no_path_dijkstra

+5%

1.7 ms1.6 ms

fill-corner_to_corner_idastar

benches/algos-fill.rs::benches::corner_to_corner_idastar

+5%

166.4 µs158.9 µs

no_path_astar

benches/algos.rs::benches::no_path_astar

+5%

1.9 ms1.8 ms

corner_to_corner_idastar

benches/algos.rs::benches::corner_to_corner_idastar

129.2 µs128.7 µs

fill-corner_to_corner_bfs

benches/algos-fill.rs::benches::corner_to_corner_bfs

1.4 ms1.4 ms

fill-no_path_dijkstra

benches/algos-fill.rs::benches::no_path_dijkstra

1.1 ms1.1 ms

separate_components

benches/algos.rs::benches::bench_separate_components

2.2 ms2.2 ms

wikipedia_example_dense

benches/edmondskarp.rs::benches::wikipedia_example_dense

30.4 µs30.4 µs

Compare kuhn_munkres with different input sizes[32]

benches/kuhn_munkres.rs::benches::compare_size

83.8 µs83.8 µs

corner_to_corner_iddfs

benches/algos.rs::benches::corner_to_corner_iddfs

1.5 ms1.5 ms

separate_components

benches/separate_components.rs::benches::bench_separate_components

7.3 ms7.3 ms

Compare kuhn_munkres with different input sizes[64]

benches/kuhn_munkres.rs::benches::compare_size

418.8 µs418.8 µs

corner_to_corner_bfs

benches/algos.rs::benches::corner_to_corner_bfs

1.5 ms1.5 ms

Compare kuhn_munkres with different input sizes[128]

benches/kuhn_munkres.rs::benches::compare_size

2.6 ms2.6 ms

fill-corner_to_corner_iddfs

benches/algos-fill.rs::benches::corner_to_corner_iddfs

3.9 ms3.9 ms

Compare kuhn_munkres with different input sizes[256]

benches/kuhn_munkres.rs::benches::compare_size

16.7 ms16.7 ms

Compare kuhn_munkres with different input sizes[512]

benches/kuhn_munkres.rs::benches::compare_size

500.1 ms500.1 ms

transpose

benches/matrices.rs::benches::transpose_benchmark

42.2 µs42.2 µs

wikipedia_example_sparse

benches/edmondskarp.rs::benches::wikipedia_example_sparse

45.8 µs45.8 µs

arena

benches/movingai.rs::benches::arena

47.2 ms47.2 ms

fill-no_path_bfs

benches/algos-fill.rs::benches::no_path_bfs

1.4 ms1.4 ms

transpose_non_square

benches/matrices.rs::benches::transpose_non_square_benchmark

159.7 µs159.8 µs

fill-no_path_astar

benches/algos-fill.rs::benches::no_path_astar

1.5 ms1.5 ms

fill-corner_to_corner_astar

benches/algos-fill.rs::benches::corner_to_corner_astar

117.1 µs117.3 µs

corner_to_corner_fringe

benches/algos.rs::benches::corner_to_corner_fringe

-1%

99.8 µs101 µs

no_path_bfs

benches/algos.rs::benches::no_path_bfs

-3%

1.3 ms1.3 ms

fill-corner_to_corner_fringe

benches/algos-fill.rs::benches::corner_to_corner_fringe

-6%

98 µs104.2 µs

fill-no_path_fringe

benches/algos-fill.rs::benches::no_path_fringe

-7%

1.2 ms1.3 ms

no_path_fringe

benches/algos.rs::benches::no_path_fringe

-9%

1.9 ms2.1 ms

Commits

Click on a commit to change the comparison range

Base

main

e32db8c

-19.93%

feat(dfs): make DFS more efficient by using IndexSet internally This requires an API change as using an `IndexSet` requires the type to implement `Hash`.

3464e58

2 years ago

by samueltardieu

Home Terms Privacy Docs