#14094: Iterating through Partitions(n) for n>=1000.
---------------------------------+------------------------------------------
Reporter: nthiery | Owner: sage-combinat
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.7
Component: combinatorics | Resolution:
Keywords: days45 | Work issues:
Report Upstream: N/A | Reviewers: Travis Scrimshaw
Authors: Mike Hansen | Merged in:
Dependencies: #13605 | Stopgaps:
---------------------------------+------------------------------------------
Changes (by tscrim):
* reviewer: => Travis Scrimshaw
* dependencies: => #13605
Comment:
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
([https://groups.google.com/forum/?fromgroups=#!topic/cython-
users/KnjF7ViaHUM: 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,[[BR]]
Travis
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14094#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
