id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
19161 LatticePoset: faster is_complemented() jmantysalo "This 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.
Let `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.
Maybe this could be optimized further, as join and meet are commutative. However, now it is already quite fast." enhancement closed major sage-6.9 combinatorics fixed mlapointe nadialafreniere Nathann Cohen, Jori Mäntysalo Nadia Lafrenière N/A a9b0d3fa8f14e195040efc7e5e2623e8e631bedd a9b0d3fa8f14e195040efc7e5e2623e8e631bedd