#15998: Restore some documentation and doctests and a function removed with
#15466
-------------------------------------+-------------------------------------
Reporter: darij | Owner:
Type: defect | Status: positive_review
Priority: major | Milestone: sage-6.2
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Darij Grinberg | Reviewers: Nathann Cohen
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/combinat/re-15466 | 5f67fa2245dec9fbf1670c75cd0a41a6da18959f
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by tscrim):
I've implemented a hybrid algorithm which mostly does a bunch of special
casing before passing it off to GAP. The one case where it definitively
does something different is when `2k >= n`, where it is just equal to the
number of partitions of size `n - k`. Also for `k = 2` where it's equal to
`n // 2`.
Some timings:
{{{
sage: N = [20, 500, 156234]
sage: K = [5, 10, 15, 20, 250, 499, 500, 501, 80000]
sage: for n in N:
....: for k in K:
....: P = Partitions(n, length=k)
....: print n,k
....: %timeit P.cardinality()
....: %timeit P.cardinality('gap')
....:
20 5
1 loops, best of 3: 7.91 ms per loop
100 loops, best of 3: 8 ms per loop
20 10
100000 loops, best of 3: 10.2 µs per loop
100 loops, best of 3: 8 ms per loop
20 15
100000 loops, best of 3: 10.5 µs per loop
100 loops, best of 3: 8 ms per loop
20 20
100000 loops, best of 3: 1.64 µs per loop
100 loops, best of 3: 8 ms per loop
20 250
100000 loops, best of 3: 1.74 µs per loop
100 loops, best of 3: 7.99 ms per loop
20 499
100000 loops, best of 3: 1.41 µs per loop
100 loops, best of 3: 8 ms per loop
20 500
1000000 loops, best of 3: 1.45 µs per loop
100 loops, best of 3: 8 ms per loop
20 501
1000000 loops, best of 3: 1.42 µs per loop
100 loops, best of 3: 7.99 ms per loop
20 80000
1000000 loops, best of 3: 1.44 µs per loop
100 loops, best of 3: 8 ms per loop
500 5
100 loops, best of 3: 8 ms per loop
100 loops, best of 3: 8 ms per loop
500 10
100 loops, best of 3: 7.99 ms per loop
100 loops, best of 3: 8 ms per loop
500 15
100 loops, best of 3: 8 ms per loop
100 loops, best of 3: 8 ms per loop
500 20
100 loops, best of 3: 8.04 ms per loop
100 loops, best of 3: 8 ms per loop
500 250
100000 loops, best of 3: 10.3 µs per loop
100 loops, best of 3: 23 ms per loop
500 499
100000 loops, best of 3: 10.2 µs per loop
10 loops, best of 3: 18.5 ms per loop
500 500
100000 loops, best of 3: 1.55 µs per loop
100 loops, best of 3: 8 ms per loop
500 501
100000 loops, best of 3: 1.41 µs per loop
100 loops, best of 3: 8 ms per loop
500 80000
100000 loops, best of 3: 1.41 µs per loop
100 loops, best of 3: 8 ms per loop
156234 5
10 loops, best of 3: 132 ms per loop
10 loops, best of 3: 134 ms per loop
156234 10
1 loops, best of 3: 280 ms per loop
1 loops, best of 3: 264 ms per loop
156234 15
1 loops, best of 3: 424 ms per loop
1 loops, best of 3: 420 ms per loop
156234 20
1 loops, best of 3: 656 ms per loop
1 loops, best of 3: 664 ms per loop
156234 250
1 loops, best of 3: 23.6 s per loop
1 loops, best of 3: 23.2 s per loop
156234 499
1 loops, best of 3: 1min 6s per loop
1 loops, best of 3: 1min 7s per loop
[Killed because it redirected to gap at this point]
sage: P = Partitions(4562, length=2800)
sage: %timeit P.cardinality('gap')
1 loops, best of 3: 980 ms per loop
sage: %timeit P.cardinality()
100000 loops, best of 3: 10.5 µs per loop
sage: P = Partitions(15623, length=8000)
sage: %timeit P.cardinality()
10000 loops, best of 3: 10.1 µs per loop
sage: %timeit P.cardinality('gap')
1 loops, best of 3: 15.4 s per loop
sage: P = Partitions(156234, length=80000)
sage: %timeit P.cardinality()
100000 loops, best of 3: 10.3 µs per loop
sage: %timeit P.cardinality('gap')
[Took too long, so killed as well]
}}}
The hybrid approach could probably be improved further for the special
case of `3k >= n > 2k`, or up to a small multiple of `k`.
I also added another special case to the ZS1 algorithm for `k == 1`.
--
Ticket URL: <http://trac.sagemath.org/ticket/15998#comment:30>
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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
