#2737 closed enhancement (fixed)
[with patch, positive review] add balanced_sum to Sage
Reported by: | Mike Hansen | Owned by: | somebody |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.1.1 |
Component: | basic arithmetic | Keywords: | |
Cc: | Merged in: | Sage 4.1.1.alpha1 | |
Authors: | Jason Grout, Mike Hansen | Reviewers: | Robert Bradshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Attachments (2)
Change History (15)
Changed 15 years ago by
Attachment: | 2737.patch added |
---|
comment:1 Changed 15 years ago by
comment:2 Changed 15 years ago by
Can you post some timings? For most types summation won't be helped by balancing it (compared to say multiplication) because the basic algorithm is already linear. Unless there are non-trivial improvements, I don't think it's worth the code duplication.
comment:3 Changed 15 years ago by
I don't know of any good benchmarks (since I don't have any personal interest in this). However, this is from Joel:
About a month ago, I mailed sage-devel with a related issue: sage: N=1000 sage: R.<x,y>=QQ[] sage: L2=[x^i for i in range(N)] sage: sum(L2) ... The above sum behaves quadratically since it appears that singular goes through it's whole list of monomials when it adds a single monomial. This was much improved by a divide and conquer sum approach. I didn't bother to write the generic function though. I'm just noting that if you've written the generic code, I think it should be included because there are some types for which the small additions are expensive. Whether or not this should replace 'sum' in the sage global namespace, I'm not so certain.
comment:4 Changed 13 years ago by
Summary: | add balanced_sum to Sage → [with patch, needs review] add balanced_sum to Sage |
---|
comment:5 Changed 13 years ago by
Summary: | [with patch, needs review] add balanced_sum to Sage → [with patch, positive review] add balanced_sum to Sage |
---|
I fixed a bug, added some documentation, and rebased the patch to 4.1. I think my changes are minor enough that I can still review the patch. Positive review.
Mike is right, though. There is some major code duplication that eventually should be factored out.
comment:6 follow-up: 12 Changed 13 years ago by
Reviewers: | → Jason Grout |
---|
Some timing info for the tour, comparing balanced sum with the builtin sum.
sage: a=range(10e6) sage: %timeit sum(a) 10 loops, best of 3: 2.58 s per loop sage: %timeit balanced_sum(a) 10 loops, best of 3: 891 ms per loop sage: balanced_sum(a)==sum(a) True
comment:7 Changed 13 years ago by
Summary: | [with patch, positive review] add balanced_sum to Sage → [with patch, needs review] add balanced_sum to Sage |
---|
A more drastic example:
sage: a=[[i] for i in range(10e4)] sage: %time b=sum(a,[]) CPU times: user 209.95 s, sys: 0.57 s, total: 210.51 s Wall time: 245.69 s sage: a==[[i] for i in range(10e4)] True sage: b==range(10e4) True sage: %time c=balanced_sum(a, []) CPU times: user 0.11 s, sys: 0.00 s, total: 0.11 s Wall time: 0.12 s sage: a==[[i] for i in range(10e4)] True sage: c==range(10e4) True
However, I also uncovered a bug because the function does not copy its arguments (it modified the lists it was using, giving an incorrect sum). I'm posting a revised patch. This revised patch should be reviewed.
comment:8 Changed 13 years ago by
Apply just the trac-2737-balancedsum-rebased-bug-fixed.patch patch.
Changed 13 years ago by
Attachment: | trac-2737-balancedsum-rebased-bug-fixed.patch added |
---|
apply instead of previous patch
comment:9 Changed 13 years ago by
Summary: | [with patch, needs review] add balanced_sum to Sage → [with patch, positive review] add balanced_sum to Sage |
---|
Positive review to the second patch. I don't see an easy way to get rid of code duplication, so I think this is worth it.
comment:10 Changed 13 years ago by
Authors: | → Jason Grout, Mike Hansen |
---|---|
Reviewers: | Jason Grout → Robert Bradshaw |
comment:11 Changed 13 years ago by
Merged in: | → Sage 4.1.1.alpha1 |
---|---|
Resolution: | → fixed |
Status: | new → closed |
Merged trac-2737-balancedsum-rebased-bug-fixed.patch
.
comment:12 Changed 13 years ago by
Replying to jason:
Some timing info for the tour, comparing balanced sum with the builtin sum.
sage: a=range(10e6) sage: %timeit sum(a) 10 loops, best of 3: 2.58 s per loop sage: %timeit balanced_sum(a) 10 loops, best of 3: 891 ms per loop sage: balanced_sum(a)==sum(a) True
This is what I get on sage.math:
sage: L = range(10e6) sage: %time sum(L); CPU times: user 0.51 s, sys: 0.00 s, total: 0.51 s Wall time: 0.51 s sage: %time balanced_sum(L); CPU times: user 0.78 s, sys: 0.00 s, total: 0.78 s Wall time: 0.79 s sage: %timeit sum(L); 10 loops, best of 3: 504 ms per loop sage: %timeit balanced_sum(L); 10 loops, best of 3: 753 ms per loop
Looks like balanced_sum()
is worse off than the built-in sum()
for this particular example.
comment:13 Changed 13 years ago by
So I guess my computer is slow. The builtin sum is *fast*. However, when it costs a fixed high cost to add two elements together (like the lists above), I think the balanced sum is a clear, clear winner. The list example above should show great improvement, even on sage.math.
I've added my initial patch. There is major code duplication through.