Opened 6 years ago
Closed 6 years ago
#11118 closed enhancement (fixed)
Add a cache for .list() method in FiniteEnumeratedSet
Reported by: | hivert | Owned by: | hivert |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | combinatorics | Keywords: | list FiniteEnumeratedSet cache Cernay2012 |
Cc: | sage-combinat | 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 6 years ago by
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
- Description modified (diff)
Here is an advanced solution. Please review.
comment:3 Changed 6 years ago by
- Owner changed from sage-combinat to hivert
comment:4 Changed 6 years ago by
- Keywords Cernay2012 added
comment:5 Changed 6 years ago by
- Status changed from needs_review to 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 6 years ago by
comment:6 Changed 6 years ago by
- Reviewers set to Nicolas M. Thiéry
comment:7 Changed 6 years ago by
- Merged in set to sage-5.0.beta4
- Resolution set to fixed
- Status changed from positive_review to closed
I tried the most elementary solution... It seems to work.
Please review,
Florent