[Tim] > Woo hoo! Another coincidence. I just happened to be playing with > this problem today: > > You have a large list - xs - of N numbers. It's necessary to compute slice > sums > > sum(xs[i:j]) > > for a great many slices, 0 <= i <= j <= N.
Which brought to mind a different problem: we have a list of numbers, `xs`. For each index position `i`, we want to know the largest sum among all segments ending at xs[i], and the number of elements in a maximal-sum slice ending at xs[i]. `accumulate()` is a natural way to approach this, for someone with a functional language background. You'll have to trust me on that ;-) But there are some twists: - The identity element for max() is minus infinity, which accumulate() can';t know. - We want to generate a sequence of 2-tuples, despite that xs is a sequence of numbers. - In this case, we do _not_ want to see the special initial value. For example, given the input xs [-10, 3, -1, 7, -9, -7, -9, 7, 4] we want to generate (-10, 1), (3, 1), (2, 2), (9, 3), (0, 4), (-7, 1), (-9, 1), (7, 1), (11, 2) Note: the largest sum across all non-empty slices is then max(that_result). The code below could be easily changed to keep track off that incrementally too, but this is already so different from "plain old running sum" that I don't want more novelty than necessary to make the points (a special initial value is needed, and it's not necessarily insane to want to produce results of a different type than the inputs). The key part is the state updating function: def update(state, x): prevmax, count = state newsum = prevmax + x if newsum > x: return newsum, count + 1 else: return x, 1 That's all there is to it! Then, e.g., >>> from itertools import accumulate, chain >>> import math >>> xs = [-10, 3, -1, 7, -9, -7, -9, 7, 4] >>> initial = (-math.inf, 1) >>> result = accumulate(chain([initial], xs), update) >>> next(result) # discard unwanted value (-inf, 1) >>> list(result) [(-10, 1), (3, 1), (2, 2), (9, 3), (0, 4), (-7, 1), (-9, 1), (7, 1), (11, 2)] _______________________________________________ Python-ideas mailing list Pythonemail@example.com https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/