* Steve Howell:
On Mar 28, 8:17 am, Duncan Booth <duncan.bo...@invalid.invalid> wrote:
Steve Howell <showel...@yahoo.com> wrote:
The mildly surprising part of sum() is that is does add vs. add-in-
place, which leads to O(N) vs. O(1) for the inner loop calls, for
certain data structures, notably lists, even though none of the
intermediate results get used by the caller. For lists, you could
make a more efficient variant of sum() that clones the start value and
does add-in-place.
Doing add-in-place isn't the only way to make sum more efficient: if you
assume that addition is associative (which of course the builtin sum can't)
then you can form partial sums. e.g. instead of calculating:
(((((((a + b) + c) + d) + e) + f) + g) + h)
you calculate:
(((a + b) + (c + d)) + ((e + f) + (g + h)))
Obviously this requires more space than the naive sum, but not as much as
you might at first expect: you only need to hold log(n) intermediates
values at any time.
Yep, I did mention in my post that the outer loop does not *have* to
be O(N), if you can parallelize it. Apart from reducing
intermediates, the divide-and-conquer method does not reduce overall
computation time unless you have multiple processors, correct?
With a single thread of execution it can reduce the time for large integers and
custom numerical types, with n the number of final bits, from O(n^2) to O(n log n).
I don't think the parallelism here is very relevant for Python.
From a more practical point of view, the sum efficiency could be improved by
doing the first addition using '+' and the rest using '+=', without changing the
behavior.
Cheers & hth.,
- Alf
--
http://mail.python.org/mailman/listinfo/python-list
