Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Faster join() for lattice #21882

Closed
jm58660 mannequin opened this issue Nov 16, 2016 · 6 comments
Closed

Faster join() for lattice #21882

jm58660 mannequin opened this issue Nov 16, 2016 · 6 comments
Labels
c: combinatorics p: major / 3 t: enhancement
Milestone
sage-7.5

Comments

@jm58660
Copy link
Mannequin

jm58660 mannequin commented Nov 16, 2016

This patch will speed up computation of join matrix in lattices. On 1024-element Boolean lattice

H = Posets.BooleanLattice(10).hasse_diagram()
H.relabel(lambda x: x+1)  # To clear possible caches.
P = Poset(H)

Before/after the patch:

1 loops, best of 1: 2.86 s per loop
1 loops, best of 1: 1.23 s per loop

Time to count join-semilattices from all 9-element bounded posets drops from 710 ms to 278 ms.

CC: @tscrim

Component: combinatorics

Author: Jori Mäntysalo

Branch/Commit: 672cee2

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/21882
@jm58660 jm58660 mannequin added this to the sage-7.5 milestone Nov 16, 2016
@jm58660 jm58660 mannequin added c: combinatorics labels Nov 16, 2016
@jm58660
Copy link
Mannequin Author

jm58660 mannequin commented Nov 16, 2016

Branch: u/jmantysalo/faster-join

@jm58660
Copy link
Mannequin Author

jm58660 mannequin commented Nov 16, 2016

comment:2

Basically same change as in #21109.

New commits:

672cee2Faster join().

@jm58660
Copy link
Mannequin Author

jm58660 mannequin commented Nov 16, 2016

Commit: 672cee2

@jm58660 jm58660 mannequin added the s: needs review label Nov 16, 2016
@tscrim
Copy link
Collaborator

tscrim commented Nov 16, 2016

comment:3

LGTM.

@tscrim
Copy link
Collaborator

tscrim commented Nov 16, 2016

Reviewer: Travis Scrimshaw

@vbraun
Copy link
Member

vbraun commented Nov 17, 2016

Changed branch from u/jmantysalo/faster-join to 672cee2

@vbraun vbraun closed this as completed in 6df171b Nov 17, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: combinatorics p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-7.5
Development

No branches or pull requests
2 participants
@vbraun @tscrim