Opened 2 years ago
Closed 22 months ago
#30840 closed enhancement (fixed)
small improvement in Hasse diagram
Reported by:  Frédéric Chapoton  Owned by:  

Priority:  major  Milestone:  sage9.3 
Component:  combinatorics  Keywords:  poset 
Cc:  Travis Scrimshaw  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  8459bf4 (Commits, GitHub, GitLab)  Commit:  8459bf421630778e1288d30a6ed10903575736e7 
Dependencies:  Stopgaps: 
Description (last modified by )
faster "are_comparable" and "are_incomparable" methods
and now with with a class for the (increasing) Chains in a poset.
BEFORE:
sage: P=posets.TamariLattice(5) sage: Q=posets.DexterSemilattice(3) sage: %timeit list(Q.chains()) 276 µs ± 664 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each) sage: %timeit list(Q.antichains()) 198 µs ± 670 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each) sage: %timeit list(P.chains()) 239 ms ± 630 µs per loop (mean ± std. dev. of 7 runs, 1 loop each) sage: %timeit list(P.antichains()) 395 ms ± 608 µs per loop (mean ± std. dev. of 7 runs, 1 loop each) sage: R=posets.CoxeterGroupAbsoluteOrderPoset(CoxeterGroup(['H',3])) sage: R Finite poset containing 120 elements sage: %timeit list(R.chains()) 256 ms ± 582 µs per loop (mean ± std. dev. of 7 runs, 1 loop each) sage: S=posets.IntegerPartitions(11) sage: %timeit list(S.antichains()) 243 ms ± 929 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
AFTER:
sage: P=posets.TamariLattice(5) sage: Q=posets.DexterSemilattice(3) sage: P Finite lattice containing 42 elements sage: Q Finite meetsemilattice containing 5 elements sage: %timeit list(Q.chains()) 137 µs ± 102 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) sage: %timeit list(Q.antichains()) 230 µs ± 48.7 µs per loop (mean ± std. dev. of 7 runs, 1 loop each) sage: %timeit list(P.chains()) 63.3 ms ± 97 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) sage: %timeit list(P.antichains()) 392 ms ± 938 µs per loop (mean ± std. dev. of 7 runs, 1 loop each) sage: R=posets.CoxeterGroupAbsoluteOrderPoset(CoxeterGroup(['H',3])) sage: %timeit list(R.chains()) 23.9 ms ± 70.1 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) sage: S=posets.IntegerPartitions(11) sage: %timeit list(S.antichains()) 235 ms ± 1.34 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Change History (20)
comment:1 Changed 2 years ago by
Branch:  → u/chapoton/30840 

Commit:  → bdd072c7f8a80c6ee8cc8de319c556f19cb62d33 
Status:  new → needs_review 
comment:2 Changed 2 years ago by
Commit:  bdd072c7f8a80c6ee8cc8de319c556f19cb62d33 → 15557a657c49f1e96532a6098f87987c8e369c8a 

Branch pushed to git repo; I updated commit sha1. New commits:
15557a6  make a class for Chains in posets

comment:3 Changed 2 years ago by
Description:  modified (diff) 

New commits:
15557a6  make a class for Chains in posets

comment:4 Changed 2 years ago by
Commit:  15557a657c49f1e96532a6098f87987c8e369c8a → 6ac14ffa3fb1ce02db4d16d3ac1cb6ed8d40b9bf 

Branch pushed to git repo; I updated commit sha1. New commits:
6ac14ff  remove one method

comment:5 Changed 2 years ago by
Keywords:  poset added 

comment:6 Changed 2 years ago by
Commit:  6ac14ffa3fb1ce02db4d16d3ac1cb6ed8d40b9bf → 200b93bbec93e4f26fcbf9a729403d8c92d18f4a 

Branch pushed to git repo; I updated commit sha1. New commits:
200b93b  adding doc to the new class for IncreasingChains

comment:7 Changed 2 years ago by
Description:  modified (diff) 

adding some before/after timings. Not so conclusive maybe ?
comment:9 Changed 2 years ago by
Cc:  Travis Scrimshaw added 

comment:11 Changed 23 months ago by
I think this is good. It seems like the timings get no worse (or perhaps slightly), but sometimes significantly better.
Some technical comments:
IncreasingChains
documentation is weird. I would move the __init__
docstring to the class level.
Why this removal?
 Eventually the following syntax will be accepted::

 sage: C.subset(size = 2) # todo: not implemented

You probably could get a little more speed out of the IncreasingChains
by type specifying variables. I am thinking for _vertices
and _greater_than
being lists (or even more specific for _vertices
, an array of Py_ssize_t
). I wonder slightly about the use of hash tables versus (ordered?) lists for the _greater_than
as the number of covers of an element tends to be relatively small compared to the number of elements in a poset. However, this isn't anything worth holding up this ticket for.
comment:12 Changed 23 months ago by
Commit:  200b93bbec93e4f26fcbf9a729403d8c92d18f4a → d1c542f3fbd6789a6be574897ad77cc8dba3072a 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
35fd884  small improvement in Hasse diagram

d327d4e  make a class for Chains in posets

9a80626  remove one method

f2b1bbf  adding doc to the new class for IncreasingChains

d1c542f  add some cdef in the IncreasingChains class methods

comment:13 Changed 23 months ago by
I have added some cdef in the methods.
Stupid me, but how to give types to attributes of the class when then class itself cannot be "cdef'ed" ?
comment:14 Changed 23 months ago by
Thank you for the changes.
Ah, I didn't notice that it was not an extension class. Actually, that is something we should change very soon by moving and making SearchForest
into the recursively_enumerated_set.pyx
... At least that aspect should be trivial: to move and cdef
the class.
Unfortunately I don't think you can do that. Although you can type cast it everywhere it could be useful.
Also, the IncreasingChains.__init__
now needs a doctest; a good old TestSuite(foo).run()
perhaps.
comment:15 Changed 23 months ago by
Commit:  d1c542f3fbd6789a6be574897ad77cc8dba3072a → 527d94d38db906c45c843557db988c2fdefe1bfd 

Branch pushed to git repo; I updated commit sha1. New commits:
527d94d  add a doctest for __init__ of increasing chains

comment:17 Changed 23 months ago by
Reviewers:  → Travis Scrimshaw 

Status:  needs_review → positive_review 
Yes, this is good. We can make further improvements later on.
comment:18 Changed 23 months ago by
Commit:  527d94d38db906c45c843557db988c2fdefe1bfd → 8459bf421630778e1288d30a6ed10903575736e7 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
8459bf4  Merge branch 'u/chapoton/30840' in 9.3.b1

comment:19 Changed 23 months ago by
Status:  needs_review → positive_review 

Thanks, Travis. Setting back to positive after a simple rebase.
comment:20 Changed 22 months ago by
Branch:  u/chapoton/30840 → 8459bf421630778e1288d30a6ed10903575736e7 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
small improvement in Hasse diagram