#17173: Poset: faster is_distributive_lattice
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Jori Mäntysalo | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/poset__faster_is_distributive_lattice|
d69e73a0a0a655e4e1595a77cda807ccb017fb02
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jmantysalo):
Replying to [comment:4 ncohen]:
> Please, try to make your code a bit better-looking:
OK, I'll try. I was thinkig about some kind of "short-circuit test" first:
start with trivial ways to see that poset surely has not the property we
are looking for. But your code example is cleaner.
> By the way it is very unpleasant to build the list of upper covers when
all you want to do is count its length. This is just a call to `in_degree`
in the hasse diagram !
I need the list. It starts with `x=give_an_array(y)` but if it's length is
exactly one, then continues with `z=x[0]`. Or do you mean optimizing it so
that if code founds out that `len(self.upper_covers(m)` is at least 2, it
returns False?
> Also, you cannot write things like that in Sage code
> {{{
> [x for x in self if not x in self.closed_interval(self.bottom(), m)]
> }}}
>
> Here is why:
Uh, I somehow thinked that it would be optimized out. But of course it can
not be done. I will correct this.
> There is also a broken doctest in `hasse_diagram.py`
?? I didn't touch it, just deprecated a function.
> I also see that you compute 'subposet' very often, and I wonder if you
should not compute subgraphs instead, as I expect that it is much more
efficient (I beware of the `UniqueRepresentation` stuff)
> Oh. And I am just noticing that your function does not seem to be
recursive at all: you can replace the recursion by a loop ! First create a
copy of self, and at each turn of the loop remove some vertices from the
copy you work on.
Hmm... First call to `subposet` can be changed to subgraph and to search
of element with in-degree zero.
And yes, this can be also changed to direct loop without recursion.
Actually I just copied the algorithm without thinking speed; in any case
this should now be almost `O(n)` instead of `O(n^3)` in current version.
But elements can not be removed from poset; vertices can be removed from
graph (with right internal implementation). I guess it is faster that way;
only code might seem slightly complicated.
Thanks for comments! I'll continue with these later.
--
Ticket URL: <http://trac.sagemath.org/ticket/17173#comment:5>
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.
