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? > > I could guess pretty confidently that the reason this optimization was > > never tried is that sum() has always been intended to be used on > > numerics, since other alternatives exist for strings (join), lists > > (chain), and hand-coded data classes that support add-in-place (roll- > > your-own loop). > > Doing it this way helps summing lists or strings (though not as much as > str.join), but it also helps if you need to sum a long list of similarly > sized floats as you'll get a more accurate answer. > Interesting! That makes sense. The docs for math.fsum() suggest that partial sums are used to maintain precision. http://docs.python.org/library/math.html#math.fsum > Seehttp://groups.google.com/group/comp.lang.python/browse_thread/thread/... > faf92f532e/027cef7d4429aa3a > for an earlier discussion of this, or just Google comp.lang.python for > 'pairwise sum'. > > Here's the code I posted in that thread: > > def sumpairs(seq): > tmp = [] > for i,v in enumerate(seq): > if i&1: > tmp[-1] = tmp[-1] + v > i = i + 1 > n = i & -i > while n > 2: > t = tmp.pop(-1) > tmp[-1] = tmp[-1] + t > n >>= 1 > else: > tmp.append(v) > while len(tmp) > 1: > t = tmp.pop(-1) > tmp[-1] = tmp[-1] + t > return tmp[0] > > and I claimed that my Python coded sumpairs function was faster than the > builtin sum on a list of lists once you had more than about 210 items. > I never did get round to rewriting it in C for a more realistic speed > comparison: summing integers my Python version is about 60 times slower > than the builtin. -- http://mail.python.org/mailman/listinfo/python-list
