Opened 10 years ago
Closed 9 years ago
#4549 closed enhancement (fixed)
[with patch, positive review] New class IntegerListLex for generating integer lists => much improved partition iterators
Reported by: | nthiery | Owned by: | nthiery |
---|---|---|---|
Priority: | major | Milestone: | sage-3.4.1 |
Component: | combinatorics | Keywords: | |
Cc: | sage-combinat | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
IntegerListsLex? refactoring, and application to Partitions
- Reworked the integer lists lexicographic generator into a full featured combinatorial class IntegerListsLex?
- support for n in a set (or any iterable
I
implementingn in I
)
Applications to Partitions:
- Systematic use of IntegerListsLex? to get constant amortized time iterators (huge efficiency improvement).
- This includes PartitionsGreatestEQ and PartitionsGreatestLE which were previously implemented in GAP. This was inefficient due to the communication overhead, and not using an iterator. (backward compatible unpickling)
- Implements horizontal_border_strip.
Attachments (4)
Change History (23)
Changed 9 years ago by
comment:1 Changed 9 years ago by
- Summary changed from New method horizontal_border_strip using new IntegerListsLex combinatorial class to [with patch, needs review] New class IntegerListLex for generating integer lists => much improved partition iterators
comment:2 in reply to: ↑ description Changed 9 years ago by
comment:3 Changed 9 years ago by
- Milestone changed from sage-combinat to sage-3.3
comment:4 Changed 9 years ago by
- Owner changed from mhansen to nthiery
Changed 9 years ago by
comment:5 follow-ups: ↓ 6 ↓ 9 Changed 9 years ago by
I've added a patch which adds some doctests, adds a warning when min_part=0 is passed to partitions, and changed the default implementation of count to use Integers so that we don't have to reimplemented in IntegerListsLex?
Assuming someone okay's my changes, I think both patches are good to go in.
comment:6 in reply to: ↑ 5 Changed 9 years ago by
Replying to mhansen: It's ok for me ! The warning is a good idea. Go ahead.
comment:7 Changed 9 years ago by
- Summary changed from [with patch, needs review] New class IntegerListLex for generating integer lists => much improved partition iterators to [with patch, positive review] New class IntegerListLex for generating integer lists => much improved partition iterators
comment:8 follow-up: ↓ 10 Changed 9 years ago by
- Cc sage-combinat added
- Summary changed from [with patch, positive review] New class IntegerListLex for generating integer lists => much improved partition iterators to [with patch, positive review, pickle problem] New class IntegerListLex for generating integer lists => much improved partition iterators
This patch breaks the pickle jar which according to Mike is no surprise:
sage -t -long "devel/sage/sage/structure/sage_object.pyx" ********************************************************************** File "/scratch/mabshoff/sage-3.3.rc1/devel/sage/sage/structure/sage_object.pyx", line 682: sage: sage.structure.sage_object.unpickle_all(std) Expected: doctest:...: DeprecationWarning: Your data is stored in an old format. Please use the save() function to store your data in a more recent format. doctest:...: DeprecationWarning: RQDF is deprecated; use RealField(212) instead. Successfully unpickled ... objects. Failed to unpickle 0 objects. Got: doctest:1172: DeprecationWarning: Your data is stored in an old format. Please use the save() function to store your data in a more recent format. doctest:1172: DeprecationWarning: RQDF is deprecated; use RealField(212) instead. ** failed: _class__sage_combinat_partition_PartitionsGreatestEQ_nk__.sobj ** failed: _class__sage_combinat_partition_Partitions_constraints__.sobj ** failed: _class__sage_combinat_partition_PartitionsGreatestLE_nk__.sobj Failed: _class__sage_combinat_partition_PartitionsGreatestEQ_nk__.sobj _class__sage_combinat_partition_Partitions_constraints__.sobj _class__sage_combinat_partition_PartitionsGreatestLE_nk__.sobj Successfully unpickled 445 objects. Failed to unpickle 3 objects. **********************************************************************
We need to make a call if we are going to break this pickles or not. Other than that there were no doctesting issues.
Cheers,
Michael
comment:9 in reply to: ↑ 5 Changed 9 years ago by
Replying to mhansen:
I've added a patch which adds some doctests, adds a warning when min_part=0 is passed to partitions,
Thanks!
and changed the default implementation of count to use Integers
Good.
so that we don't have to reimplemented in IntegerListsLex?
We still do! Sorry, I did not comment on this in the code, but the implementation of count differs from the default one from CombinatorialClass?, as it bypasses the call to _element_constructor_!
comment:10 in reply to: ↑ 8 Changed 9 years ago by
Replying to mabshoff:
This patch breaks the pickle jar which according to Mike is no surprise:
Indeed no surprise.
We need to make a call if we are going to break this pickles or not. Other than that there were no doctesting issues.
I would tend to break the pickles indeed, unless someone cries very loud for this.
Cheers,
Nicolas
comment:11 Changed 9 years ago by
- Milestone changed from sage-3.3 to sage-3.4.1
I am cleaning up the 3.3 milestone. If a patch with positive review is put up to this ticket on time it might make it into 3.3.
Cheers,
Michael
comment:12 Changed 9 years ago by
- Summary changed from [with patch, positive review, pickle problem] New class IntegerListLex for generating integer lists => much improved partition iterators to [with patch, needs work] New class IntegerListLex for generating integer lists => much improved partition iterators
Changed 9 years ago by
comment:13 Changed 9 years ago by
- Description modified (diff)
- Summary changed from [with patch, needs work] New class IntegerListLex for generating integer lists => much improved partition iterators to [with patch, needs review] New class IntegerListLex for generating integer lists => much improved partition iterators
Updated patch:
- Now handles pickles of PartitionsGreatestEQ and PartitionsGreatestLE from sage <= 3.4.1.
- Rebased against 3.4 (and sphinx)
comment:14 follow-up: ↓ 15 Changed 9 years ago by
I should mention: only the last patch is needed; it integrates the previous ones
comment:15 in reply to: ↑ 14 ; follow-up: ↓ 16 Changed 9 years ago by
Dear Nicolas,
I should mention: only the last patch is needed; it integrates the previous ones
The patch looks good to me. However, though I'm not 100% sure I launched the correct check, it seems that one of the old pickle is still broken:
sage: std = os.environ['SAGE_DATA'] + '/extcode/pickle_jar/pickle_jar.tar.bz2' sage: sage.structure.sage_object.unpickle_all(std) ** failed: _class__sage_combinat_partition_Partitions_constraints__.sobj /usr/local/sage/sage/local/lib/python2.5/site-packages/IPython/iplib.py:2073: DeprecationWarning: RQDF is deprecated; use RealField(212) instead. exec code_obj in self.user_global_ns, self.user_ns Failed: _class__sage_combinat_partition_Partitions_constraints__.sobj Successfully unpickled 486 objects. Failed to unpickle 1 objects.
Am I doing something wrong ?
Cheers,
Florent
comment:16 in reply to: ↑ 15 Changed 9 years ago by
Dear All,
The patch looks good to me. However, though I'm not 100% sure I launched the correct check, it seems that one of the old pickle is still broken:
I added a review patch which should fix this remaining pickle problem. If someone reread it I'm ready to give a positive review.
Florent
comment:17 Changed 9 years ago by
- Priority changed from minor to major
- Summary changed from [with patch, needs review] New class IntegerListLex for generating integer lists => much improved partition iterators to [with patch, positive review] New class IntegerListLex for generating integer lists => much improved partition iterators
Thanks Florent for the fix. I had overlooked this pickle. Oh, and thanks for pointing out how one can test backward compatibility unpickles :-)
I tried the patch on my machine and it looks and works fine.
So, I allow myself to set the positive review flag on behalf of Florent!
I also lifted the priority to major, since this gives a large (memory) efficiency gain.
comment:18 Changed 9 years ago by
- Milestone changed from sage-3.4.2 to sage-3.4.1
If its still possible, I'd rather see this integrated in 3.4.1, this allows for #5308 being integrated as soon as possible.
Florent
comment:19 Changed 9 years ago by
- Resolution set to fixed
- Status changed from new to closed
Merged
- integer_lists_lex-4549-submitted.patch
- integer_lists_lex-4549-review.patch
in Sage 3.4.1.rc0.
Cheers,
Michael
Reworked the integer lists lexicographic generator into a full featured combinatorial class IntegerListsLex? Use it systematically in Partitions to get constant amortized time iterators. Also implements horizontal_border_strip.
Note: the attached patch does not contain the commit messages!