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: sage-7.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 jmantysalo)

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 jmantysalo

  • Description modified (diff)
  • Type changed from enhancement to defect

comment:2 Changed 4 years ago by jmantysalo

  • Branch set to u/jmantysalo/finite_posets__faster_is_antichain_of_poset__

comment:3 Changed 4 years ago by jmantysalo

  • Commit set to 38400a3da6f9d4885f0b36cd2169cc5c14b0142c

After P = Posets.BooleanLattice(10); l = P.level_sets()[5] this patch reduced time for P.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 both is_chain_of_poset() and is_antichain_of_poset() are defined in the same file. Also the user will get error message always, if there is an element of elms not in the poset.

The code may seem slightly odd, but AFAIK there is no built-in way in Python to get pairs (a,b) from list L such that L.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:

6bd3062Added a function is_antichain_of_poset to posets.py.
38400a3Removed spaces from empty line.

comment:4 Changed 3 years ago by git

  • Commit changed from 38400a3da6f9d4885f0b36cd2169cc5c14b0142c to fcde384f50a6535ee3608e9b59eb0e067f2e4dbe

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

4ac4893Better check for antichain of poset.
fcde384Remove a space.

comment:5 Changed 3 years ago by jmantysalo

  • Milestone changed from sage-6.9 to sage-7.5
  • Status changed from new to needs_review

comment:6 follow-up: Changed 3 years ago by tscrim

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 ; follow-up: Changed 3 years ago by 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']) (where 2<3 in the poset) a bug or a good short-circuit 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 jmantysalo

Just pinging.

comment:9 Changed 3 years ago by kdilks

  • Cc kdilks added

comment:10 in reply to: ↑ 7 ; follow-up: Changed 3 years ago by tscrim

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']) (where 2<3 in the poset) a bug or a good short-circuit 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 and is_chain_of_poset. Better to have is_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 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']) (where 2<3 in the poset) a bug or a good short-circuit 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).

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 follow-up: Changed 3 years ago by tscrim

Ah, I see what you mean by short-circuit 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 ; follow-up: Changed 3 years ago by jmantysalo

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/or is_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 sage-devel.

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 jmantysalo

  • Status changed from needs_review to needs_info

comment:15 in reply to: ↑ 13 Changed 3 years ago by jmantysalo

Replying to jmantysalo:

I'll write to sage-devel.

This done, but we got only one answer. It voted for raising an exception. Should we proceed with that ("vote" 2-1), or ask for more opinions?

comment:16 follow-up: Changed 3 years ago by 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.

comment:17 Changed 3 years ago by git

  • Commit changed from fcde384f50a6535ee3608e9b59eb0e067f2e4dbe to ee10a610ab6be38a168d91ba81c1747be2d3570d

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

8486510Better check for antichain of poset.
bae3d8eRemove a space.
ee10a61Merge remote-tracking 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 jmantysalo

  • 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 tscrim

  • 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 vbraun

  • 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
Note: See TracTickets for help on using tickets.