Opened 11 years ago

Closed 10 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:

Status badges

Description (last modified by 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 nthiery 10 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 11 years ago by hivert

  • Status changed from new to needs_review

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

Please review,


comment:2 Changed 11 years ago by hivert

  • Description modified (diff)

Here is an advanced solution. Please review.

comment:3 Changed 10 years ago by hivert

  • Owner changed from sage-combinat to hivert

comment:4 Changed 10 years ago by hivert

  • Keywords Cernay2012 added

comment:5 Changed 10 years ago by nthiery

  • Status changed from needs_review to positive_review

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


comment:6 Changed 10 years ago by jdemeyer

  • Reviewers set to Nicolas M. Thiéry

comment:7 Changed 10 years ago by jdemeyer

  • Merged in set to sage-5.0.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.