Add a cache for .list() method in FiniteEnumeratedSet

[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

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: list FiniteEnumeratedSet cache Cernay2012

Author: Florent Hivert

Reviewer: Nicolas M. Thiéry

Merged: sage-5.0.beta4

Issue created by migration from https://trac.sagemath.org/ticket/11118

[hivert]

comment:1

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

Please review,

Florent

[hivert]

comment:2

Here is an advanced solution. Please review.

[hivert]

Description changed:

--- 
+++ 
@@ -6,5 +6,14 @@
 ```
 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.
+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
+```
+

[hivert]

Changed keywords from list FiniteEnumeratedSet cache to list FiniteEnumeratedSet cache Cernay2012

[nthiery]

comment:5

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