search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.36k stars 462 forks source link

add a cache on basis in free modules #11402

Closed hivert closed 13 years ago

hivert commented 13 years ago

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 commented 13 years ago
comment:1

Attachment: trac_11402-free_module_basis_cache-fh.patch.gz

A pretty simple one, ready for review.

nthiery commented 13 years ago

Reviewer: Nicolas M. Thiéry

nthiery commented 13 years ago
comment:2

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

jdemeyer commented 13 years ago

Merged: sage-4.7.1.alpha3