Ticket #11382 (closed defect: fixed)
Speedup subposet and _vertex_to_element
| Reported by: | hivert | Owned by: | hivert |
|---|---|---|---|
| Priority: | major | Milestone: | sage-5.0 |
| Component: | combinatorics | Keywords: | poset, subposet, Cernay2012 |
| Cc: | sage-combinat | Work issues: | |
| Report Upstream: | N/A | Reviewers: | Nicolas M. Thiéry |
| Authors: | Florent Hivert | Merged in: | sage-5.0.beta5 |
| Dependencies: | #10998 | Stopgaps: |
Description (last modified by nthiery) (diff)
A lot of unnecessary and redundant check were performed with a preliminary version of #10998. See a more precise analyze on this thread of sage-combinat-devel
sage: P = cutting_poset(WeylGroup(['A',3])) sage: P.cardinality() 24
Before:
sage: %timeit P.subposet(P.list()[1:]) 5 loops, best of 3: 214 ms per loop
After:
sage: %timeit P.subposet(P.list()[1:]) 25 loops, best of 3: 24.8 ms per loop
Here is another timing for a bigger poset:
sage: P = cutting_poset(WeylGroup(['A',4])) sage: P.cardinality() 120
Before:
sage: %timeit P.subposet(P.list()[1:]) 5 loops, best of 3: 28.8 s per loop
After:
sage: %timeit P.subposet(P.list()[1:]) 5 loops, best of 3: 597 ms per loop
This is basically fixed in the final version of #10998 (run on a slightly slower machine than for the above timings):
sage: %timeit P.subposet(P.list()[1:]) 5 loops, best of 3: 801 ms per loop
The attached patch optimizes it a tiny bit further and adds doctests:
sage: %timeit P.subposet(P.list()[1:]) 5 loops, best of 3: 688 ms per loop
Attachments
Change History
comment:1 Changed 2 years ago by hivert
- Status changed from new to needs_review
- Description modified (diff)
comment:2 Changed 2 years ago by hivert
- Summary changed from subposet is too slow to Speedup subposet and _vertex_to_element
comment:5 Changed 16 months ago by hivert
- Keywords poset, subposet, Cernay2012 added; poset subposet removed
comment:6 Changed 16 months ago by nthiery
- Reviewers set to Nicolas M. Thiéry
- Description modified (diff)
comment:9 Changed 16 months ago by nthiery
We finalized the patch together with Florent. Positive review on the version I just uploaded, assuming the test pass (I am running them).
comment:11 Changed 15 months ago by jdemeyer
- Status changed from positive_review to closed
- Resolution set to fixed
- Merged in set to sage-5.0.beta5
Note: See
TracTickets for help on using
tickets.

