#19197: LatticePoset: add breadth()
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Jori Mäntysalo | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/latticeposet__add_breadth__|
33610ad2c4327679b8dfc1d3af445fe4d9080e4a
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jmantysalo):
Replying to [comment:15 ncohen]:
> - Definition of 'elems': this line often test for containment in
'too_close'. Do
> not run containment tests in a list. use a 'set' for that: containment
is
> faster.
True. This gave a sligth benefit to speed.
> - Anyway, you probably should do this differently, i.e. with
> `breadth_first_search(report_distance=True)` while filtering 'too
close'
> elements according to their distance.
False. After
{{{
elems = [e[0] for e in H.breadth_first_search(j, neighbors=H.neighbors_in,
report_distance=True) if e[1] > B-2]`
}}}
it took about infinite time to compute breadth of `TamariLattice(6)`,
whereas
{{{
too_close = set(H.breadth_first_search(j, neighbors=H.neighbors_in,
distance=B-2))
elems = [e for e in H.order_ideal([j]) if e not in too_close]
}}}
did it in 40 milliseconds.
> - I still believe that it would be faster to use
> 'subsets_with_hereditary_property' inside of your code.
Don't know. Please not that this code tries first with maximal breadth and
then goes down one by one. subsets_with_hereditary_property would work to
other direction. I guess that it will stuck with too many pairs, triples
and so on.
> - Why do you deal with breadth 2 differently from the rest? That could
mean a
> couple more operations, but compared to everything else that should
not mean
> much.
True. This only slowed down the code like `sum(L.breadth() for L in L10)`,
where `L10` is a list of 10-element lattices. And even it was very slight
loss.
Anyways, I did some tests with product lattices and so. This code seems to
be "fast enought". For example it takes 4,4 seconds to create a Tamari
lattice, and 4,6 seconds to compute it's breadth. So this should not be a
bottleneck.
--
Ticket URL: <http://trac.sagemath.org/ticket/19197#comment:24>
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.
