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:

Status badges

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 Rudi

Branch: → u/Rudi/more_efficient_components___for_basisexchangematroid

comment:2 Changed 8 years ago by Rudi

Cc: chaoxu added
Commit: → 9767c25c5c5ec12d4d600a50966ee3494a2352e7
Status: new → needs_review

All done.

New commits:

​9767c25added BasisEchangeMatroid.components()

comment:3 Changed 8 years ago by Rudi

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 chaoxu

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:5 Changed 8 years ago by Rudi

Owner: set to Rudi

Thanks Chao. That was quick!

comment:6 Changed 8 years ago by vbraun

Branch: u/Rudi/more_efficient_components___for_basisexchangematroid → 9767c25c5c5ec12d4d600a50966ee3494a2352e7
Resolution: → fixed
Status: positive_review → closed
Note: See TracTickets for help on using tickets.