#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: | ec6f18a7290517028a45f216f4b6ae90a3157f7c
u/jmantysalo/faster_is_complemented| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by jmantysalo):
* status: needs_work => needs_review
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
> for both of them reduces below one second.
New description:
This patch makes `is_complemented()` much faster. Basically it does not
compute every complement of every element, just what is needed. I.e. if
`2` is a complement of `1`, it does not check if `3` and `1` are also
complements; and if `4` has no complements, it returns `False` without
searching complements for `5`, `6` and so on.
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.
Maybe this could be optimized further, as join and meet are commutative.
However, now it is already quite fast.
--
Comment:
Replying to [comment:13 nadialafreniere]:
> I'm Mélodie's colleague and I reviewed the graph documentation ticket
with her.
Thanks! I did the changes.
--
Ticket URL: <http://trac.sagemath.org/ticket/19161#comment:15>
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.
