#5308 closed enhancement (fixed)
[with patch, positive review] Removing __len__ for combinatorial classes (depend on #5200,#4549)
Reported by: | hivert | Owned by: | hivert |
---|---|---|---|
Priority: | major | Milestone: | sage-3.4.1 |
Component: | combinatorics | Keywords: | __len__, count, combinatorial class |
Cc: | sage-combinat | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
After some discussion on sage-combinat-devel, it was decided that __len__
should no be used to get the size of a combinatorial class. Indeed the specifications of __len__
says that it has to return a plain python int, whereas we want to deal with huge and even infinite sets. Unfortunately due to __len__
being called by list / filter / map
and maybe some other functions, it is not possible to issue a warning. So it was decided to simply remove it and issue an error, telling to call .cardinality()
instead. The former usage of .count()
is also deprecated.
Combinat has to be adapted to this and also to the deprecation of iterator
in favor of __iter__
I'm preparing a patch to solve those issues.
Cheers,
Florent
Attachments (4)
Change History (26)
comment:1 Changed 9 years ago by
- Status changed from new to assigned
comment:2 Changed 9 years ago by
- Description modified (diff)
comment:3 Changed 9 years ago by
- Summary changed from Removing __len__ for combinatorial classes to [with patch, needs review] Removing __len__ for combinatorial classes (depend on #5200)
comment:4 Changed 9 years ago by
- Summary changed from [with patch, needs review] Removing __len__ for combinatorial classes (depend on #5200) to [with patch, needs review] Removing __len__ for combinatorial classes (depend on #5200,#4549)
comment:5 Changed 9 years ago by
When applying the patch on top of 3.4 with the following patches applied:
zephyr-/opt/sage/devel/sage>hg qapplied integer_lists_lex-4549-submitted.patch subsets_subwords-5200-submitted.2.patch subsets_subwords-5200-review.patch subwords_fix-5534-submitted.patch combinatorialclass_iter_len_count_cleanup.patch
I get a reject in
zephyr-/opt/sage/devel/sage>cat sage/combinat/subset.py.rej --- subset.py +++ subset.py @@ -522,7 +522,7 @@ [0, 1, 3] sage: S._multiplicities [1, 2, 1] - sage: Subsets([1,2,3,3], multiset=True).count() + sage: Subsets([1,2,3,3], multiset=True).cardinality() 12 sage: S == loads(dumps(S)) True @@ -604,7 +604,7 @@ sage: S = Subsets([1,2,3,3],2, multiset=True) sage: S._k 2 - sage: S.count() + sage: S.cardinality() 4 sage: S.first() [1, 2]
Moreover, the following tests get broken:
sage -t "3.4.rc0/devel/sage-patches/sage/combinat/sf/ns_macdonald.py" sage -t "3.4.rc0/devel/sage-patches/sage/combinat/subset.py" sage -t "3.4.rc0/devel/sage-patches/sage/combinat/words/words.py"
either by the deprecation warnings, or for words by a change of output:
96889010407L -> 96889010407
Other than this, the patch sounds good to me!
comment:6 follow-ups: ↓ 7 ↓ 8 Changed 9 years ago by
In CartesianProduct?, shouldn't we test first if it.cardinality works, and resort to len if this raised an AttributeError?? Line 3 of the doc of InfiniteAbstractCombinatorialClass?:
- inerit -> inherit, wich -> which, count -> cardinality, ...
The log of the patch should advertise this new class
In CyclicPermutations?: leave at least a note that this deviates from the standard (iter/list take no argument), and should be cleaned up further at some point
In the examples (like in SemistandardTableaux?), do we want to use: [t for t in iterable]
or list(iterable)
comment:7 in reply to: ↑ 6 ; follow-up: ↓ 9 Changed 9 years ago by
I've looked over the changes to the words files. Everything looks good. To fix the problem with the doctests related to 96889010407L that nthiery mentioned above, just have Word_n.cardinality() (in sage/combinat/words/words.py) return a Sage Integer instead of a Python int. If you do this, then it also deals with #4938.
comment:8 in reply to: ↑ 6 ; follow-up: ↓ 11 Changed 9 years ago by
Dear Nicolas,
I sumbmitted a new patch which should addres all the issues except this last one:
In the examples (like in SemistandardTableaux?), do we want to use:
[t for t in iterable]
orlist(iterable)
I think both kind of example should by advertised. IMHO, they both are very python idiomatic, the first one allows for extra condition, the second one is shorter. The only clear argument is that the first one is slightly faster:
sage: timeit("it = iter(Permutations(6)); list(it)") 125 loops, best of 3: 4.57 ms per loop sage: timeit("it = iter(Permutations(6)); list(it)") 125 loops, best of 3: 4.45 ms per loop sage: timeit("it = iter(Permutations(6)); [i for i in it]") 125 loops, best of 3: 4.64 ms per loop sage: timeit("it = iter(Permutations(6)); [i for i in it]") 125 loops, best of 3: 4.61 ms per loop
Do we really what to standardize all the doc on it ?
Cheers,
Florent
comment:9 in reply to: ↑ 7 ; follow-up: ↓ 10 Changed 9 years ago by
Dear Franco,
I've looked over the changes to the words files. Everything looks good. To fix the problem with the doctests related to 96889010407L that nthiery mentioned above, just have Word_n.cardinality() (in sage/combinat/words/words.py) return a Sage Integer instead of a Python int. If you do this, then it also deals with #4938.
Actually, the problem was that I forgot to re-export the patch from the combinat server...
I can't reproduce the problem on word but I don't have access to a 32bit machine. More precisely, words.size_of_alphabet()
seems now to always return a sage integer. That should fix the problem. Can you please check it ?
Cheers,
Florent
comment:10 in reply to: ↑ 9 Changed 9 years ago by
Replying to hivert:
Dear Franco,
I can't reproduce the problem on word but I don't have access to a 32bit machine. More precisely,
words.size_of_alphabet()
seems now to always return a sage integer. That should fix the problem. Can you please check it ?
Sorry it took so long: I had to compile sage on a 32-bit machine!
The last patch (combinatorialclass_iter_len_count_cleanup-5308-submitted.patch) applies cleanly to sage-3.4 on top of the patches for #5200 and #4549. I ran all the combinat doctests and all tests passed.
You get a positive review from me. I won't change the status though, since Nicolas might still have some issues.
comment:11 in reply to: ↑ 8 Changed 9 years ago by
- Cc hivert added
- Milestone changed from sage-combinat to sage-3.4.2
- Summary changed from [with patch, needs review] Removing __len__ for combinatorial classes (depend on #5200,#4549) to [with patch, positive review] Removing __len__ for combinatorial classes (depend on #5200,#4549)
Replying to hivert:
In the examples (like in SemistandardTableaux?), do we want to use:
[t for t in iterable]
orlist(iterable)
I think both kind of example should by advertised. IMHO, they both are very python idiomatic, the first one allows for extra condition, the second one is shorter. The only clear argument is that the first one is slightly faster:
sage: timeit("it = iter(Permutations(6)); list(it)") 125 loops, best of 3: 4.57 ms per loop sage: timeit("it = iter(Permutations(6)); list(it)") 125 loops, best of 3: 4.45 ms per loop sage: timeit("it = iter(Permutations(6)); [i for i in it]") 125 loops, best of 3: 4.64 ms per loop sage: timeit("it = iter(Permutations(6)); [i for i in it]") 125 loops, best of 3: 4.61 ms per loopDo we really what to standardize all the doc on it ?
Good point. The speed difference is too negligible that it seems likely to change in the future one way or the other. I guess we can just leave it as it is. Future will tell if any of the two form become more sage-combinat idiomatic.
Positive review
comment:12 follow-up: ↓ 13 Changed 9 years ago by
Hmm, one last thing: In def __len__(self):
you deprecate __len__
and tell people to use count. Isn't it possible to deprecate __len__
and have it call count() automatically because that is the way it is supposed to work.
Cheers,
Michael
comment:13 in reply to: ↑ 12 Changed 9 years ago by
Replying to mabshoff:
Hmm, one last thing: In
def __len__(self):
you deprecate__len__
and tell people to use count. Isn't it possible to deprecate__len__
and have it call count() automatically because that is the way it is supposed to work.
It should say that one needs to use cardinality instead of __len__
.
There are a few reasons why this doesn't work. One reason is that __len__
must return a Python int. So, if the CombinatorialClass? is too big, then calling __len__
will raise an error, which is a bug.
Another problem is that some methods, like __list__
, call __len__
behind the scenes. This means that there would be deprecation warnings popping up in various places: for instance, list(Permutations(3))
would give a warning, and it would be very confusing to a user not familiar with Python internals to see a warning about using __len__
when they didn't obviously call __len__
. Also the doctests would be littered with such deprecation warnings in various places (whenever list/filter/map
are called). Instead, we decided to raise an AttributeError
, which behaves nicely with Python's specifications on how __len__
is to behave when called by list/filter/map
, and also gives an appropriate error message when len
is called directly. It really is a special case, where the usual deprecation procedure won't work.
comment:14 Changed 9 years ago by
- Milestone changed from sage-3.4.2 to sage-3.4.1
If its still possible, I'd rather seen this integrated in 3.4.1, to be sure that new users get good habits.
Florent
comment:15 Changed 9 years ago by
The patch needed a trivial rebase because of my review patch on #4549. The rebased patch should apply cleanly on top of attachment:ticket:4549:integer_lists_lex-4549-submitted.patch and attachment:ticket:4549:integer_lists_lex-4549-review.patch
Cheers,
Florent
comment:16 follow-up: ↓ 18 Changed 9 years ago by
- Summary changed from [with patch, positive review] Removing __len__ for combinatorial classes (depend on #5200,#4549) to [with patch, needs work] Removing __len__ for combinatorial classes (depend on #5200,#4549)
This patch introduces two trivial to fix doctest failures:
mabshoff@sage:/scratch/mabshoff/sage-3.4.1.rc0$ ./sage -t -long devel/sage/sage/rings/polynomial/multi_polynomial_ideal.py sage -t -long "devel/sage/sage/rings/polynomial/multi_polynomial_ideal.py" ********************************************************************** File "/scratch/mabshoff/sage-3.4.1.rc0/devel/sage/sage/rings/polynomial/multi_polynomial_ideal.py", line 911: sage: I.dimension() Expected: verbose 0 (...: multi_polynomial_ideal.py, dimension) Warning: falling back to very slow toy implementation. 0 Got: verbose 0 (891: multi_polynomial_ideal.py, dimension) Warning: falling back to very slow toy implementation. doctest:966: DeprecationWarning: The usage of iterator for combinatorial classes is deprecated. Please use the class itself 0 ********************************************************************** 1 items had failures: 1 of 15 in __main__.example_17 ***Test Failed*** 1 failures. For whitespace errors, see the file /scratch/mabshoff/sage-3.4.1.rc0/tmp/.doctest_multi_polynomial_ideal.py [11.3 s] exit code: 1024 ---------------------------------------------------------------------- The following tests failed: sage -t -long "devel/sage/sage/rings/polynomial/multi_polynomial_ideal.py" Total time for all tests: 11.3 seconds mabshoff@sage:/scratch/mabshoff/sage-3.4.1.rc0$ ./sage -t -long devel/sage/doc/en/a_tour_of_sage/index.rst sage -t -long "devel/sage/doc/en/a_tour_of_sage/index.rst" ********************************************************************** File "/scratch/mabshoff/sage-3.4.1.rc0/devel/sage/doc/en/a_tour_of_sage/index.rst", line 132: sage: z = Partitions(10^8).count() #about 4.5 seconds Expected nothing Got: doctest:1: DeprecationWarning: The usage of iterator for combinatorial classes is deprecated. Please use the class itself ********************************************************************** 1 items had failures: 1 of 4 in __main__.example_9 ***Test Failed*** 1 failures. For whitespace errors, see the file /scratch/mabshoff/sage-3.4.1.rc0/tmp/.doctest_index.py [10.9 s] exit code: 1024
Once those are fixed the positive review can be reinstated.
Cheers,
Michael
comment:17 Changed 9 years ago by
comment:18 in reply to: ↑ 16 Changed 9 years ago by
- Summary changed from [with patch, needs work] Removing __len__ for combinatorial classes (depend on #5200,#4549) to [with patch, positive review] Removing __len__ for combinatorial classes (depend on #5200,#4549)
Replying to mabshoff:
This patch introduces two trivial to fix doctest failures:
- Oups !!! I probably let the first pass because it's typically one of the few files that triggers the pexpect issue on my fast testing machine...
- Next time I'll check also the .rst files.
These should be fixed right now. Re-uploaded a new patch and re marked as positive reviewed.
Cheers,
Florent
comment:19 Changed 9 years ago by
I have had to update the hunk applied to sage/rings/polynomial/multi_polynomial_ideal.py due to #5485, but I am doctesting the patch now ;)
Cheers,
Michael
comment:20 Changed 9 years ago by
- Resolution set to fixed
- Status changed from assigned to closed
Merged in Sage 3.4.1.rc1.
Cheers,
Michael
comment:21 Changed 9 years ago by
FYI: Merged trac_5308_combinatorialclass_iter_len_count_cleanup-5308-rebased.patch in Sage 3.4.1.rc1.
Cheers,
Michael
comment:22 Changed 9 years ago by
- Cc sage-combinat added; hivert removed
I've attached a patch for the cleanup. It should apply cleanly on top of #5200.
Author: Florent Hivert