Changes between Version 10 and Version 15 of Ticket #19161


Ignore:
Timestamp:
09/08/15 18:39:16 (6 years ago)
Author:
jmantysalo
Comment:

Replying to nadialafreniere:

I'm Mélodie's colleague and I reviewed the graph documentation ticket with her.

Thanks! I did the changes.

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #19161

    • Property Cc nadialafreniere added
    • Property Commit changed from b8853ed85f14cb8b3d2a9046d31505bf81223c7d to ec6f18a7290517028a45f216f4b6ae90a3157f7c
  • Ticket #19161 – Description

    v10 v15  
    1 As playing with matrices is much faster than looping over elements, this patch makes `is_complemented()` much faster.
     1This 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.
    22
    33Let `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.
     4
     5Maybe this could be optimized further, as join and meet are commutative. However, now it is already quite fast.