Opened 8 years ago
Closed 8 years ago
#18591 closed enhancement (fixed)
More efficient components() for BasisExchangeMatroid
Reported by: | Rudi | Owned by: | Rudi |
---|---|---|---|
Priority: | major | Milestone: | sage-6.8 |
Component: | matroid theory | Keywords: | |
Cc: | chaoxu | Merged in: | |
Authors: | Rudi Pendavingh | Reviewers: | Chao Xu |
Report Upstream: | N/A | Work issues: | |
Branch: | 9767c25 (Commits, GitHub, GitLab) | Commit: | 9767c25c5c5ec12d4d600a50966ee3494a2352e7 |
Dependencies: | Stopgaps: |
Description
Write a specialised version of Matroid.components() for BasisExchangeMatroid? which exploits bitsets to improve the efficiency.
Change History (6)
comment:1 Changed 8 years ago by
Branch: | → u/Rudi/more_efficient_components___for_basisexchangematroid |
---|
comment:2 Changed 8 years ago by
Cc: | chaoxu added |
---|---|
Commit: | → 9767c25c5c5ec12d4d600a50966ee3494a2352e7 |
Status: | new → needs_review |
comment:3 Changed 8 years ago by
With the new routine:
sage: A =MatrixSpace(GF(2), 500, 1000).random_element() sage: M = Matroid(A) sage: timeit("M.components()") 625 loops, best of 3: 244 µs per loop
Forcing the use of the old routine:
sage: timeit("sage.matroids.matroid.Matroid.components(M)") 5 loops, best of 3: 52.2 ms per loop
comment:4 Changed 8 years ago by
Reviewers: | → Chao Xu |
---|---|
Status: | needs_review → positive_review |
All tests passed. The behavior also matches with the original for all matroids of at most 9 elements.
comment:6 Changed 8 years ago by
Branch: | u/Rudi/more_efficient_components___for_basisexchangematroid → 9767c25c5c5ec12d4d600a50966ee3494a2352e7 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Note: See
TracTickets for help on using
tickets.
All done.
New commits:
added BasisEchangeMatroid.components()