Opened 4 years ago
Closed 3 years ago
#19078 closed defect (fixed)
Finite posets: Faster is_antichain_of_poset()
Reported by:  jmantysalo  Owned by:  

Priority:  minor  Milestone:  sage7.5 
Component:  combinatorics  Keywords:  
Cc:  kdilks  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  ee10a61 (Commits)  Commit:  ee10a610ab6be38a168d91ba81c1747be2d3570d 
Dependencies:  Stopgaps: 
Description (last modified by )
Implementation in the category of posets works but is unoptimal for finite posets. It compares every pair of elements twice, using only le()
function.
Also there is a slight bug:
P = Posets.PentagonPoset() print P.is_antichain_of_poset([2,3,'junk']) print P.is_antichain_of_poset(['junk',2,3])
Prints False
and then gives an error.
Change History (20)
comment:1 Changed 4 years ago by
 Description modified (diff)
 Type changed from enhancement to defect
comment:2 Changed 4 years ago by
 Branch set to u/jmantysalo/finite_posets__faster_is_antichain_of_poset__
comment:3 Changed 4 years ago by
 Commit set to 38400a3da6f9d4885f0b36cd2169cc5c14b0142c
comment:4 Changed 3 years ago by
 Commit changed from 38400a3da6f9d4885f0b36cd2169cc5c14b0142c to fcde384f50a6535ee3608e9b59eb0e067f2e4dbe
comment:5 Changed 3 years ago by
 Milestone changed from sage6.9 to sage7.5
 Status changed from new to needs_review
comment:6 followup: ↓ 7 Changed 3 years ago by
Are you also saying that there is a bug in the category version of is_antichain_of_poset
? (I think we should also remove the _of_poset
; it is redundant to have in the method name...)
comment:7 in reply to: ↑ 6 ; followup: ↓ 10 Changed 3 years ago by
Replying to tscrim:
Are you also saying that there is a bug in the category version of
is_antichain_of_poset
?
It depends. Do you consider P.is_antichain_of_poset([2,3,'junk'])
(where 2<3
in the poset) a bug or a good shortcircuit evaluation?
(I think we should also remove the
_of_poset
; it is redundant to have in the method name...)
Nope, we already have is_chain
and is_chain_of_poset
. Better to have is_antichain_of_poset
for symmetry.
comment:8 Changed 3 years ago by
Just pinging.
comment:9 Changed 3 years ago by
 Cc kdilks added
comment:10 in reply to: ↑ 7 ; followup: ↓ 11 Changed 3 years ago by
Replying to jmantysalo:
Replying to tscrim:
Are you also saying that there is a bug in the category version of
is_antichain_of_poset
?It depends. Do you consider
P.is_antichain_of_poset([2,3,'junk'])
(where2<3
in the poset) a bug or a good shortcircuit evaluation?
I would want that to return False
since that is not an antichain of the poset, but I know some people agree that it would be a bug (see the is_similar
discussion).
(I think we should also remove the
_of_poset
; it is redundant to have in the method name...)Nope, we already have
is_chain
andis_chain_of_poset
. Better to haveis_antichain_of_poset
for symmetry.
Good point, and it already exists in the category.
comment:11 in reply to: ↑ 10 Changed 3 years ago by
Replying to tscrim:
Are you also saying that there is a bug in the category version of
is_antichain_of_poset
?It depends. Do you consider
P.is_antichain_of_poset([2,3,'junk'])
(where2<3
in the poset) a bug or a good shortcircuit evaluation?I would want that to return
False
since that is not an antichain of the poset, but I know some people agree that it would be a bug (see theis_similar
discussion).
At least then P.is_antichain_of_poset(['junk',2,3])
should also return False
, not raise an exception. And for example is_induced_subposet()
raises exception in similar situation.
I guess for this one we have no common view and so this can be closed as wontfix, but I'll wait for a week or two if others have more opinions.
comment:12 followup: ↓ 13 Changed 3 years ago by
Ah, I see what you mean by shortcircuit now. I think the bet behavior going forward is to catch this exception and return False
. We can change the behavior of this function and/or is_induced_subposet
to make things more globally consistent on a separate ticket. At least this will make is_antichain_of_poset
locally consistent.
Also, we definitely do not want this to be a wontfix because there is a definite improvement in the speed.
comment:13 in reply to: ↑ 12 ; followup: ↓ 15 Changed 3 years ago by
Replying to tscrim:
I think the bet behavior going forward is to catch this exception and return
False
. We can change the behavior of this function and/oris_induced_subposet
to make things more globally consistent on a separate ticket.
We have a clear disagreement here. I want to change this to be like is_induced_subposet
, you want just the opposite.
I'll write to sagedevel.
Also, we definitely do not want this to be a wontfix because there is a definite improvement in the speed.
OK. It's not actually very big, as even the current version is fast.
comment:14 Changed 3 years ago by
 Status changed from needs_review to needs_info
comment:15 in reply to: ↑ 13 Changed 3 years ago by
Replying to jmantysalo:
I'll write to sagedevel.
This done, but we got only one answer. It voted for raising an exception. Should we proceed with that ("vote" 21), or ask for more opinions?
comment:16 followup: ↓ 18 Changed 3 years ago by
I can deal with it raising an exception, but note it will also slow things down for shortcut failures as it must check that every input object is equal to something in the poset.
comment:17 Changed 3 years ago by
 Commit changed from fcde384f50a6535ee3608e9b59eb0e067f2e4dbe to ee10a610ab6be38a168d91ba81c1747be2d3570d
Branch pushed to git repo; I updated commit sha1. New commits:
8486510  Better check for antichain of poset.

bae3d8e  Remove a space.

ee10a61  Merge remotetracking branch 'refs/remotes/trac/u/jmantysalo/finite_posets__faster_is_antichain_of_poset__' into t/19078/finite_posets__faster_is_antichain_of_poset__

comment:18 in reply to: ↑ 16 Changed 3 years ago by
 Status changed from needs_info to needs_review
Replying to tscrim:
I can deal with it raising an exception, but note it will also slow things down for shortcut failures as it must check that every input object is equal to something in the poset.
True, but other possibility is worst, as it can pass some errors unnoticed.
I rebased this, ready for review.
comment:19 Changed 3 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
For the record, I only believe it may sometimes be a logical error.
However, I'm setting this to a positive review because the speed improvements are good.
comment:20 Changed 3 years ago by
 Branch changed from u/jmantysalo/finite_posets__faster_is_antichain_of_poset__ to ee10a610ab6be38a168d91ba81c1747be2d3570d
 Resolution set to fixed
 Status changed from positive_review to closed
After
P = Posets.BooleanLattice(10); l = P.level_sets()[5]
this patch reduced time forP.is_antichain_of_poset(l)
from 642 ms to 558 ms. That is 13% faster.At the same time the index in
posets.py
can be slightly better, as now bothis_chain_of_poset()
andis_antichain_of_poset()
are defined in the same file. Also the user will get error message always, if there is an element ofelms
not in the poset.The code may seem slightly odd, but AFAIK there is no builtin way in Python to get pairs
(a,b)
from listL
such thatL.index(a) < L.index(b)
. This implementation was fastest I found.However, I am waiting for #18941 to get accepted (or rejected). Then I'll add this to index of functions. (Assuming that #19061 isn't done yet.)
New commits:
Added a function is_antichain_of_poset to posets.py.
Removed spaces from empty line.