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: sage-9.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:

Status badges

Description (last modified by Frédéric Chapoton)

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 meet-semilattice 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 Frédéric Chapoton

Branch: u/chapoton/30840
Commit: bdd072c7f8a80c6ee8cc8de319c556f19cb62d33
Status: newneeds_review

New commits:

bdd072csmall improvement in Hasse diagram

comment:2 Changed 2 years ago by git

Commit: bdd072c7f8a80c6ee8cc8de319c556f19cb62d3315557a657c49f1e96532a6098f87987c8e369c8a

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

15557a6make a class for Chains in posets

comment:3 Changed 2 years ago by Frédéric Chapoton

Description: modified (diff)

New commits:

15557a6make a class for Chains in posets

comment:4 Changed 2 years ago by git

Commit: 15557a657c49f1e96532a6098f87987c8e369c8a6ac14ffa3fb1ce02db4d16d3ac1cb6ed8d40b9bf

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

6ac14ffremove one method

comment:5 Changed 2 years ago by Frédéric Chapoton

Keywords: poset added

comment:6 Changed 2 years ago by git

Commit: 6ac14ffa3fb1ce02db4d16d3ac1cb6ed8d40b9bf200b93bbec93e4f26fcbf9a729403d8c92d18f4a

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

200b93badding doc to the new class for IncreasingChains

comment:7 Changed 2 years ago by Frédéric Chapoton

Description: modified (diff)

adding some before/after timings. Not so conclusive maybe ?

comment:8 Changed 2 years ago by Frédéric Chapoton

Description: modified (diff)

more timings

comment:9 Changed 2 years ago by Frédéric Chapoton

Cc: Travis Scrimshaw added

comment:10 Changed 23 months ago by Frédéric Chapoton

bot is morally green. Any opinion ?

comment:11 Changed 23 months ago by Travis Scrimshaw

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 git

Commit: 200b93bbec93e4f26fcbf9a729403d8c92d18f4ad1c542f3fbd6789a6be574897ad77cc8dba3072a

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

35fd884small improvement in Hasse diagram
d327d4emake a class for Chains in posets
9a80626remove one method
f2b1bbfadding doc to the new class for IncreasingChains
d1c542fadd some cdef in the IncreasingChains class methods

comment:13 Changed 23 months ago by Frédéric Chapoton

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 Travis Scrimshaw

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 git

Commit: d1c542f3fbd6789a6be574897ad77cc8dba3072a527d94d38db906c45c843557db988c2fdefe1bfd

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

527d94dadd a doctest for __init__ of increasing chains

comment:16 Changed 23 months ago by Frédéric Chapoton

ok, then here is the missing doctest. Maybe good to go ?

comment:17 Changed 23 months ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

Yes, this is good. We can make further improvements later on.

comment:18 Changed 23 months ago by git

Commit: 527d94d38db906c45c843557db988c2fdefe1bfd8459bf421630778e1288d30a6ed10903575736e7
Status: positive_reviewneeds_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

8459bf4Merge branch 'u/chapoton/30840' in 9.3.b1

comment:19 Changed 23 months ago by Frédéric Chapoton

Status: needs_reviewpositive_review

Thanks, Travis. Setting back to positive after a simple rebase.

comment:20 Changed 22 months ago by Volker Braun

Branch: u/chapoton/308408459bf421630778e1288d30a6ed10903575736e7
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.