#19161: LatticePoset: faster is_complemented()
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Nathann Cohen, | Reviewers:
Jori Mäntysalo | Work issues:
Report Upstream: N/A | Commit:
Branch: | b8853ed85f14cb8b3d2a9046d31505bf81223c7d
u/jmantysalo/faster_is_complemented| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Nathann Cohen, Jori M\xe4ntysalo', 'oldvalue':
u'Jori M\xe4ntysalo'}):
* cc: mlapointe (added)
* author: Jori Mäntysalo => Nathann Cohen, Jori Mäntysalo
Old description:
> As playing with matrices is much faster than looping over elements, this
> patch makes `is_complemented()` much faster.
>
> Let `L10` bet the list of all lattices of 10 elements and `B10` be the
> Boolean lattice with `2^10` elements. Then without the patch it takes
> 7,76 seconds to run `len([L for L in L10 if L.is_complemented()])` and
> 101,84 seconds to run `B10.is_complemented()`. With the patch the time
> reduces to 0,38 and 0,23 seconds.
New description:
As playing with matrices is much faster than looping over elements, this
patch makes `is_complemented()` much faster.
Let `L10` bet the list of all lattices of 10 elements and `B10` be the
Boolean lattice with `2^10` elements. Then without the patch it takes 7,76
seconds to run `len([L for L in L10 if L.is_complemented()])` and 101,84
seconds to run `B10.is_complemented()`. With the patch the time for both
of them reduces below one second.
--
Comment:
Replying to [comment:8 ncohen]:
> > That was fast to test. Matrix-based loses by factor of 6 when going
through posets of size 11.
>
> Both are matrix based, so I do not know what you have in mind.
I meant that mine was "matrix-based", i.e. the speed come from speed of
matrix operations.
> Keep the one that is the fastest
Your implementation is faster.
Mélodie, can you review this? The code is now mostly from Nathann, but if
it does not work, it might also be that I have made a mistake.
> She has a different opinion about mining? Amazing.
`;=)`
--
Ticket URL: <http://trac.sagemath.org/ticket/19161#comment:10>
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.
