[Python-ideas] Start argument for itertools.accumulate() [Was: Proposal: A Reduce-Map Comprehension and a "last" builtin]
tim.peters at gmail.com
Tue Apr 10 12:58:48 EDT 2018
> 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
> 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()
- 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
return x, 1
That's all there is to it!
>>> 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
[(-10, 1), (3, 1), (2, 2), (9, 3), (0, 4), (-7, 1), (-9, 1), (7, 1), (11, 2)]
More information about the Python-ideas