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:

Status badges

Description (last modified by Florent Hivert)

There are two way to get the list of the elements of a FiniteEnumeratedSet:


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)

trac_11118-finite_enumset_list_cache-fh.patch (17.4 KB) - added by Nicolas M. Thiéry 11 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 12 years ago by Florent Hivert

Status: newneeds_review

I tried the most elementary solution... It seems to work.

Please review,


comment:2 Changed 12 years ago by Florent Hivert

Description: modified (diff)

Here is an advanced solution. Please review.

comment:3 Changed 11 years ago by Florent Hivert

Owner: changed from Sage Combinat CC user to Florent Hivert

comment:4 Changed 11 years ago by Florent Hivert

Keywords: Cernay2012 added

comment:5 Changed 11 years ago by Nicolas M. Thiéry

Status: needs_reviewpositive_review

Except for a timeout in sage/sandpiles/, all tests passed on sage-5.0.beta2 with the following patches applied::


Changed 11 years ago by Nicolas M. Thiéry

comment:6 Changed 11 years ago by Jeroen Demeyer

Reviewers: Nicolas M. Thiéry

comment:7 Changed 11 years ago by Jeroen Demeyer

Merged in: sage-5.0.beta4
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.