Iterating through Partitions(n) for n>=1000.

[nthiery]

As discovered live during the Sage Days 45 tutorial, the default fast iterator for Partitions(n) is recursive and breaks for n>988:

sage: P = Partitions(988)
sage: for p in P: print p
Traceback (most recent call last):
  File "<ipython console>", line 1, in <module>
  File "/opt/sage-5.6/local/lib/python2.7/site-packages/sage/combinat/partition.py", line 4282, in __iter__
    sage: all(test(mu,k) for k in range(1,5)
  File "/opt/sage-5.6/local/lib/python2.7/site-packages/sage/combinat/partition.py", line 4312, in _fast_iterator
    new_w.sort(reverse=True)
  File "/opt/sage-5.6/local/lib/python2.7/site-packages/sage/combinat/partition.py", line 4312, in _fast_iterator
    new_w.sort(reverse=True)

Whereas the generic iterator works:

sage: P = Partitions(988, max_part=1000)
sage: for p in P: print p
[988]
[987, 1]
[986, 2]
[986, 1, 1]
[985, 3]

Possible fix: either make the fast iterator non recursive, or default to the generic iterator.

---

Apply: attachment: trac_14094.patch, attachment: trac_14094-partition_iterator-review-ts.patch

Depends on #13605

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: days45

Author: Mike Hansen

Reviewer: Travis Scrimshaw

Merged: sage-5.9.beta3

Issue created by migration from https://trac.sagemath.org/ticket/14094

[mwhansen]

Author: Mike Hansen

[mwhansen]

comment:1

Attachment: trac_14094.patch.gz

I implemented the algorithm found at http://www.site.uottawa.ca/~ivan/F49-int-part.pdf

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

Dependencies: #13605

[tscrim]

comment:2

Hey Mike,

I'm uploading a review patch which moves the functionality into a .pyx file. Here are my average timings:

# Using a python list as in your original implementation
sage: %time L = [x for x in ZS1_iterator(60)]
CPU times: user 3.97 s, sys: 0.18 s, total: 4.16 s
Wall time: 5.31 s

# Old recursive _fast_iterator
sage: P = Partitions(60)
sage: %time L = [x for x in P._fast_iterator()]                         
CPU times: user 15.11 s, sys: 0.64 s, total: 15.74 s
Wall time: 21.81 s

# Using C a int array
sage: %time L = [x for x in ZS1_iterator(60)]
CPU times: user 5.28 s, sys: 0.32 s, total: 5.60 s
Wall time: 6.11 s

I believe the python list will be faster mainly because converting from the C array into the python list will cause frequent memory allocations (see here). I don't know enough cython to do anything different. I also tried pushing the actual implementation into C and pulling back from that, but I would doubt that would net any additional performance increase (anyways, considering we get ~4x increase as is, it will likely be miniscule). I left my C int implementation as comments, feel free to delete.

Also I make this ZS iterator be the fast iterator for both Partitions_all and Partitions_n, remove the old ones, and add a doctest for run_test.

If you agree with my implementation, feel free to set this to positive review.

Thanks for finding and the first implementation of this algorithm,

Travis

[tscrim]

comment:3

Hey Mike,

I've updated my patch which fixes the failing doctests.

Best,

Travis

[tscrim]

comment:4

Rebased patch.

[tscrim]

comment:5

Rebased to remove fuzz for 5.9.beta1. Could someone give my review patch a review? Thanks.

[mwhansen]

comment:6

Your changes look good to me.

[tscrim]

comment:7

Thank you Mike.

[jdemeyer]

comment:8

sage -t devel/sage/sage/combinat/partitions.pyx
**********************************************************************
File "devel/sage/sage/combinat/partitions.pyx", line 103, in sage.combinat.partitions.run_tests
Failed example:
    run_tests(False, False)
Expected:
    Done.
Got:
    Computing p(1)... OK.
    Computing p(10)... OK.
    Computing p(100)... OK.
    Computing p(1000)... OK.
    Computing p(10000)... OK.
    Computing p(100000)... OK.
    Computing p(1000000)... OK.
    Computing p(4219)... OK.
    Computing p(4219)... OK.
    Computing p(38869)... OK.
    Computing p(42719)... OK.
[...and so on...]

[tscrim]

comment:9

Attachment: trac_14094-partition_iterator-review-ts.patch.gz

Fixed:

Doctesting 1 file.
sage -t partitions.pyx
    [30 tests, 1.7 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 2.1 seconds
    cpu time: 1.3 seconds
    cumulative wall time: 1.7 seconds

For patchbot:

Apply: [attachment: trac_14094.patch], [attachment: trac_14094-partition_iterator-review-ts.patch]

[jdemeyer]

Merged: sage-5.9.beta3