#17492: Speedup k-closed check
-------------------------------------+-------------------------------------
Reporter: tscrim | Owner: tscrim
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.5
Component: matroid theory | Resolution:
Keywords: k-closed | Merged in:
Authors: Travis Scrimshaw | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/tscrim/k_closed_speedup-17492 | 2da089f7f2be369af66a5277eb5c9797dcbc5234
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by tscrim):
* status: new => needs_review
* commit: => 2da089f7f2be369af66a5277eb5c9797dcbc5234
* branch: => u/tscrim/k_closed_speedup-17492
Comment:
With patch:
{{{
sage: PR4 = RootSystem(['D',4]).root_lattice().positive_roots()
sage: m4 = matrix(map(lambda x: x.to_vector(), PR4)).transpose()
sage: M4 = Matroid(m4)
sage: %timeit M4.is_k_closed(3)
10 loops, best of 3: 147 ms per loop
sage: %timeit M4.is_k_closed(4)
1 loops, best of 3: 413 ms per loop
sage: PR5 = RootSystem(['D',5]).root_lattice().positive_roots()
sage: m5 = matrix(map(lambda x: x.to_vector(), PR5)).transpose()
sage: M5 = Matroid(m5)
sage: %timeit M5.is_k_closed(3)
1 loops, best of 3: 1.45 s per loop
}}}
Before:
{{{
sage: %timeit M4.is_k_closed(3)
1 loops, best of 3: 776 ms per loop
sage: %timeit M4.is_k_closed(4)
1 loops, best of 3: 3.09 s per loop
sage: %timeit M5.is_k_closed(3)
1 loops, best of 3: 4.16 s per loop
}}}
So we are getting a 3x~4x speedup.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=ff68516e2ce63ac8a8d6de57ec9490e9b05c9ad3
ff68516]||{{{Speedup k-closure by using python sets.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=07c0a3f4d5101844e1fe22044f073380a1a1433d
07c0a3f]||{{{Removed unnecessary import.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=2da089f7f2be369af66a5277eb5c9797dcbc5234
2da089f]||{{{One additional tweak to avoid unnecessary checks.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/17492#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
