Opened 10 years ago
Closed 9 years ago
#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 | Merged in: | sage-5.0.beta5 |
Authors: | Florent Hivert | Reviewers: | Nicolas M. Thiéry |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #10998 | Stopgaps: |
Description (last modified by )
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 (1)
Change History (12)
comment:1 Changed 10 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Summary changed from subposet is too slow to Speedup subposet and _vertex_to_element
comment:3 Changed 10 years ago by
- Dependencies set to #10998
- Owner changed from sage-combinat to (none)
comment:4 Changed 9 years ago by
- Owner changed from (none) to hivert
comment:5 Changed 9 years ago by
- Keywords Cernay2012 added
comment:6 Changed 9 years ago by
- Description modified (diff)
- Reviewers set to Nicolas M. Thiéry
comment:7 Changed 9 years ago by
- Description modified (diff)
comment:8 Changed 9 years ago by
- Description modified (diff)
comment:9 Changed 9 years ago by
Changed 9 years ago by
comment:10 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:11 Changed 9 years ago by
- Merged in set to sage-5.0.beta5
- Resolution set to fixed
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
We finalized the patch together with Florent. Positive review on the version I just uploaded, assuming the test pass (I am running them).