More efficient components() for BasisExchangeMatroid

[sagetrac-Rudi]

Write a specialised version of Matroid.components() for BasisExchangeMatroid which exploits bitsets to improve the efficiency.

CC: @chaoxu

Component: matroid theory

Author: Rudi Pendavingh

Branch/Commit: 9767c25

Reviewer: Chao Xu

Issue created by migration from https://trac.sagemath.org/ticket/18591

[sagetrac-Rudi]

Branch: u/Rudi/more_efficient_components___for_basisexchangematroid

[sagetrac-Rudi]

Commit: 9767c25

[sagetrac-Rudi]

comment:2

All done.

---

New commits:

9767c25

added BasisEchangeMatroid.components()

[sagetrac-Rudi]

comment:3

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

[chaoxu]

Reviewer: Chao Xu

[chaoxu]

comment:4

All tests passed.
The behavior also matches with the original for all matroids of at most 9 elements.

[sagetrac-Rudi]

comment:5

Thanks Chao. That was quick!

[vbraun]

Changed branch from u/Rudi/more_efficient_components___for_basisexchangematroid to 9767c25