#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, Travis
Report Upstream: N/A | Scrimshaw
Branch: | Work issues:
public/combinat/re-15466 | Commit:
Dependencies: | da4bf10359d8a23746de8647904ba2c389f61d59
| Stopgaps:
-------------------------------------+-------------------------------------
Comment (by tscrim):
There are two things that slow it down:
- checking to make sure it is a valid partition (something which I'd think
you'd advocate), and
- striping trailing 0's (i.e. standardizing the data, which again I'd
think you'd advocate).
As I recall, there's code out there that assumes that initialization of a
partition always does these (one of these) two operations (both of which
need to loop over each partition), so we can't refactor this away
completely. I also don't like passing these (IMO stupid) 'check'
arguments.
Here's my data:
{{{
sage: P = Partitions(80, length=8)
sage: %prun L = list(P)
11256609 function calls in 87.175 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
3602112 24.280 0.000 36.376 0.000 partition.py:697(<genexpr>)
450264 16.763 0.000 75.347 0.000 partition.py:673(__init__)
3602112 14.055 0.000 14.055 0.000
non_negative_integers.py:94(__contains__)
450264 11.744 0.000 48.120 0.000 {all}
450266 9.136 0.000 85.687 0.000 partition.py:5643(__iter__)
1350792 3.582 0.000 3.582 0.000 {len}
450264 3.194 0.000 4.499 0.000 combinat.py:780(__init__)
900528 2.933 0.000 2.933 0.000 {isinstance}
1 0.742 0.742 43.490 43.490
finite_enumerated_sets.py:171(_list_from_iterator)
1 0.740 0.740 87.175 87.175 <string>:1(<module>)
1 0.007 0.007 43.496 43.496
finite_enumerated_sets.py:254(list)
1 0.000 0.000 0.000 0.000
dynamic_class.py:122(dynamic_class)
2 0.000 0.000 0.000 0.000
{sage.combinat.partitions.ZS1_iterator_nk}
1 0.000 0.000 0.000 0.000 {method 'disable' of
'_lsprof.Profiler' objects}
}}}
The check of containment in `NN` is actually pretty good:
{{{
sage: f = int(5)
sage: %timeit f in ZZ
100000 loops, best of 3: 5.33 µs per loop
sage: %timeit f in NN
1000000 loops, best of 3: 1.95 µs per loop
}}}
Remember that Sage's preparser wraps a number as an `Integer`, so the
following is unfair:
{{{
sage: %timeit 5 in ZZ # quick parent check
1000000 loops, best of 3: 476 ns per loop
sage: %timeit 5 in NN
100000 loops, best of 3: 2.04 µs per loop
}}}
I also tried my usual optimizing of using enumerate and `if not mu` for
`len(mu) == 0` and it didn't seem to result in a noticeable speedup.
Also your test is unfair because we have to do extra processing on the
result from iterator to get the actual partition we wanted.
So in the end, we'll have to sit down on a separate ticket and optimize
partition creation someday, but not today.
However I'm not surprised you see the slowdown in using a list in python
as opposed to C. Python is slow compared to C because of it's interpreted
/weakly-typed/higher-level nature.
PS - Nathann, that's 4 things `:P`
--
Ticket URL: <http://trac.sagemath.org/ticket/15998#comment:40>
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.
