Opened 4 years ago
Closed 4 years ago
#19161 closed enhancement (fixed)
LatticePoset: faster is_complemented()
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  combinatorics  Keywords:  
Cc:  mlapointe, nadialafreniere  Merged in:  
Authors:  Nathann Cohen, Jori Mäntysalo  Reviewers:  Nadia Lafrenière 
Report Upstream:  N/A  Work issues:  
Branch:  a9b0d3f (Commits)  Commit:  a9b0d3fa8f14e195040efc7e5e2623e8e631bedd 
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Change History (22)
comment:1 Changed 4 years ago by
 Branch set to u/jmantysalo/faster_is_complemented
comment:2 Changed 4 years ago by
 Commit set to bf8fdd5dd0702a6158691183ac6a3351461a650e
 Status changed from new to needs_review
comment:3 Changed 4 years ago by
 Description modified (diff)
comment:4 followup: ↓ 5 Changed 4 years ago by
HMmmm... The speedup is cool, but the algorithm is slightly less clear. Is it slower to do it like that:
from itertools import izip for row1,row2 in izip(meet,join): for c1,c2 in izip(row1,row2): if c1==0 and c2==n1: break else: retun False return True
Sorry but it is a bit hard for me to try it today: I burned the two main fingers of my right hand while cooking, and I type mostly with my left hand :/
Nathann
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 4 years ago by
Replying to ncohen:
Is it slower to do it like that:
It depends. For B10
example your algorithm is clearly faster, it takes about half of the time of matrixbased algorithm. And for the L10
example it is twise slower. I guess that your is better, but I will check that with some more tests.
Sorry but it is a bit hard for me to try it today: I burned the two main fingers of my right hand while cooking, and I type mostly with my left hand
:/
Use professionals. Eat at MacDonalds?.
comment:6 in reply to: ↑ 5 Changed 4 years ago by
It depends. For
B10
example your algorithm is clearly faster, it takes about half of the time of matrixbased algorithm. And for theL10
example it is twise slower. I guess that your is better, but I will check that with some more tests.
Hmmmm.. I do not know what to think of it. It "may" answer "no" slightly faster, but then iterators are not free. Sigh. That would be straightforward in C with real arrays, and not those unreliable matrices _
Use professionals. Eat at MacDonalds?.
Ahah.
Nathann
comment:7 followup: ↓ 8 Changed 4 years ago by
That was fast to test. Matrixbased loses by factor of 6 when going through posets of size 11.
(About food: When you want a car, do you go to mine to get some iron ore? Why should it be different with food? :=)
(But my wife has different opinion on that...))
comment:8 in reply to: ↑ 7 ; followup: ↓ 10 Changed 4 years ago by
That was fast to test. Matrixbased loses by factor of 6 when going through posets of size 11.
Both are matrix based, so I do not know what you have in mind. Keep the one that is the fastest, and if it is the current one then consider it in positive_review
, provided that tests pass (the patchbot still silent).
(About food: When you want a car, do you go to mine to get some iron ore? Why should it be different with food?
:=)
(But my wife has different opinion on that...))
She has a different opinion about mining? Amazing.
In the case at hand (if I may say), I do not see the need to generalize to cooking in general. Let me just hope that I will not make the same mistake, with the same hand, tomorrow morning.
Nathann
comment:9 Changed 4 years ago by
 Commit changed from bf8fdd5dd0702a6158691183ac6a3351461a650e to b8853ed85f14cb8b3d2a9046d31505bf81223c7d
Branch pushed to git repo; I updated commit sha1. New commits:
b8853ed  Faster algorithm, thanks to Nathann Cohen.

comment:10 in reply to: ↑ 8 Changed 4 years ago by
 Cc mlapointe added
 Description modified (diff)
