#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 ncohen):
> OK, I see... to be honest, that's too many cases for me to code. (First
we branch on whether there is space left for the partition to grow, then
on whether x[h] is 2, then on whether there is a 1 in the partition; am I
seeing that right?) But it's a nice argument!
Hmmmm... Well, you already tested that x[h] was larger than two, it is the
test that you have just before the loop in your code.
And you can test at the same time if there is space left for the partition
to grow and if there is a one to the right of x[h] : that's testing if h
is equal to m `:-)`
If it is,you can skip the loop.
If it isn't,then you have to decrease h in order to find this element
larger than x[h]+2.
I do not know which kind of speed difference this could make, but really
given that you return Python lists I would say that it does not change
much.
Oh, actually Marc Mezzarobba taught me a nice profiling trick that I would
like to use right here to see if the most time consuming operation is this
multiplication, let me check !!!
Okay, first most of the time is spent over-wrapping the result and not
computing stuff. I love combinat code.
{{{
sage: sage: %time _=list(Partitions(100,length=8))
CPU times: user 20 s, sys: 56 ms, total: 20.1 s
Wall time: 19.9 s
sage: sage: %time _=list(ZS1_iterator_nk(100-8,8))
CPU times: user 796 ms, sys: 0 ns, total: 796 ms
Wall time: 797 ms
}}}
Ahem. Anyway `:-P`
And it seems to still be the case when you call `ZS1_iterator`, i.e.
mostof the time is Python time.
Replacing all of the "yield the partition" with "yield x[h-1]" (so that it
does not create lists all the time) gives...
Oh. I am not very sure of what I read in the profiling, but it looks like
having a Python list x instead of a C one has a cost : each time you read
one of its elements, this element is a "python object" and not a C
integer. So whatever you do with it is a python operation.
I now use the C code which replaces this python list x with a C array...
Okay, now the bottle neck seems the moments when the iterator yields a
value, which has to be converted to a Python integer before being
returned.
Ahahaha. And no multiplication has appeared yet unless I misread
something.
Nice.
It's funny to profile code `:-)`
Soooooooooooo there are two things to remember, I believe :
1) The optimization above would change nothing to the current code's speed
2) This code is combinat code, all its effort is made toward ONE objective
: generating new objects, creating new classes, making use of
metaclasscall
3) If you want MUCH better performances, call ZS1 directly
4) It seems that you can go very very far with this code if you do
everything at C level. I mean, if someday you want to run serious
computations this code is good, but what you should do is work on the
Cython code directly and don't wait for it to return its data at Python
level.
Wow.
Cool `:-)`
Well, I think I should go eat something now. Thank you very much for this
code, and have a nice day ! `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/15998#comment:39>
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.
