#17408: Faster transitive_reduction (=> faster Poset creation)
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: poset | Commit:
Authors: | ce577a909e3ac2835f975cc9515b54459174e8ca
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/17408 |
Dependencies: |
-------------------------+-------------------------------------------------
Description changed by ncohen:
Old description:
> As reported on #17361, the call to `transitive_reduction` represents a
> non-negligible part of Poset creation.
>
> This branch re-implements it for acyclic graphs.
>
> Before
> {{{
> sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure();
> g = g.cartesian_product(g)
> sage: %time Poset(g)
> CPU times: user 1.3 s, sys: 8 ms, total: 1.3 s
> Wall time: 1.29 s
> Finite poset containing 1024 elements
> }}}
>
> After
> {{{
> sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure();
> g = g.cartesian_product(g)
> sage: %time Poset(g)
> CPU times: user 292 ms, sys: 12 ms, total: 304 ms
> Wall time: 265 ms
> Finite poset containing 1024 elements
> }}}
>
> Note that a LOT of time is lost on calls to `__eq__`. If I make no
> mistake it is because `Posets` are `UniqueRepresentation`. I would
> personally be very very glad if we could get rid of that.
New description:
As reported on #17361, the call to `transitive_reduction` represents a
non-negligible part of Poset creation.
This branch re-implements it for acyclic graphs.
{{{
sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); g
= g.cartesian_product(g)
sage: %timeit g.transitive_reduction()
1 loops, best of 3: 1.02 s per loop
sage: %timeit g.transitive_reduction(acyclic=True)
10 loops, best of 3: 28.9 ms per loop
}}}
Now the critical part in the creation of a `Poset` is triggered by
`UniqueRepresentation`. As soon as you create a `Poset` it is being
compared with those that already exists... That is actually pre-computing
the equality relationships between all existing posets even if you never
asked for it, and I personally see it as wasted time (especially since I
cannot disable it).
Nathann
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17408#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.