Replying to ncohen:
That was fast to test. Matrixbased loses by factor of 6 when going through posets of size 11.
Both are matrix based, so I do not know what you have in mind.
I meant that mine was "matrixbased", i.e. the speed come from speed of matrix operations.
Keep the one that is the fastest
Your implementation is faster.
Mélodie, can you review this? The code is now mostly from Nathann, but if it does not work, it might also be that I have made a mistake.
She has a different opinion about mining? Amazing.
;=)
comment:11 followup: ↓ 12 Changed 4 years ago by
HMmmmm... Factor 6?... O_o
Weird, weird... :/
comment:12 in reply to: ↑ 11 Changed 4 years ago by
Replying to ncohen:
HMmmmm... Factor 6?...
O_o
Weird, weird...
:/
Not really. Original code checks ALL element pairs. My code takes one element, and kind of check it against all other elements, and stops when an element has no complement. Your code jumps to next element when it founds a complement and return False
if it found an element without the complement.
Even your code is not optimal, because meet and join are commutative operations. But it may be slower to optimize that, because the code would be more complicated.
In any case, this is now quite fast and IMO ready for review.
comment:13 followup: ↓ 15 Changed 4 years ago by
 Cc nadialafreniere added
 Status changed from needs_review to needs_work
Hi Jori, I'm Mélodie's colleague and I reviewed the graph documentation ticket with her.
About your new ticket, now.
+ n = self.cardinality()1
+ for row1,row2 in izip(mt, jn):
+ for c1,c2 in izip(row1,row2):
+ if c1==0 and c2==n:
You should respect the Python / Sage conventions and add spaces before and after binary operators of the lowest priority : self.cardinality()  1
, c1 == 0
, etc. This includes equality and assignments.
As well, there should be spaces after every coma sign: row1, row2
, c1, c2
, izip(row1, row2)
. For more info on these conventions, see http://doc.sagemath.org/html/en/developer/coding_basics.html#pythoncodestyle
comment:14 Changed 4 years ago by
 Commit changed from b8853ed85f14cb8b3d2a9046d31505bf81223c7d to ec6f18a7290517028a45f216f4b6ae90a3157f7c
Branch pushed to git repo; I updated commit sha1. New commits:
ec6f18a  Reviewers comment about Python conventions.

comment:15 in reply to: ↑ 13 Changed 4 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
Replying to nadialafreniere:
I'm Mélodie's colleague and I reviewed the graph documentation ticket with her.
Thanks! I did the changes.
comment:16 followup: ↓ 19 Changed 4 years ago by
Most of the things look fine. One last thing: I know you didn't touch to this, but the examples should also respect the python conventions. Therefore, I'm hoping to see a space after each of the commas.
sage: L = LatticePoset({0:[1,2,3],1:[4],2:[4],3:[4]})
sage: L = LatticePoset({0:[1,2],1:[3],2:[3],3:[4]})
should look like
sage: L = LatticePoset({0:[1, 2, 3], 1:[4], 2:[4], 3:[4]})
comment:17 Changed 4 years ago by
 Status changed from needs_review to needs_work
comment:18 Changed 4 years ago by
 Commit changed from ec6f18a7290517028a45f216f4b6ae90a3157f7c to a9b0d3fa8f14e195040efc7e5e2623e8e631bedd
Branch pushed to git repo; I updated commit sha1. New commits:
a9b0d3f  Spaces to examples of is_complemented_lattice().

comment:19 in reply to: ↑ 16 ; followup: ↓ 21 Changed 4 years ago by
 Status changed from needs_work to needs_review
Replying to nadialafreniere:
  but the examples should also respect the python conventions. Therefore, I'm hoping to see a space after each of the commas.
Done this.
comment:20 Changed 4 years ago by
 Reviewers set to Nadia Lafrenière
 Status changed from needs_review to positive_review
comment:21 in reply to: ↑ 19 Changed 4 years ago by
Replying to jmantysalo:
Replying to nadialafreniere:
  but the examples should also respect the python conventions. Therefore, I'm hoping to see a space after each of the commas.
Done this.
Everything looks fine!
comment:22 Changed 4 years ago by
 Branch changed from u/jmantysalo/faster_is_complemented to a9b0d3fa8f14e195040efc7e5e2623e8e631bedd
 Resolution set to fixed
 Status changed from positive_review to closed
Nathann, want an easy review?
New commits:
Faster is_complemented() for lattices.