Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#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 hivert)

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)

combinatorialclass_iter_len_count_cleanup.patch (152.6 KB) - added by hivert 9 years ago.
Good version of the file
combinatorialclass_iter_len_count_cleanup-5308-submitted.patch (157.2 KB) - added by hivert 9 years ago.
Addressed Nicolas reqests.
combinatorialclass_iter_len_count_cleanup-5308-rebased.patch (157.4 KB) - added by hivert 9 years ago.
Hopefully final version
trac_5308_combinatorialclass_iter_len_count_cleanup-5308-rebased.patch (157.5 KB) - added by mabshoff 9 years ago.
Slightly rebased version of Florent's last patch

Download all attachments as: .zip

Change History (26)

comment:1 Changed 9 years ago by hivert

  • Status changed from new to assigned

comment:2 Changed 9 years ago by hivert

  • Description modified (diff)

comment:3 Changed 9 years ago by hivert

  • Summary changed from Removing __len__ for combinatorial classes to [with patch, needs review] Removing __len__ for combinatorial classes (depend on #5200)

I've attached a patch for the cleanup. It should apply cleanly on top of #5200.

Author: Florent Hivert

Changed 9 years ago by hivert

Good version of the file

comment:4 Changed 9 years ago by hivert

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

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: Changed 9 years ago by nthiery

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: Changed 9 years ago by saliola

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.

Changed 9 years ago by hivert

Addressed Nicolas reqests.

comment:8 in reply to: ↑ 6 ; follow-up: Changed 9 years ago by hivert

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] or list(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: Changed 9 years ago by hivert

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 saliola

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 nthiery

  • 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] or list(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 ?

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: Changed 9 years ago by 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.

Cheers,

Michael

comment:13 in reply to: ↑ 12 Changed 9 years ago by saliola

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 hivert

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

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: Changed 9 years ago by mabshoff

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

This ticket also fixes #4938 which should be closed afterwards.

Cheers,

Michael

Changed 9 years ago by hivert

Hopefully final version

comment:18 in reply to: ↑ 16 Changed 9 years ago by hivert

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

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 mabshoff

  • Resolution set to fixed
  • Status changed from assigned to closed

Merged in Sage 3.4.1.rc1.

Cheers,

Michael

Changed 9 years ago by mabshoff

Slightly rebased version of Florent's last patch

comment:21 Changed 9 years ago by mabshoff

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 nthiery

  • Cc sage-combinat added; hivert removed
Note: See TracTickets for help on using tickets.