Faster meet() for lattice

[jm58660]

This trivial patch will speed up computation of meet matrix in lattices. Before:

sage: P = Posets.BooleanLattice(10)
sage: timeit("_ = P._hasse_diagram._meet", repeat=1, number=1)
1 loops, best of 1: 2.24 s per loop

After:

sage: P = Posets.BooleanLattice(10)
sage: timeit("_ = P._hasse_diagram._meet", repeat=1, number=1)
1 loops, best of 1: 917 ms per loop

And for small lattices:

sage: P10 = [P.with_bounds() for P in Posets(8)]
sage: timeit("len([P for P in P10 if P.is_meet_semilattice()])", repeat=1, number=1)

Without this patch it took 5.46 seconds, after the patch 1.54 seconds.

CC: @fchapoton

Component: combinatorics

Keywords: lattice poset

Author: Jori Mäntysalo

Branch/Commit: 965b8ab

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/21109

[jm58660]

Branch: u/jmantysalo/faster-meet

[jm58660]

Commit: b679b3d

[jm58660]

New commits:

b679b3d

Trivial speedup for meet().

[fchapoton]

comment:3

I have some questions:

I do not understand the comment # T = {x_i \wedge z : z>-x_k}
What is the meaning of >- ?

Does lc stands for "lower covers" ? if yes, that would be worth to say in a comment

Could you take the opportunity to make the method fully pep8 compliant ? only the line

raise ValueError("No meet for x=%s y=%s"%(x,y))

must be changed to

raise ValueError("No meet for x=%s y=%s" % (x, y))

[tscrim]

comment:4

Have you run tests on smaller and larger lattices? Does the about 2x speedup still hold in those cases?

[tscrim]

Changed keywords from latticeposet to lattice poset

[tscrim]

comment:5

If you haven't, just let me know, and I can run the tests.

[jm58660]

comment:7

Replying to @tscrim:

Have you run tests on smaller and larger lattices? Does the about 2x speedup still hold in those cases?

It is very hard to think an example where my code would be slower. This references to a python dict, whereas current code references to a matrix; referencing to matrix elements in a loop is slow. And that matrix must be precomputed first. You can test what happens if you compute le-matrix first (assuming that the user has, say, computed Möbius function matrix), but there will still be speedup.

I added another example to description.

[sagetrac-git]

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

965b8ab

Reviewer's comments.

[sagetrac-git]

Changed commit from b679b3d to 965b8ab

[jm58660]

comment:9

Replying to @fchapoton:

Could you take the opportunity to make the method fully pep8 compliant ? only the line

raise ValueError("No meet for x=%s y=%s"%(x,y))

must be changed to

raise ValueError("No meet for x=%s y=%s" % (x, y))

Changed. Then there is the error message formatting question... Python exceptions start with lowercase and do not end to a period. But this has been discussed in sage-devel without clear conclusion.

I do not understand the comment # T = {x_i \wedge z : z>-x_k}
What is the meaning of >- ?

I guess it has meant covering. I removed it.

Does lc stands for "lower covers" ? if yes, that would be worth to say in a comment

Done.

[jm58660]

comment:10

rc0 is out.

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

comment:11

ok, looks good enough. Thanks

[vbraun]

Changed branch from u/jmantysalo/faster-meet to 965b8ab