#19299: product of elements of a cartesian products is very slow
-------------------------+-------------------------------------------------
Reporter: | Owner:
vdelecroix | Status: needs_review
Type: | Milestone: sage-6.9
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
algebra | Work issues:
Keywords: | Commit:
Authors: | 1b271285ac389d31d9603e227e40da6fe3f45d3e
Vincent Delecroix | Stopgaps:
Report Upstream: N/A |
Branch: |
public/19299 |
Dependencies: |
-------------------------+-------------------------------------------------
Description changed by vdelecroix:
Old description:
> As reported in [https://groups.google.com/forum/#!topic/sage-
> devel/hbF_0XVpq_k this sage-devel thread] the product of elements of a
> cartesian product are very slow
> {{{
> sage: X = cartesian_product([IntegerModRing(2)] * 8)
> sage: A = X.addition_table() # very very long
> }}}
> One problem is the default implementation of `cartesian_factors` for
> element of such product provided by `sage.categories.sets_cat`
> {{{
> def cartesian_factors(self):
> # TODO: optimize
> return tuple(self.cartesian_projection(i) for i in
> self.parent()._sets_keys())
> }}}
>
> Before
> {{{
> sage: %time A = X.addition_table()
> CPU times: user 12.4 s, sys: 32 ms, total: 12.5 s
> Wall time: 12.4 s
> }}}
> After
> {{{
> sage: X = cartesian_product([IntegerModRing(2)] * 8)
> sage: %time A = X.addition_table()
> CPU times: user 644 ms, sys: 48 ms, total: 692 ms
> Wall time: 604 ms
> }}}
New description:
As reported in [https://groups.google.com/forum/#!topic/sage-
devel/hbF_0XVpq_k this sage-devel thread] the product of elements of a
cartesian product are very slow
{{{
sage: X = cartesian_product([IntegerModRing(2)] * 8)
sage: A = X.addition_table() # very very long
}}}
One problem is the default implementation of `cartesian_factors` for
element of such product provided by `sage.categories.sets_cat`
{{{
def cartesian_factors(self):
# TODO: optimize
return tuple(self.cartesian_projection(i) for i in
self.parent()._sets_keys())
}}}
Before
{{{
sage: X = cartesian_product([IntegerModRing(2)] * 8)
sage: %time A = X.addition_table()
CPU times: user 12.4 s, sys: 32 ms, total: 12.5 s
Wall time: 12.4 s
}}}
After
{{{
sage: X = cartesian_product([IntegerModRing(2)] * 8)
sage: %time A = X.addition_table()
CPU times: user 644 ms, sys: 48 ms, total: 692 ms
Wall time: 604 ms
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/19299#comment:6>
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.
