Changes between Version 1 and Version 5 of Ticket #17408


Ignore:
Timestamp:
11/28/14 06:19:59 (6 years ago)
Author:
ncohen
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #17408

    • Property Commit changed from to ce577a909e3ac2835f975cc9515b54459174e8ca
    • Property Keywords poset added
    • Property Branch changed from to u/ncohen/17408

  • Ticket #17408 – Description

    v1 v5  
    33This branch re-implements it for acyclic graphs.
    44
    5 Before
    65{{{
    76sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); g = g.cartesian_product(g)
    8 sage: %time Poset(g)
    9 CPU times: user 1.3 s, sys: 8 ms, total: 1.3 s
    10 Wall time: 1.29 s
    11 Finite poset containing 1024 elements
     7sage: %timeit g.transitive_reduction()
     81 loops, best of 3: 1.02 s per loop
     9sage: %timeit g.transitive_reduction(acyclic=True)
     1010 loops, best of 3: 28.9 ms per loop
    1211}}}
    1312
    14 After
    15 {{{
    16 sage: g = posets.BooleanLattice(5).hasse_diagram().transitive_closure(); g = g.cartesian_product(g)
    17 sage: %time Poset(g)
    18 CPU times: user 292 ms, sys: 12 ms, total: 304 ms
    19 Wall time: 265 ms
    20 Finite poset containing 1024 elements
    21 }}}
     13Now 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).
    2214
    23 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.
     15Nathann