Opened 7 years ago

Closed 7 years ago

#18760 closed enhancement (fixed)

Posets: Slightly faster is_lattice()

Reported by: jmantysalo Owned by:
Priority: minor Milestone: sage-6.9
Component: combinatorics Keywords: posets
Cc: nthiery Merged in:
Authors: Jori Mäntysalo Reviewers: David Einstein
Report Upstream: N/A Work issues:
Branch: cfbc7da (Commits, GitHub, GitLab) Commit: cfbc7daccfee560158f7d52a9aa0e00dfeb7d868
Dependencies: Stopgaps:

Status badges

Description

Finite join-semilattice with bottom element is a lattice. (Resp. meet-semilattice with top element.)

Change History (16)

comment:1 Changed 7 years ago by jmantysalo

  • Branch set to u/jmantysalo/posets__slightly_faster_is_lattice__

comment:2 Changed 7 years ago by jmantysalo

  • Commit set to 48bd0ff4c629af3002fb5f1dc7d926963ef2a057
  • Status changed from new to needs_review

New commits:

48bd0ffOne line slight optimization.

comment:3 Changed 7 years ago by jmantysalo

  • Cc nthiery added

Nicolas? This one is quite trivial to review.

comment:4 follow-up: Changed 7 years ago by deinst

This breaks the tests in poset_examples.py, because the empty poset is a lattice but has no bottom. I'm not sure that special casing the empty poset is worth the less than factor of two speedup.

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

Replying to deinst:

This breaks the tests in poset_examples.py, because the empty poset is a lattice but has no bottom. I'm not sure that special casing the empty poset is worth the less than factor of two speedup.

True, thanks for noticing that. I'll make a fix.

Speedup should be quite near to two if the poset happen to be a lattice. For me it is enought to add about 50 characters to source.

comment:6 in reply to: ↑ 5 Changed 7 years ago by deinst

Replying to jmantysalo:

Replying to deinst:

This breaks the tests in poset_examples.py, because the empty poset is a lattice but has no bottom. I'm not sure that special casing the empty poset is worth the less than factor of two speedup.

True, thanks for noticing that. I'll make a fix.

Speedup should be quite near to two if the poset happen to be a lattice. For me it is enought to add about 50 characters to source.

Please provide some measurements to back up your intuition. I suspect that you are probably correct, but it is worth measuring.

comment:7 Changed 7 years ago by jmantysalo

After P8=Posets(8).list() time for

len([L for L in P8 if L.is_lattice()])

drop from 1,36 seconds to 0,63 seconds (factor more than two, which should not happen, but I guess it is random noise). And after

P=Posets.BooleanLattice(10)
P1=Poset(P)

time for

P1.is_lattice()

drops from 5,91 to 3,84 seconds.

comment:8 Changed 7 years ago by git

  • Commit changed from 48bd0ff4c629af3002fb5f1dc7d926963ef2a057 to 46cf5a4fa8775ba1fdcb9d6042d16a14092032e1

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

46cf5a4Added a check for 0-element poset.

comment:9 follow-up: Changed 7 years ago by deinst

  • Status changed from needs_review to needs_work

Please, please, please, please run make ptestlong or make testlong before submitting something for review, no matter how trivial the change. The heat death of the universe is progressing just fine by itself. In other words you are missing a pair of parentheses after cardinality.

The fact that it runs slightly faster than twice as fast on average for all posets of size 8 is surprising at first but not unexpected we are much faster on those posets with a bottom but no top, about the same (but very fast) for the ones with no bottom and about as fast to twice as fast for the ones with both.

comment:10 Changed 7 years ago by git

  • Commit changed from 46cf5a4fa8775ba1fdcb9d6042d16a14092032e1 to 7eb8510dacf61b691664cd8f1d2e75e5d473e5a0

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

comment:11 Changed 7 years ago by git

  • Commit changed from 7eb8510dacf61b691664cd8f1d2e75e5d473e5a0 to cfbc7daccfee560158f7d52a9aa0e00dfeb7d868

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

cfbc7daFaster is_lattice().

comment:12 in reply to: ↑ 9 Changed 7 years ago by jmantysalo

Replying to deinst:

are missing a pair of parentheses after cardinality.

Some days I think I should flush myself down the toilet.

I did the change with () and ran (short) tests. Then I happen to crash something and had to re-did the oneliner. And I forget the parenthesis.

Please, please, please, please run make ptestlong or make testlong before submitting something for review, no matter how trivial the change.

Does it differ from sage -t -a --long? Anyways, I am now running make ptestlong and will mark this as needs_review after that.

There were some strange errors in compiling, maybe because of new version of Sage as a base. This is now pushed with git -f.

The fact that it runs slightly faster than twice as fast on average for all posets of size 8 is surprising at first but not unexpected we are much faster on those posets with a bottom but no top, about the same (but very fast) for the ones with no bottom and about as fast to twice as fast for the ones with both.

True. Of course this means nothing until we get #14110 and #17147 done.

comment:13 Changed 7 years ago by jmantysalo

  • Milestone changed from sage-6.8 to sage-6.9
  • Status changed from needs_work to needs_review

All tests passed!

comment:14 follow-up: Changed 7 years ago by deinst

  • Reviewers set to David Einstein
  • Status changed from needs_review to positive_review

Sorry for being snarky, I was having a bad day.

Everything looks good now.

comment:15 in reply to: ↑ 14 Changed 7 years ago by jmantysalo

Replying to deinst:

Sorry for being snarky, I was having a bad day.

Nothing to be sorry about. Better a co-developer to complain before change than a user to complain after.

comment:16 Changed 7 years ago by vbraun

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