#8746 closed defect (fixed)
Equality of posets element is very slow
Reported by: | hivert | Owned by: | |
---|---|---|---|
Priority: | blocker | Milestone: | sage-4.4.1 |
Component: | combinatorics | Keywords: | Comparison posets elements |
Cc: | sage-combinat | Merged in: | sage-4.4.1.alpha2 |
Authors: | Florent Hivert | Reviewers: | Andrey Novoseltsev |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This is due to comparing the parent which can indeed be very slow. However most of the time when comparing x
and y
, the two parent are identical and are better compared with is
. Here is the results:
Before the patch:
sage: P = Posets.ChainPoset(30) sage: %time len([x == y for x in P for y in P]) CPU times: user 18.05 s, sys: 0.04 s, total: 18.09 s Wall time: 18.25 s 900
After the patch:
sage: P = Posets.ChainPoset(30) sage: %time len([x == y for x in P for y in P]) CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s Wall time: 0.02 s 900
Cheers,
Florent
Attachments (1)
Change History (8)
comment:1 Changed 11 years ago by
- Cc sage-combinat added
- Status changed from new to needs_review
Changed 11 years ago by
comment:2 follow-up: ↓ 3 Changed 11 years ago by
- Reviewers set to Andrey Novoseltsev
- Status changed from needs_review to positive_review
comment:3 in reply to: ↑ 2 Changed 11 years ago by
Replying to novoselt:
Looks good to me and passes all doctests.
Thanks a lot for the very quick review !
comment:4 Changed 11 years ago by
- Owner changed from sage-combinat to (none)
- Priority changed from major to blocker
comment:5 Changed 11 years ago by
I've sent the following message to sage-release and sage-devel but it doesn't seems to pass through
> This release candidate for Sage 4.4 closed 19 tickets (on top of > 4.4.alpha1). On trac, these tickets were labeled as "merged into > 4.4.alpha2", but then I decided that alpha2 should be the same as rc0. Cool ! So there is a good chance that we'll have 4.4 for sage 20.5 next week at Toronto ! This is perfect... I'm however embarrassed to have the following question/request: - how do we decide to make some ticket blocker for a release. Is it possible at this stage to make #8746 blocker for 4.4. Here is the rationale: The Posets library (by Franco Saliola) allows to deals with small Partially Ordered SETS. This kind of structure is extremely useful an common in combinatorics. Usually we play with one poset at a time, seeking for particular property of one of them. For my research I had to play with many of them and I discovered that the equality was (very fast) but completely broken, preventing them to be used eg. as key in dict. This was fixed in #7438. We solved this together with Nicolas Borie (which is a student of Nicolas Thiéry) and this was merged in alpha0. However we didn't realize that doing this we slowed of the most common usage that is comparing element in a single poset by several order of magnitude. I take the full blame for this mistake which I consider as an important regression. #8746 solve this common use issue. So is there still possible to merge #8746 while having 4.4 out before sage days 20.5 ? I realize that I should have marked this ticket as critical or blocker at its creation but I don't know how this is decided so that I never change this field... Many Apologies for this late request.
comment:6 Changed 11 years ago by
- Merged in set to 4.4.1.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:7 Changed 11 years ago by
- Merged in changed from 4.4.1.alpha2 to sage-4.4.1.alpha2
Note: See
TracTickets for help on using
tickets.
Looks good to me and passes all doctests.