Re: [sage-combinat-devel] partitions
Hey Nicolas,
Thanks for investigating this! If you feel like it, I am all in favor
> of a small patch taking care of the most urgent optimizations before
> we go for the full cythonization. I am not surprised by the results of
> your timings. In MuPAD we had done a similar optimization by using the
> infinite value of IEEE floats (and its negative); it was quite fast,
> and we did not even have to handle a special case. Could you give it a
> shot using the following?
>
> sage: float('inf')
> inf
>
>
I only made the additional change to the max_part=float(infinity) default
argument to IntegerListsLex in the integer_lists_speedup-ts.patch and got
the following:
1127783 function calls (1127779 primitive calls) in 16.864 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
50962.4950.0006.0650.001
integer_list.py:200(rightmost_pivot)
50962.1900.000 11.7750.002 integer_list.py:44(first)
1081962.1370.0006.2520.000 integer_list.py:366()
1561682.0480.0002.9740.000 integer_list.py:1080(ceiling)
1561681.9160.0004.8900.000 integer_list.py:1122()
2775621.6190.0001.6190.000 {len}
1112001.4750.0002.1140.000 integer_list.py:1061(floor)
1081960.7780.0000.7780.000 {min}
581320.6840.0002.5000.000 integer_list.py:359()
530510.3790.0000.3790.000 {max}
50960.3010.000 18.2390.004 integer_list.py:329(next)
479560.2920.0000.2920.000 {method 'insert' of 'list'
objects}
50970.1950.000 18.4900.004 integer_list.py:1141(__iter__)
152880.1460.0000.1460.000 {range}
101910.1160.0000.1160.000 {sum}
50960.0490.0000.0490.000 integer_list.py:638(check)
10.0330.033 18.522 18.522
finite_enumerated_sets.py:126(_list_from_iterator)
...
sage: time p = Partitions(150, max_slope=-1, length=15).list()
Time: CPU 2.86 s, Wall: 2.98 s
without the patch I get approximately the same timings.
I've created ticket #13840
for
this and uploaded my patch (it's ready for review). I've put this patch at
the front of the combinat queue (and moved it passed the partition options
patch #13605).
Best,
Travis
--
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/-/6Deh8WGVO_8J.
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.
Re: [sage-combinat-devel] partitions
On Fri, Dec 14, 2012 at 06:51:06PM -0800, Travis Scrimshaw wrote:
>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.
Thanks for investigating this! If you feel like it, I am all in favor
of a small patch taking care of the most urgent optimizations before
we go for the full cythonization. I am not surprised by the results of
your timings. In MuPAD we had done a similar optimization by using the
infinite value of IEEE floats (and its negative); it was quite fast,
and we did not even have to handle a special case. Could you give it a
shot using the following?
sage: float('inf')
inf
I got the pleasant surprise that Sage's infinity plays well with
float('inf'):
sage: float(infinity)
inf
sage: float('inf') == infinity
False
sage: float('inf') < infinity
True
sage: float('inf') > infinity
False
sage: float('-inf') < infinity
True
sage: float('-inf') > -infinity
True
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil"
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
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.
Re: [sage-combinat-devel] partitions
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.2530.000 37.5670.000
infinity.py:883(_element_constructor_)
43495 16.2810.000 16.2810.000 {isinstance}
50967.3500.001 53.8610.011
integer_list.py:192(rightmost_pivot)
5070784.2210.0004.2210.000 infinity.py:942(__init__)
2571613.7090.0006.0720.000 infinity.py:956(__cmp__)
1081962.9410.000 12.1960.000 {min}
479562.3020.000 13.3950.000 infinity.py:377(_mul_)
50962.0160.000 22.4180.004 integer_list.py:38(first)
1081961.9700.000 17.1710.000 integer_list.py:355()
1060741.8920.0006.9960.000 {max}
1561681.8810.0004.4360.000 integer_list.py:1034()
1561681.8010.0002.5550.000 integer_list.py:991(ceiling)
711.3470.0002.1160.000 infinity.py:285(__cmp__)
2775611.3400.0001.3400.000 {len}
1112001.2800.0001.8040.000 integer_list.py:972(floor)
581471.0300.0001.7130.000 infinity.py:1232(_neg_)
50960.4550.000 77.5160.015 integer_list.py:318(next)
581470.3850.0000.3850.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)
2041147.0610.000 13.1930.000
infinity.py:883(_element_constructor_)
685485.4880.0005.4880.000 {isinstance}
50963.2040.001 15.6250.003
integer_list.py:200(rightmost_pivot)
1081962.8110.000 11.0620.000 {min}
50961.8070.000 20.0200.004 integer_list.py:44(first)
1081961.8060.000 15.5410.000 integer_list.py:366()
1561681.6780.0002.3320.000 integer_list.py:1080(ceiling)
2041141.6570.0001.6570.000 infinity.py:942(__init__)
1561681.5470.0003.8790.000 integer_list.py:1123()
1112001.2130.0001.6970.000 integer_list.py:1061(floor)
2775621.1850.0001.1850.000 {len}
1081990.9800.0001.4500.000 infinity.py:956(__cmp__)
479560.7420.0002.6060.000 infinity.py:1049(_sub_)
479570.7220.0001.1960.000 infinity.py:1232(_neg_)
581320.5470.0002.0040.000 integer_list.py:359()
479570.5050.0000.8010.000 infinity.py:285(__cmp__)
479560.4220.0000.6680.000 infinity.py:
Re: [sage-combinat-devel] partitions
Hi Alex, 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. Cheers, Nicolas -- Nicolas M. Thiéry "Isil" http://Nicolas.Thiery.name/ -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. 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.
Re: [sage-combinat-devel] partitions
Hi Anne, Andrew, 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. sage: time mypartitions(130, 15) Time: CPU 0.00 s, Wall: 0.00 s sage: time mypartitions(140, 15) Time: CPU 0.01 s, Wall: 0.01 s sage: time mypartitions(150, 15) Time: CPU 0.02 s, Wall: 0.02 s sage: time mypartitions(160, 15) Time: CPU 0.12 s, Wall: 0.12 s sage: time mypartitions(170, 15) Time: CPU 0.43 s, Wall: 0.43 s sage: time mypartitions(180, 15) Time: CPU 1.49 s, Wall: 1.49 s sage: time p = Partitions(130, max_slope=-1, length=15).list() Time: CPU 0.05 s, Wall: 0.05 s sage: time p = Partitions(140, max_slope=-1, length=15).list() Time: CPU 0.47 s, Wall: 0.47 s sage: time p = Partitions(150, max_slope=-1, length=15).list() Time: CPU 3.43 s, Wall: 3.44 s sage: time p = Partitions(160, max_slope=-1, length=15).list() Time: CPU 18.20 s, Wall: 18.25 s sage: time p = Partitions(170, max_slope=-1, length=15).list() Time: CPU 77.37 s, Wall: 77.62 s sage: time p = Partitions(180, max_slope=-1, length=15).list() Time: CPU 277.75 s, Wall: 278.64 s 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. Here is the mypartitions() code: def GenP(A, n, k, korig, ell): if (k == 1): A[k] = n # the partition is now in A, do whatever you want with it, e.g. # print A.values() else: h = n/k - (k-1)/2 # print n, k, ell, h for i in range(ell, h+1): A[k] = i GenP(A, n-i, k-1, korig, i+1) def mypartitions(n, k): A = dict() GenP(A, n, k, k, 1) It is just a straightforward implementation (that can undoubtedly be optimized) of the algorithm from [1] J.M.Boyer, Simple constant amortized time generation of fixed length numeric partitions, J. Algorithms 54 (2005), 31-39. -- Best, Alex -- Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne http://aghitza.org -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. 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.
Re: [sage-combinat-devel] partitions
Oops, sorry I didn't see your length requirement: sage: Partitions(16,max_slope=-1, length=4)[:] [[10, 3, 2, 1], [9, 4, 2, 1], [8, 5, 2, 1], [8, 4, 3, 1], [7, 6, 2, 1], [7, 5, 3, 1], [7, 4, 3, 2], [6, 5, 4, 1], [6, 5, 3, 2]] sage: Partitions(10,max_slope=-1, length=3)[:] [[7, 2, 1], [6, 3, 1], [5, 4, 1], [5, 3, 2]] Andrew On Friday, 14 December 2012 20:15:49 UTC+11, Andrew Mathas wrote: > > Hi Alex, > > The best/easiest way is probably to use the max_slope option for > Partitions: > > sage: Partitions(16,max_slope=-1)[:] > [[16], [15, 1], [14, 2], [13, 3], [13, 2, 1], [12, 4], [12, 3, 1], [11, > 5], [11, 4, 1], [11, 3, 2], [10, 6], [10, 5, 1], [10, 4, 2], [10, 3, 2, 1], > [9, 7], [9, 6, 1], [9, 5, 2], [9, 4, 3], [9, 4, 2, 1], [8, 7, 1], [8, 6, > 2], [8, 5, 3], [8, 5, 2, 1], [8, 4, 3, 1], [7, 6, 3], [7, 6, 2, 1], [7, 5, > 4], [7, 5, 3, 1], [7, 4, 3, 2], [6, 5, 4, 1], [6, 5, 3, 2], [6, 4, 3, 2, 1]] > > Cheers, > Andrew > -- 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/-/p637RNmLhOcJ. 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.
Re: [sage-combinat-devel] partitions
Hi Alex, The best/easiest way is probably to use the max_slope option for Partitions: sage: Partitions(16,max_slope=-1)[:] [[16], [15, 1], [14, 2], [13, 3], [13, 2, 1], [12, 4], [12, 3, 1], [11, 5], [11, 4, 1], [11, 3, 2], [10, 6], [10, 5, 1], [10, 4, 2], [10, 3, 2, 1], [9, 7], [9, 6, 1], [9, 5, 2], [9, 4, 3], [9, 4, 2, 1], [8, 7, 1], [8, 6, 2], [8, 5, 3], [8, 5, 2, 1], [8, 4, 3, 1], [7, 6, 3], [7, 6, 2, 1], [7, 5, 4], [7, 5, 3, 1], [7, 4, 3, 2], [6, 5, 4, 1], [6, 5, 3, 2], [6, 4, 3, 2, 1]] Cheers, Andrew -- 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/-/muZq70Aamw4J. 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.
Re: [sage-combinat-devel] partitions
Hi Alex, How about def add_rho(mu,k): mu = (mu+[0]*k)[:k] return [mu[i]+k-i for i in range(k)] def partitions_with_distinct_parts(N,k): M = Integer(N-(k+1)*k/2) P = Partitions(M,max_length=k) return [add_rho(p,k) for p in P] sage: partitions_with_distinct_parts(10,3) [[7, 2, 1], [6, 3, 1], [5, 4, 1], [5, 3, 2]] Best, Anne On 12/13/12 8:48 PM, Alex Ghitza wrote: > Hi, > > For fixed positive integers k and N, I'd like to compute the list of > partitions > > N = n_1 + n_2 + ... + n_k > > such that n_1 < n_2 < ... < n_k. > > What's the best (i.e. fastest) way to achieve this? > > > -- > Best, > Alex > > -- > Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne > http://aghitza.org -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. 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.
[sage-combinat-devel] partitions
Hi, For fixed positive integers k and N, I'd like to compute the list of partitions N = n_1 + n_2 + ... + n_k such that n_1 < n_2 < ... < n_k. What's the best (i.e. fastest) way to achieve this? -- Best, Alex -- Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne http://aghitza.org -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. 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.
Re: [sage-combinat-devel] Partitions bug with max_slope?
Yes I searched min_slope=-1 ;-) Thanks very much Nicolas.
A raised error should convince me that I made an error (or I can
consult the documentation before doing).
Thanks one more time.
Vincent
2010/1/9 Nicolas M. Thiery :
> On Sat, Jan 09, 2010 at 10:53:30AM +0100, Vincent Delecroix wrote:
>> I get the following with sage-4.3, is it normal to have [2, 1] and [1,
>> 2] as partitions ?
>>
>> {{{
>> sage: for p in Partitions(3, max_slope=1):
>> : print p
>> :
>> [3]
>> [2, 1]
>> [1, 2]
>> [1, 1, 1]
>> }}}
>
> Well, that's consistent with max_slope=1. Did you mean max_slope=-1?
> Of course, it would have been nicer to get an error (since the highest
> meaningful max_slope for a partition is 0). Hopefully we will be able
> to do that when the IntegerListsLex kernel will be rewritten
> (volunteers for that welcome!).
>
> Cheers,
> Nicolas
> --
> Nicolas M. Thiéry "Isil"
> http://Nicolas.Thiery.name/
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-combinat-devel" group.
> To post to this group, send email to sage-combinat-de...@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.
>
>
>
>
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-de...@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.
Re: [sage-combinat-devel] Partitions bug with max_slope?
On Sat, Jan 09, 2010 at 10:53:30AM +0100, Vincent Delecroix wrote:
> I get the following with sage-4.3, is it normal to have [2, 1] and [1,
> 2] as partitions ?
>
> {{{
> sage: for p in Partitions(3, max_slope=1):
> : print p
> :
> [3]
> [2, 1]
> [1, 2]
> [1, 1, 1]
> }}}
Well, that's consistent with max_slope=1. Did you mean max_slope=-1?
Of course, it would have been nicer to get an error (since the highest
meaningful max_slope for a partition is 0). Hopefully we will be able
to do that when the IntegerListsLex kernel will be rewritten
(volunteers for that welcome!).
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil"
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-de...@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.
[sage-combinat-devel] Partitions bug with max_slope?
I get the following with sage-4.3, is it normal to have [2, 1] and [1,
2] as partitions ?
{{{
sage: for p in Partitions(3, max_slope=1):
: print p
:
[3]
[2, 1]
[1, 2]
[1, 1, 1]
}}}
Vincent
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-de...@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.
