#18194: Speedup of calculation of Macdonald H and Ht bases
-------------------------------------+-------------------------------------
Reporter: zabrocki | Owner:
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-6.6
Component: combinatorics | Resolution:
Keywords: sf, days67, sage- | Merged in:
combinat | Reviewers: Travis Scrimshaw
Authors: Mike Zabrocki | Work issues:
Report Upstream: N/A | Commit:
Branch: | 54336b9146a247b6ee7ae97e47d07e0a5d5c41d0
public/combinat/mac_speedup-18194 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by tscrim):
Here's at 9196d33:
{{{
1354375 function calls (1342455 primitive calls) in 18.690
seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
484 8.666 0.018 10.441 0.022 {method 'subs' of
'sage.structure.element.Element' objects}
19061 1.364 0.000 1.460 0.000
fraction_field.py:293(<lambda>)
6231/2951 1.089 0.000 15.034 0.005 {sum}
25/23 0.832 0.033 2.594 0.113
{sage.combinat.dict_addition.dict_linear_combination}
1289 0.475 0.000 1.076 0.001 macdonald.py:722(<genexpr>)
1859/1005 0.393 0.000 1.577 0.002 macdonald.py:1388(<genexpr>)
4664 0.294 0.000 0.323 0.000
free_module.py:2028(<genexpr>)
14485 0.270 0.000 0.702 0.000 partition.py:608(__init__)
62071 0.245 0.000 0.357 0.000 combinat.py:1069(__hash__)
1958 0.229 0.000 14.979 0.008 macdonald.py:1245(<genexpr>)
484 0.225 0.000 1.215 0.003
{sage.libs.symmetrica.symmetrica.t_MONOMIAL_SCHUR_symmetrica}
82819 0.210 0.000 0.210 0.000
non_negative_integers.py:94(__contains__)
840/701 0.188 0.000 2.481 0.004 macdonald.py:1391(<genexpr>)
642 0.177 0.000 0.179 0.000
dynamic_class.py:324(dynamic_class_internal)
14620 0.173 0.000 0.469 0.000
partition.py:5049(__contains__)
47261 0.172 0.000 0.258 0.000 partition.py:632(<genexpr>)
8878 0.162 0.000 1.227 0.000
partition.py:552(__classcall_private__)
183978 0.160 0.000 0.160 0.000
rational_field.py:825(is_finite)
102278 0.158 0.000 0.158 0.000 {isinstance}
194018 0.133 0.000 0.133 0.000
rational_field.py:814(is_field)
10814 0.123 0.000 1.104 0.000
partition.py:5030(_element_constructor_)
35558 0.123 0.000 0.184 0.000 partition.py:5081(<genexpr>)
835/356 0.123 0.000 1.987 0.006 macdonald.py:677(cmunu)
1474 0.121 0.000 0.136 0.000 free_module.py:670(support)
1487 0.105 0.000 0.109 0.000 macdonald.py:636(<genexpr>)
22 0.104 0.005 15.518 0.705
macdonald.py:1244(<dictcomp>)
290 0.092 0.000 0.164 0.001 macdonald.py:669(<genexpr>)
290 0.082 0.000 0.144 0.000 macdonald.py:672(<genexpr>)
22609/20887 0.080 0.000 0.112 0.000 combinat.py:951(__eq__)
3497 0.077 0.000 0.440 0.000
free_module.py:1976(_from_dict)
15893 0.076 0.000 0.076 0.000 combinat.py:821(__init__)
24936 0.071 0.000 0.583 0.000 {all}
968 0.066 0.000 0.085 0.000
free_module.py:519(_coefficient_fast)
73371 0.066 0.000 0.095 0.000 {len}
67171 0.066 0.000 0.066 0.000 fraction_field.py:463(ring)
2331/484 0.058 0.000 4.225 0.009 macdonald.py:1338(_Lmunu)
}}}
With the current branch:
{{{
1666331 function calls (1654153 primitive calls) in 24.257
seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
968 12.717 0.013 16.142 0.017 {method 'subs' of
'sage.structure.element.Element' objects}
37990 2.681 0.000 2.871 0.000
fraction_field.py:293(<lambda>)
6231/2951 1.070 0.000 20.717 0.007 {sum}
25/23 0.833 0.033 2.509 0.109
{sage.combinat.dict_addition.dict_linear_combination}
1289 0.476 0.000 1.074 0.001 macdonald.py:722(<genexpr>)
1859/1005 0.397 0.000 1.578 0.002 macdonald.py:1453(<genexpr>)
4664 0.294 0.000 0.322 0.000
free_module.py:2028(<genexpr>)
14485 0.275 0.000 0.711 0.000 partition.py:608(__init__)
281963 0.253 0.000 0.253 0.000
rational_field.py:825(is_finite)
62071 0.245 0.000 0.360 0.000 combinat.py:1069(__hash__)
1958 0.232 0.000 20.663 0.011 macdonald.py:1304(<genexpr>)
82819 0.218 0.000 0.218 0.000
non_negative_integers.py:94(__contains__)
291562 0.195 0.000 0.195 0.000
rational_field.py:814(is_field)
840/701 0.189 0.000 2.463 0.004 macdonald.py:1456(<genexpr>)
642 0.172 0.000 0.174 0.000
dynamic_class.py:324(dynamic_class_internal)
47261 0.172 0.000 0.261 0.000 partition.py:632(<genexpr>)
8878 0.161 0.000 1.196 0.000
partition.py:552(__classcall_private__)
104289 0.159 0.000 0.159 0.000 {isinstance}
14620 0.144 0.000 0.434 0.000
partition.py:5049(__contains__)
484 0.140 0.000 1.127 0.002
{sage.libs.symmetrica.symmetrica.t_MONOMIAL_SCHUR_symmetrica}
35558 0.126 0.000 0.190 0.000 partition.py:5081(<genexpr>)
10814 0.124 0.000 1.076 0.000
partition.py:5030(_element_constructor_)
1474 0.122 0.000 0.137 0.000 free_module.py:670(support)
835/356 0.122 0.000 1.966 0.006 macdonald.py:677(cmunu)
1487 0.107 0.000 0.111 0.000 macdonald.py:636(<genexpr>)
22 0.106 0.005 21.207 0.964
macdonald.py:1303(<dictcomp>)
105995 0.103 0.000 0.103 0.000 fraction_field.py:463(ring)
3445 0.083 0.000 0.112 0.000 {method 'sub' of
'_sre.SRE_Pattern' objects}
22609/20887 0.082 0.000 0.114 0.000 combinat.py:951(__eq__)
15893 0.076 0.000 0.076 0.000 combinat.py:821(__init__)
290 0.075 0.000 0.146 0.001 macdonald.py:669(<genexpr>)
3497 0.074 0.000 0.440 0.000
free_module.py:1976(_from_dict)
24936 0.072 0.000 0.592 0.000 {all}
290 0.071 0.000 0.135 0.000 macdonald.py:672(<genexpr>)
968 0.067 0.000 0.085 0.000
free_module.py:519(_coefficient_fast)
73394 0.066 0.000 0.095 0.000 {len}
1968 0.065 0.000 0.067 0.000
fraction_field.py:412(_repr_)
}}}
So the issue is doing the 2 substitutions, which are quite expensive,
instead of 1. (Although it's quite worrisome the sheer number of calls to
certain things, like `is_finite`, but they are minor in terms of speed).
--
Ticket URL: <http://trac.sagemath.org/ticket/18194#comment:23>
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.
