Opened 6 years ago
Last modified 5 years ago
#21218 needs_work enhancement
Making DisjointUnionEnumeratedSets check for FiniteEnumeratedSets when category is not set
Reported by: | Andrew Mathas | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.4 |
Component: | categories | Keywords: | |
Cc: | Sage Combinat CC user | Merged in: | |
Authors: | Andrew Mathas | Reviewers: | Maarten Derickx |
Report Upstream: | N/A | Work issues: | |
Branch: | u/andrew.mathas/making_disjointunionenumeratedsets_check_for_finiteenumeratedsets_when_category_is_not_set (Commits, GitHub, GitLab) | Commit: | 951331c5127f7ff442be49ea25c5d918b1cfcd19 |
Dependencies: | Stopgaps: |
Description (last modified by )
The __init__
method for DisjointEnumeratedSets
contains the following lines:
if category is None: # try to guess if the result is infinite or not. if self._family in InfiniteEnumeratedSets(): category = InfiniteEnumeratedSets() elif self._family.last().cardinality() == Infinity: category = InfiniteEnumeratedSets() else: category = FiniteEnumeratedSets()
For some finite enumerated sets the only way to determine their cardinality is to generate all of the elements and count, so the elif
branch is potentially quite slow. It seems to me that it is better to write
if category is None: # try to guess if the result is infinite or not. if self._family in InfiniteEnumeratedSets(): category = InfiniteEnumeratedSets() elif self._family in FiniteEnumeratedSets(): category = FiniteEnumeratedSets() elif self._family.last().cardinality() == Infinity: category = InfiniteEnumeratedSets() else: category = FiniteEnumeratedSets()
This change does not break anything, should speed some things up and it was the source of a bug that I have just spent some time hunting for. Arguably, the self._family.last().cardinality() == Infinity
could be removed.
Of course, if the category is given explicitly then this issue does not arise but I always thought that part of the point of such constructs is not to have to do this.
Change History (5)
comment:1 Changed 6 years ago by
Branch: | → u/andrew.mathas/making_disjointunionenumeratedsets_check_for_finiteenumeratedsets_when_category_is_not_set |
---|
comment:2 Changed 6 years ago by
Authors: | → Andrew Mathas |
---|---|
Cc: | Sage Combinat CC user added |
Commit: | → 951331c5127f7ff442be49ea25c5d918b1cfcd19 |
Component: | PLEASE CHANGE → categories |
Description: | modified (diff) |
Milestone: | sage-7.3 → sage-7.4 |
Status: | new → needs_review |
Type: | PLEASE CHANGE → enhancement |
comment:3 Changed 6 years ago by
Description: | modified (diff) |
---|
comment:4 Changed 5 years ago by
Reviewers: | → Maarten Derickx |
---|---|
Status: | needs_review → needs_work |
The family being a finite enumerated set is not enough to guarantee that the disjoint union is finite. For example without this branch we have
sage: F = Family(range(10), lambda i: ZZ) sage: D = DisjointUnionEnumeratedSets(F) sage: F in FiniteEnumeratedSets() True sage: D in InfiniteEnumeratedSets() True sage: D.cardinality() +Infinity
but your patch will change this!!!
Actually the current code is also already buggy since just checking wether family.last() is infinite or not is not enough!
sage: F = Family(range(10), lambda i: ZZ if i==0 else Set([])) sage: D in FiniteEnumeratedSets() False sage: F = Family(range(10), lambda i: ZZ if i==0 else Set([])) sage: D = DisjointUnionEnumeratedSets(F) sage: D in FiniteEnumeratedSets() True sage: D.cardinality() +Infinity
So a correct implementation should check wether all elements in the union are finite and make a FiniteEnumeratedSet? in this case and otherwise make an InfiniteEnumeratedSet?
comment:5 Changed 5 years ago by
As you say the current implementation is buggy, but this ticket has been sitting here for over a year without any one looking at it, so my motivation for working on this is low -- and in any case I can't at the moment because sage won't compile on my computer due to a skylake issue.
New commits:
Changing DisjointEnumerateSets when category is None