#20008: Implement non-recursive iterator for compositions
-------------------------------------+-------------------------------------
Reporter: tscrim | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.1
Component: combinatorics | Resolution:
Keywords: iterator | Merged in:
Authors: Travis Scrimshaw | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/combinat/composition_iterator-20008|
a796f0eb320c7955d2007486fefd2407a9bb7345
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by tscrim):
Some timings with the current branch:
{{{
sage: C = Compositions(5)
sage: %timeit for x in C: pass
The slowest run took 8.30 times longer than the fastest. This could mean
that an intermediate result is being cached
10000 loops, best of 3: 34.9 µs per loop
sage: C = Compositions(10)
sage: %timeit for x in C: pass
1000 loops, best of 3: 1.1 ms per loop
sage: C = Compositions(20)
sage: %timeit for x in C: pass
1 loops, best of 3: 1.18 s per loop
}}}
versus the old version:
{{{
sage: C = Compositions(5)
sage: %timeit for x in C: pass
The slowest run took 10.67 times longer than the fastest. This could mean
that an intermediate result is being cached
1000 loops, best of 3: 187 µs per loop
sage: C = Compositions(10)
sage: %timeit for x in C: pass
100 loops, best of 3: 9.11 ms per loop
sage: C = Compositions(20)
sage: %timeit for x in C: pass
1 loops, best of 3: 15.7 s per loop
}}}
Also, the old version instantly fails for large `n` because of the
recursion:
{{{
sage: C = Compositions(1000)
sage: for x in C: pass
...
RuntimeError: maximum recursion depth exceeded in cmp
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/20008#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
