Opened 9 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 nthiery)

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 implementing n 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)

integer_lists_lex-4549-nt.patch (30.1 KB) - added by nthiery 9 years ago.
trac_4549-review.patch (8.9 KB) - added by mhansen 9 years ago.
integer_lists_lex-4549-submitted.patch (40.5 KB) - added by nthiery 9 years ago.
integer_lists_lex-4549-review.patch (3.4 KB) - added by hivert 9 years ago.
Fix for the remaining broken pickle + tests for the other one.

Download all attachments as: .zip

Change History (23)

Changed 9 years ago by nthiery

comment:1 Changed 9 years ago by nthiery

  • 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

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!

comment:2 in reply to: ↑ description Changed 9 years ago by saliola

Replying to nthiery:

See the title. Patch integer_lists_lex-nt in development in sage-combinat.

Note: this patch depends on #4371 and #5255.

comment:3 Changed 9 years ago by hivert

  • Milestone changed from sage-combinat to sage-3.3

comment:4 Changed 9 years ago by nthiery

  • Owner changed from mhansen to nthiery

Changed 9 years ago by mhansen

comment:5 follow-ups: Changed 9 years ago by mhansen

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 hivert

Replying to mhansen: It's ok for me ! The warning is a good idea. Go ahead.

comment:7 Changed 9 years ago by mhansen

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

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

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 nthiery

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 mabshoff

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

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

comment:13 Changed 9 years ago by nthiery

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

I should mention: only the last patch is needed; it integrates the previous ones

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

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

Changed 9 years ago by hivert

Fix for the remaining broken pickle + tests for the other one.

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

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 nthiery

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

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

  • 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

Note: See TracTickets for help on using tickets.