add a cache on basis in free modules

[hivert]

Let FM be a combinatorial free module currently creating elements using the basis is very slow because the family is recreated each time:

sage: FM = CombinatorialFreeModule(QQ, ZZ)
sage: %timeit [FM.basis()[i] for i in range(100)]
5 loops, best of 3: 44.4 ms per loop

Adding a cache to basis gives a large speedup

sage: FM = CombinatorialFreeModule(QQ, ZZ)
sage: %timeit [FM.basis()[i] for i in range(100)]
125 loops, best of 3: 3.45 ms per loop

The speedup will be even larger with Simon King optimization on cache_methods.

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: FreeModules basis cache

Author: Florent Hivert

Reviewer: Nicolas M. Thiéry

Merged: sage-4.7.1.alpha3

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

[hivert]

comment:1

Attachment: trac_11402-free_module_basis_cache-fh.patch.gz

A pretty simple one, ready for review.

[nthiery]

Reviewer: Nicolas M. Thiéry

[nthiery]

comment:2

I had wanted to do that for a while. Thanks!

[jdemeyer]

Merged: sage-4.7.1.alpha3