Opened 4 years ago

Closed 4 years ago

#19161 closed enhancement (fixed)

LatticePoset: faster is_complemented()

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-6.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 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.

Change History (22)

comment:1 Changed 4 years ago by jmantysalo

  • Branch set to u/jmantysalo/faster_is_complemented

comment:2 Changed 4 years ago by jmantysalo

  • Commit set to bf8fdd5dd0702a6158691183ac6a3351461a650e
  • Status changed from new to needs_review

Nathann, want an easy review?


New commits:

bf8fdd5Faster is_complemented() for lattices.

comment:3 Changed 4 years ago by jmantysalo

  • Description modified (diff)

comment:4 follow-up: Changed 4 years ago by ncohen

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==n-1:
            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 ; follow-up: Changed 4 years ago by jmantysalo

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 matrix-based 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 ncohen

It depends. For B10-example your algorithm is clearly faster, it takes about half of the time of matrix-based 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.

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 follow-up: Changed 4 years ago by jmantysalo

That was fast to test. Matrix-based 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 ; follow-up: Changed 4 years ago by ncohen

That was fast to test. Matrix-based 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 git

  • Commit changed from bf8fdd5dd0702a6158691183ac6a3351461a650e to b8853ed85f14cb8b3d2a9046d31505bf81223c7d

Branch pushed to git repo; I updated commit sha1. New commits:

b8853edFaster algorithm, thanks to Nathann Cohen.

comment:10 in reply to: ↑ 8 Changed 4 years ago by jmantysalo

  • Authors changed from Jori Mäntysalo to Nathann Cohen, Jori Mäntysalo
  • Cc mlapointe added
  • Description modified (diff)

Replying to ncohen:

That was fast to test. Matrix-based 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 "matrix-based", 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 follow-up: Changed 4 years ago by ncohen

HMmmmm... Factor 6?... O_o

Weird, weird... :-/

comment:12 in reply to: ↑ 11 Changed 4 years ago by jmantysalo

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 follow-up: Changed 4 years ago by nadialafreniere

  • 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#python-code-style

comment:14 Changed 4 years ago by git

  • Commit changed from b8853ed85f14cb8b3d2a9046d31505bf81223c7d to ec6f18a7290517028a45f216f4b6ae90a3157f7c

Branch pushed to git repo; I updated commit sha1. New commits:

ec6f18aReviewers comment about Python conventions.

comment:15 in reply to: ↑ 13 Changed 4 years ago by jmantysalo

  • 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 follow-up: Changed 4 years ago by nadialafreniere

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 nadialafreniere

  • Status changed from needs_review to needs_work

comment:18 Changed 4 years ago by git

  • Commit changed from ec6f18a7290517028a45f216f4b6ae90a3157f7c to a9b0d3fa8f14e195040efc7e5e2623e8e631bedd

Branch pushed to git repo; I updated commit sha1. New commits:

a9b0d3fSpaces to examples of is_complemented_lattice().

comment:19 in reply to: ↑ 16 ; follow-up: Changed 4 years ago by jmantysalo

  • 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 nadialafreniere

  • 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 nadialafreniere

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 vbraun

  • Branch changed from u/jmantysalo/faster_is_complemented to a9b0d3fa8f14e195040efc7e5e2623e8e631bedd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.