#20669 closed enhancement (fixed)
LatticePoset: add function to get all sublattices
Reported by: | jmantysalo | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.3 |
Component: | combinatorics | Keywords: | lattice poset, days78 |
Cc: | tscrim | Merged in: | |
Authors: | Jori Mäntysalo | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | 1bb87bd (Commits, GitHub, GitLab) | Commit: | |
Dependencies: | Stopgaps: |
Description
This patch will add a function that gives all sublattices of a lattice.
Change History (16)
comment:1 Changed 5 years ago by
- Branch set to u/jmantysalo/all_sublattices
comment:2 Changed 5 years ago by
- Cc tscrim added
- Commit set to 1bb87bd775eece24a586b9ccedb7dfd6ca0b5488
- Status changed from new to needs_review
comment:3 follow-up: ↓ 4 Changed 5 years ago by
- Reviewers set to Travis Scrimshaw
- Status changed from needs_review to needs_work
I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like self.cardinality()
), never run up against the Python maximum recursion limit, and have better input (which set()
and 0
should be defaults anyways).
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 5 years ago by
Replying to tscrim:
I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like
self.cardinality()
), never run up against the Python maximum recursion limit, and have better input (whichset()
and0
should be defaults anyways).
Maximun recursion limit is 999 by default, and that is too small only if we have a ChainPoset(n)
with n > 999
; recursion stack will have at most as many steps as the lattice has elements. And it will have 2^999
sublattices anyway, so this is not valid argument.
For example after B4 = Posets.BooleanLattice(4)
it takes 0,02 seconds to count 732 sublattices with len(list(B4._hasse_diagram.sublattices_iterator(set(), 0)))
, whereas it took 1,13 seconds with len(B4.sublattices())
. So if one wants to optimize lattices, then bottleneck is usually not in hasse_diagram.py
but in lattices.py
.
Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 5 years ago by
Replying to jmantysalo:
Replying to tscrim:
I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like
self.cardinality()
), never run up against the Python maximum recursion limit, and have better input (whichset()
and0
should be defaults anyways).Maximun recursion limit is 999 by default, and that is too small only if we have a
ChainPoset(n)
withn > 999
; recursion stack will have at most as many steps as the lattice has elements. And it will have2^999
sublattices anyway, so this is not valid argument.
People could want to do some partial tests on some really big example of a lattice or wanted to run a month-long-type computation on a big lattice (of which, there are a number of examples of finite exceptional cases that I come across in my research where the easiest way to prove things can be to do long computations).
For example after
B4 = Posets.BooleanLattice(4)
it takes 0,02 seconds to count 732 sublattices withlen(list(B4._hasse_diagram.sublattices_iterator(set(), 0)))
, whereas it took 1,13 seconds withlen(B4.sublattices())
. So if one wants to optimize lattices, then bottleneck is usually not inhasse_diagram.py
but inlattices.py
.
I don't disagree with this, but you should not be creating the lattice by using the LatticePoset
but directly creating the necessary data and passing it to FiniteLatticePoset
. This avoids the extra overhead and checks that is in the Poset
code.
Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?
I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?
comment:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 5 years ago by
Replying to tscrim:
Replying to jmantysalo:
Replying to tscrim:
I think you should use a backtracking algorithm instead of a recursion. It will be faster (and you don't have to constantly get things like
self.cardinality()
), never run up against the Python maximum recursion limit, and have better input (whichset()
and0
should be defaults anyways).Maximun recursion limit is 999 by default, and that is too small only if we have a
ChainPoset(n)
withn > 999
; recursion stack will have at most as many steps as the lattice has elements. And it will have2^999
sublattices anyway, so this is not valid argument.
People could want to do some partial tests on some really big example of a lattice or wanted to run a month-long-type computation on a big lattice (of which, there are a number of examples of finite exceptional cases that I come across in my research where the easiest way to prove things can be to do long computations).
Well, now it took only 20 seconds to make ChainPoset(1000)
. So yes, it is theoretically possible to run this kind of computations. But then, recursion limit can be changed.
Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?
I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?
No, but that could be added. Or actually copied from current file. For Frattini sublattices that would actually make sense.
---
Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?
comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 5 years ago by
Replying to jmantysalo:
Replying to tscrim:
Replying to jmantysalo:
Of course I can change this to use backtracking, but... Then why not move this to static sparce graphs class, if we really want as fast code as possible?
I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?
No, but that could be added. Or actually copied from current file. For Frattini sublattices that would actually make sense.
However, meet and join doesn't quite make sense to have it there mathematically AFAIK. Although by cythonizing hasse_diagram.py
, we should get most of possible speed without doing really much in the way of changes.
Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?
I am going to treat this as you telling me your process for reviewing. Otherwise I would take that a very insulting comment to me which you are telling me how to do my review.
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 5 years ago by
Replying to tscrim:
I have no inherent objects to this, but does the static sparse digraph code have the capacity to do the meet and joins?
No, but that could be added.
However, meet and join doesn't quite make sense to have it there mathematically AFAIK. Although by cythonizing
hasse_diagram.py
, we should get most of possible speed without doing really much in the way of changes.
True, but I think that there was obstackle for cythonizing. Something with inheritance, I think; I discussed about this with Nathann Cohen maybe a two years ago.
Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?
I am going to treat this as you telling me your process for reviewing. Otherwise I would take that a very insulting comment to me which you are telling me how to do my review.
Sorry. I don't intend to insult. (But also I does not so much english words to make my expressions smoother.)
I was just trying to say what developer guide says: "Please refrain from additional feature requests or open-ended discussion about alternative implementations."
comment:9 in reply to: ↑ 8 ; follow-up: ↓ 10 Changed 5 years ago by
Replying to jmantysalo:
Replying to tscrim:
However, meet and join doesn't quite make sense to have it there mathematically AFAIK. Although by cythonizing
hasse_diagram.py
, we should get most of possible speed without doing really much in the way of changes.True, but I think that there was obstackle for cythonizing. Something with inheritance, I think; I discussed about this with Nathann Cohen maybe a two years ago.
I don't see anything that would prevent a cythonization; the HasseDiagram
class only has single inheritance (and cython probably has improved since when you discussed this).
Basic questions about all reviews: 1) Is Sage better with this or without? 2) If with, is there some easy steps to make it still better?
I am going to treat this as you telling me your process for reviewing. Otherwise I would take that a very insulting comment to me which you are telling me how to do my review.
Sorry. I don't intend to insult. (But also I does not so much english words to make my expressions smoother.)
I know you didn't, but it first seemed like you were trying to tell me how to review this. My reply was condescending, to which I apologize as well.
I was just trying to say what developer guide says: "Please refrain from additional feature requests or open-ended discussion about alternative implementations."
I don't think we are in an open-ended discussion because I am proposing a (single) concrete/explicit alternative implementation. While I am not strictly opposed to the current implementation, I think there is a relatively easy way to improve it. I might have some time to change the algorithm today, if you're okay with it (I'm on French time for this week and the next).
comment:10 in reply to: ↑ 9 Changed 5 years ago by
Replying to tscrim:
I might have some time to change the algorithm today, if you're okay with it (I'm on French time for this week and the next).
Of course. I can review it then, and hopefully you can check docstrings I wrote.
comment:11 Changed 5 years ago by
Just pinging...
comment:12 Changed 5 years ago by
ping
.
comment:13 Changed 5 years ago by
- Status changed from needs_work to positive_review
So, I just haven't had time to do the algorithm change that I wanted. This works as claimed (although I was not able to completely prove its correctness). Thus this works as a first implementation, and so positive review (I can change it to a backtrak on a follow-up ticket if and when I have more time).
PS - Sorry it took so long.
comment:14 Changed 5 years ago by
Thanks Travis!
Here is the followup: #20921.
comment:15 Changed 5 years ago by
- Branch changed from u/jmantysalo/all_sublattices to 1bb87bd775eece24a586b9ccedb7dfd6ca0b5488
- Resolution set to fixed
- Status changed from positive_review to closed
comment:16 Changed 5 years ago by
- Commit 1bb87bd775eece24a586b9ccedb7dfd6ca0b5488 deleted
- Keywords lattice poset days78 added; latticeposet removed
Travis selected as a random victim for review.
New commits:
Add sublattices().