Opened 7 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 hivert)

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)

trac_11118-finite_enumset_list_cache-fh.patch (17.4 KB) - added by nthiery 6 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 7 years ago by hivert

  • Status changed from new to needs_review

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

Please review,

Florent

comment:2 Changed 7 years ago by hivert

  • Description modified (diff)

Here is an advanced solution. Please review.

comment:3 Changed 6 years ago by hivert

  • Owner changed from sage-combinat to hivert

comment:4 Changed 6 years ago by hivert

  • Keywords Cernay2012 added

comment:5 Changed 6 years ago by nthiery

  • 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

comment:6 Changed 6 years ago by jdemeyer

  • Reviewers set to Nicolas M. Thiéry

comment:7 Changed 6 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.