Hey Alexm
On Sat, Dec 15, 2012 at 09:04:40AM +1100, Alex Ghitza wrote:
> > Thanks for the hints. I hadn't noticed the magic incantation with
> > max_slope and length; that's the kind of thing I was looking for.
> >
> > There seems to be quite a bit of overhead involved. Here are some
> > timings, where mypartitions() is a naive implementation of an
> > algorithm due to Boyer [1], see below.
> > ...
> > It's not a completely fair comparison, since mypartitions() does not
> > create the list of all partitions with the desired properties, but
> > rather generates them and then throws them away. Nevertheless, it
> > seems like a big gap.
>
> The theoretically complexity of the generic algorithm behind the scene
> is the same (CAT). A big part of the constant time factor should
> disappear once the generic algorithm will be Cythoned. Here, I also
> suspect that quite some time is spent transforming list's into actual
> partition's; again this should disappear once partition's will be
> Cythoned. I could not give you a time line however.
>
> If you don't absolutely need speed, I would just use the generic
> algorithm. That's will be one less thing to refactor when the
> optimization time will finally come.
I ran %prun on the partitions of 150 and there is a large amount of time
spent in the infinity element constructor, calling isinstance, and the
rightmost_pivot. Here's the exact data I got below:
5884054 function calls in 76.544 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
507078 20.253 0.000 37.567 0.000
infinity.py:883(_element_constructor_)
43495 16.281 0.000 16.281 0.000 {isinstance}
5096 7.350 0.001 53.861 0.011
integer_list.py:192(rightmost_pivot)
507078 4.221 0.000 4.221 0.000 infinity.py:942(__init__)
257161 3.709 0.000 6.072 0.000 infinity.py:956(__cmp__)
108196 2.941 0.000 12.196 0.000 {min}
47956 2.302 0.000 13.395 0.000 infinity.py:377(_mul_)
5096 2.016 0.000 22.418 0.004 integer_list.py:38(first)
108196 1.970 0.000 17.171 0.000 integer_list.py:355(<lambda>)
106074 1.892 0.000 6.996 0.000 {max}
156168 1.881 0.000 4.436 0.000 integer_list.py:1034(<lambda>)
156168 1.801 0.000 2.555 0.000 integer_list.py:991(ceiling)
111171 1.347 0.000 2.116 0.000 infinity.py:285(__cmp__)
277561 1.340 0.000 1.340 0.000 {len}
111200 1.280 0.000 1.804 0.000 integer_list.py:972(floor)
58147 1.030 0.000 1.713 0.000 infinity.py:1232(_neg_)
5096 0.455 0.000 77.516 0.015 integer_list.py:318(next)
58147 0.385 0.000 0.385 0.000 infinity.py:820(gen)
...
I believe the calls to the infinity methods comes from the min_slope being
-infinity (and a similar issue could arise for max_slope). I've written a
small test patch (after #13605) which just setting the slopes to None (and
doing the appropriate checks) if no option is passed in and does the same
for max_length. I get about a 2x speedup, and there's likely more to be
gained if we do the same for max_part:
Also before #13605 is applied:
sage: time p = Partitions(150, max_slope=-1, length=15).list()
Time: CPU 12.99 s, Wall: 15.03 s
With just #13605:
sage: time p = Partitions(150, max_slope=-1, length=15).list()
Time: CPU 13.36 s, Wall: 14.01 s
With speedup patch:
sage: time p = Partitions(150, max_slope=-1, length=15).list()
Time: CPU 6.36 s, Wall: 6.62 s
Data with speedup patch:
3000524 function calls (3000520 primitive calls) in 35.036 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
204114 7.061 0.000 13.193 0.000
infinity.py:883(_element_constructor_)
68548 5.488 0.000 5.488 0.000 {isinstance}
5096 3.204 0.001 15.625 0.003
integer_list.py:200(rightmost_pivot)
108196 2.811 0.000 11.062 0.000 {min}
5096 1.807 0.000 20.020 0.004 integer_list.py:44(first)
108196 1.806 0.000 15.541 0.000 integer_list.py:366(<lambda>)
156168 1.678 0.000 2.332 0.000 integer_list.py:1080(ceiling)
204114 1.657 0.000 1.657 0.000 infinity.py:942(__init__)
156168 1.547 0.000 3.879 0.000 integer_list.py:1123(<lambda>)
111200 1.213 0.000 1.697 0.000 integer_list.py:1061(floor)
277562 1.185 0.000 1.185 0.000 {len}
108199 0.980 0.000 1.450 0.000 infinity.py:956(__cmp__)
47956 0.742 0.000 2.606 0.000 infinity.py:1049(_sub_)
47957 0.722 0.000 1.196 0.000 infinity.py:1232(_neg_)
58132 0.547 0.000 2.004 0.000 integer_list.py:359(<lambda>)
47957 0.505 0.000 0.801 0.000 infinity.py:285(__cmp__)
47956 0.422 0.000 0.668 0.000 infinity.py:974(_add_)
53051 0.298 0.000 0.298 0.000 {max}
Best,
Travis
PS - Sorry for the long message.
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/sage-combinat-devel/-/YHBq22s6JcoJ.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
