Posets: Slightly faster is_lattice()

[jmantysalo]

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

[jmantysalo]

New commits:

​48bd0ff

One line slight optimization.

[jmantysalo]

Nicolas? This one is quite trivial to review.

[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.

[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.

[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.

[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.

[git]

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

​46cf5a4

Added a check for 0-element poset.

[deinst]

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.

[git]

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

[git]

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

​cfbc7da

Faster is_lattice().

[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.

[jmantysalo]

All tests passed!

[deinst]

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

Everything looks good now.

[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.