Opened 11 months ago
Closed 11 months ago
#31129 closed enhancement (fixed)
Improve Depth First Search in c_graph.pyx
Reported by: | gh-kliem | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.3 |
Component: | graph theory | Keywords: | |
Cc: | dcoudert | Merged in: | |
Authors: | Jonathan Kliem | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | 78d5536 (Commits, GitHub, GitLab) | Commit: | 78d553636cb4b07d51564de48ce87d1c48b7336e |
Dependencies: | #31117 | Stopgaps: |
Description (last modified by )
This ticket simply applies the improvements of #31117 to depth first search as well.
Before:
sage: def comp(): ....: for n in [5, 10, 50, 100, 500, 1000]: ....: G = graphs.Grid2dGraph(n, n) ....: print(G) ....: %timeit _ = list(G.depth_first_search(start=(0, 0))) ....: sage: comp() 2D Grid Graph for [5, 5] 8.11 µs ± 115 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 2D Grid Graph for [10, 10] 26.9 µs ± 64.3 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 2D Grid Graph for [50, 50] 827 µs ± 1.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 2D Grid Graph for [100, 100] 3.35 ms ± 5.38 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 2D Grid Graph for [500, 500] 115 ms ± 218 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 2D Grid Graph for [1000, 1000] 470 ms ± 882 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
After:
sage: def comp(): ....: for n in [5, 10, 50, 100, 500, 1000]: ....: G = graphs.Grid2dGraph(n, n) ....: print(G) ....: %timeit _ = list(G.depth_first_search(start=(0, 0))) ....: sage: comp() 2D Grid Graph for [5, 5] 4.41 µs ± 12.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 2D Grid Graph for [10, 10] 13.2 µs ± 27.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) 2D Grid Graph for [50, 50] 409 µs ± 225 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each) 2D Grid Graph for [100, 100] 1.67 ms ± 7.46 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 2D Grid Graph for [500, 500] 65.8 ms ± 54.2 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 2D Grid Graph for [1000, 1000] 264 ms ± 331 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
Change History (7)
comment:1 Changed 11 months ago by
- Branch set to public/31129
- Commit set to 606c8cf63af77f03c939c4ab9b7c2537d7dde342
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 11 months ago by
The errors reported by the patchbot are fixed in #31117. This ticket must be rebased to get last commit.
comment:3 Changed 11 months ago by
- Commit changed from 606c8cf63af77f03c939c4ab9b7c2537d7dde342 to 78d553636cb4b07d51564de48ce87d1c48b7336e
comment:4 Changed 11 months ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
We have a green bot and it's much faster this way. Perfect !
comment:5 Changed 11 months ago by
Thank you.
comment:6 Changed 11 months ago by
Btw, yield from
also gives a significant improvement, I will do this in a follow up.
comment:7 Changed 11 months ago by
- Branch changed from public/31129 to 78d553636cb4b07d51564de48ce87d1c48b7336e
- Resolution set to fixed
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
Last 10 new commits:
further improvement
revert last commit because some methods are not in all backends
trac #31117: merged with 9.3.beta5
trac #31117: better bfs
implement next_out_neighbor for static sparse
Merge branch 'u/gh-kliem/next_out_neighbor_for_static_sparse' of git://trac.sagemath.org/sage into public/graphs/31117_BFS
use next_out_neighbor_unsafe
reuse queue
account for that the loop is an if-clause now
improvements for depth_first_search