[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)[0]. 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
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/
