Opened 12 years ago
Closed 11 years ago
#11118 closed enhancement (fixed)
Add a cache for .list() method in FiniteEnumeratedSet
Reported by: | Florent Hivert | Owned by: | Florent Hivert |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | combinatorics | Keywords: | list FiniteEnumeratedSet cache Cernay2012 |
Cc: | Sage Combinat CC user | Merged in: | sage-5.0.beta4 |
Authors: | Florent Hivert | Reviewers: | Nicolas M. Thiéry |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
There are two way to get the list of the elements of a FiniteEnumeratedSet
:
list(FSet) FSet.list()
The first case uses FSet.__iter__
which is slow in many practical case, for example because of deep yield
recursion...
After a discussion with Nicolas, We decided the following: In the second case, we assume that there is a need for speed and therefore we take chance to cache the list. Here is an example of speedup (needs conbinat patches installed):
sage: %timeit list(BinaryTrees(5)) 25 loops, best of 3: 24.7 ms per loop sage: %timeit BinaryTrees(5).list() 625 loops, best of 3: 6.7 µs per loop
Attachments (1)
Change History (8)
comment:1 Changed 12 years ago by
Status: | new → needs_review |
---|
comment:2 Changed 12 years ago by
Description: | modified (diff) |
---|
Here is an advanced solution. Please review.
comment:3 Changed 11 years ago by
Owner: | changed from Sage Combinat CC user to Florent Hivert |
---|
comment:4 Changed 11 years ago by
Keywords: | Cernay2012 added |
---|
comment:5 Changed 11 years ago by
Status: | needs_review → positive_review |
---|
Except for a timeout in sage/sandpiles/sandpile.py, all tests passed on sage-5.0.beta2 with the following patches applied::
trac_11003-folded.patch trac_10998-categories-posets-nt.patch trac_10670_integral_mobius_matrix_for_posets-fh.patch trac_11382-subposet_to_vertex_speedup-fh.patch trac_12476-lattice_join_matrix_speedup-fh.patch trac_11118-finite_enumset_list_cache-fh.patch
Changed 11 years ago by
Attachment: | trac_11118-finite_enumset_list_cache-fh.patch added |
---|
comment:6 Changed 11 years ago by
Reviewers: | → Nicolas M. Thiéry |
---|
comment:7 Changed 11 years ago by
Merged in: | → sage-5.0.beta4 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
I tried the most elementary solution... It seems to work.
Please review,
Florent