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:

Status badges

Description (last modified by Andrew Mathas)

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 Andrew Mathas

Branch: u/andrew.mathas/making_disjointunionenumeratedsets_check_for_finiteenumeratedsets_when_category_is_not_set

comment:2 Changed 6 years ago by Andrew Mathas

Authors: Andrew Mathas
Cc: Sage Combinat CC user added
Commit: 951331c5127f7ff442be49ea25c5d918b1cfcd19
Component: PLEASE CHANGEcategories
Description: modified (diff)
Milestone: sage-7.3sage-7.4
Status: newneeds_review
Type: PLEASE CHANGEenhancement

New commits:

951331cChanging DisjointEnumerateSets when category is None

comment:3 Changed 6 years ago by Andrew Mathas

Description: modified (diff)

comment:4 Changed 5 years ago by Maarten Derickx

Reviewers: Maarten Derickx
Status: needs_reviewneeds_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 Andrew Mathas

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.

Note: See TracTickets for help on using tickets.