The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Accumulate function in python
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 18 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Jul 19 2010, 7:18 am
Newsgroups: comp.lang.python
From: dhruvbird <dhruvb...@gmail.com>
Date: Mon, 19 Jul 2010 04:18:48 -0700 (PDT)
Local: Mon, Jul 19 2010 7:18 am
Subject: Accumulate function in python
Hello,
I have a list of integers: x = [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]
And would like to compute the cumulative sum of all the integers
from index zero into another array. So for the array above, I should
get: [ 0, 1, 3, 4, 5, 5, 5, 7, 10 ]
What is the best way (or pythonic way) to get this.

Regards,
-Dhruv.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 7:28 am
Newsgroups: comp.lang.python
Followup-To: comp.lang.python
From: Peter Otten <__pete...@web.de>
Date: Mon, 19 Jul 2010 13:28:35 +0200
Local: Mon, Jul 19 2010 7:28 am
Subject: Re: Accumulate function in python

dhruvbird wrote:
>   I have a list of integers: x = [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]
>   And would like to compute the cumulative sum of all the integers
> from index zero into another array. So for the array above, I should
> get: [ 0, 1, 3, 4, 5, 5, 5, 7, 10 ]
>   What is the best way (or pythonic way) to get this.

Homework?

>>> def cumulative_sum(values, start=0):

...     for v in values:
...             start += v
...             yield start
...
>>> list(cumulative_sum([ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]))

[0, 1, 3, 4, 5, 5, 5, 7, 10]

Peter

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 7:40 am
Newsgroups: comp.lang.python
From: Vlastimil Brom <vlastimil.b...@gmail.com>
Date: Mon, 19 Jul 2010 13:40:29 +0200
Local: Mon, Jul 19 2010 7:40 am
Subject: Re: Accumulate function in python
2010/7/19 dhruvbird <dhruvb...@gmail.com>:

> Hello,
>  I have a list of integers: x = [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]
>  And would like to compute the cumulative sum of all the integers
> from index zero into another array. So for the array above, I should
> get: [ 0, 1, 3, 4, 5, 5, 5, 7, 10 ]
>  What is the best way (or pythonic way) to get this.

> Regards,
> -Dhruv.
> --

Hi,
just a straightworward, naive approach...:

lst_int =  [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]
acc_int = 0
output_lst = []
for i in lst_int:
acc_int += i
output_lst.append(acc_int)
print output_lst

vbr

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 8:14 am
Newsgroups: comp.lang.python
Date: Mon, 19 Jul 2010 14:14:15 +0200
Local: Mon, Jul 19 2010 8:14 am
Subject: Re: Accumulate function in python
Am 19.07.2010 13:18, dhruvbird wrote:

> Hello,
>   I have a list of integers: x = [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]
>   And would like to compute the cumulative sum of all the integers
> from index zero into another array. So for the array above, I should
> get: [ 0, 1, 3, 4, 5, 5, 5, 7, 10 ]
>   What is the best way (or pythonic way) to get this.

<python>

import copy
import itertools

def acc(items, copy=copy.deepcopy):
items = iter(items)
result = next(items)
yield copy(result)
for item in items:
result += item
yield copy(result)

print list(acc([0, 1, 2, 1, 1, 0, 0, 2, 3]))
print list(itertools.islice(acc(itertools.count()), 10))
print list(acc(['a', 'b', 'c']))
print list(acc([[a], [b], [c]]))

</python>

Output:

[0, 1, 3, 4, 5, 5, 5, 7, 10]
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
['a', 'ab', 'abc']
[[a], [a, b], [a, b, c]]

Without copy.deepcopy() the last line would be:

[[a, b, c], [a, b, c], [a, b, c]]

The copy=copy.deepcopy parameter allows for things like this:

>>> print list(acc([[a], [b], [c]], tuple))

[(a,), (a, b), (a, b, c)]

or:

>>> print list(acc([['a'], ['b'], ['f'], ['s'], ['c'], ['g']], max))

['a', 'b', 'f', 's', 's', 's']

or:

>>> data = [[0], [1], [2], [1], [1], [2], [3]]
>>> print list(acc(data, lambda x: float(sum(x)) / float(len(x))))

[0.0, 0.5, 1.0, 1.0, 1.0, 1.1666666666666667, 1.4285714285714286]

Endless possibilities in an endless universe.

Regards,
Mick.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 10:24 am
Newsgroups: comp.lang.python
From: Andre Alexander Bell <p...@andre-bell.de>
Date: Mon, 19 Jul 2010 16:24:41 +0200
Local: Mon, Jul 19 2010 10:24 am
Subject: Re: Accumulate function in python
On 07/19/2010 01:18 PM, dhruvbird wrote:

> Hello,
>   I have a list of integers: x = [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]
>   And would like to compute the cumulative sum of all the integers
> from index zero into another array. So for the array above, I should
> get: [ 0, 1, 3, 4, 5, 5, 5, 7, 10 ]
>   What is the best way (or pythonic way) to get this.

> Regards,
> -Dhruv.

Maybe not pythonic, but straight-forward:

>>> import numpy
>>> numpy.cumsum(x)

array([ 0,  1,  3,  4,  5,  5,  5,  7, 10])

An example with a class

class CumulativeSum(object):
def __init__(self, start=0):
self._current = start
def __call__(self, value):
self._current += value
return self._current

>>> cummulative_sum = CumulativeSum(0)
>>> map(cummulative_sum, x)

[0, 1, 3, 4, 5, 5, 5, 7, 10]

Dirty:

current = 0

def cummulative_sum(value):
global current
current += value
return current

>>> map(cummulative_sum, x)

[0, 1, 3, 4, 5, 5, 5, 7, 10]

Weird:

def cummulative_sum_reducer(x, y):
x.append(x[-1] + y)
return x

>>> reduce(cummulative_sum_reducer, x, [0])

[0, 0, 1, 3, 4, 5, 5, 5, 7, 10]

Cheers

Andre

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 10:49 am
Newsgroups: comp.lang.python
From: Steven D'Aprano <st...@REMOVE-THIS-cybersource.com.au>
Date: 19 Jul 2010 14:49:31 GMT
Local: Mon, Jul 19 2010 10:49 am
Subject: Re: Accumulate function in python

On Mon, 19 Jul 2010 04:18:48 -0700, dhruvbird wrote:
> Hello,
>   I have a list of integers: x = [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ] And would
>   like to compute the cumulative sum of all the integers
> from index zero into another array. So for the array above, I should
> get: [ 0, 1, 3, 4, 5, 5, 5, 7, 10 ]

[pedant]
The above are *lists*, not arrays. Python has arrays, but you have to
call "import array" to get them.
[/pedant]

>   What is the best way (or pythonic way) to get this.

Others have given you a plethora of advanced, complicated and obscure
ways to solve this question, but I haven't seen anyone give the simplest
method (simple as in no tricks or advanced features):

data = [0, 1, 2, 1, 1, 0, 0, 2, 3]
csums = []
for x in data:
if csums:
y = x + csums[-1]
else:
y = x
csums.append(y)

We can save some code with the ternary operator:

data = [0, 1, 2, 1, 1, 0, 0, 2, 3]
csums = []
for x in data:
csums.append((x + csums[-1]) if csums else x)

Here's a version that writes the cumulative sum in place:

data = [0, 1, 2, 1, 1, 0, 0, 2, 3]
for i in range(1, len(data)):
data[i] += data[i-1]

--
Steven

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 12:12 pm
Newsgroups: comp.lang.python
From: Brian Victor <homeusen...@brianhv.org>
Date: Mon, 19 Jul 2010 16:12:04 +0000 (UTC)
Local: Mon, Jul 19 2010 12:12 pm
Subject: Re: Accumulate function in python

dhruvbird wrote:
> Hello,
>   I have a list of integers: x = [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]
>   And would like to compute the cumulative sum of all the integers
> from index zero into another array. So for the array above, I should
> get: [ 0, 1, 3, 4, 5, 5, 5, 7, 10 ]
>   What is the best way (or pythonic way) to get this.

Now that Steven's given you the simple, pythonic way, I'll just mention
the advanced, complicated and obscure way that might be vaguely familiar
if you're coming from a functional programming background:

x = [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]
def running_sum(result, current_value):
return result + [result[-1]+current_value if result else current_value]

reduce(running_sum, x, [])

Having offered this, I don't recall ever seeing reduce used in real
python code, and explicit iteration is almost always preferred.

--
Brian

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 12:56 pm
Newsgroups: comp.lang.python
From: dhruvbird <dhruvb...@gmail.com>
Date: Mon, 19 Jul 2010 09:56:03 -0700 (PDT)
Local: Mon, Jul 19 2010 12:56 pm
Subject: Re: Accumulate function in python
On Jul 19, 9:12 pm, Brian Victor <homeusen...@brianhv.org> wrote:

Yes, even I have noticed that reduce is a tad under-used function.

So, I guess no function like "accumulate" below exists in the standard
lib.

def accumulate(proc, seed, seq):
ret = []
for i in seq:
ret.append(proc(seed, i))
return ret

x = [0, 1, 3, 4, 5, 5, 5, 7, 10]
print accumulate(lambda x,y: x+y, 0, x)

My guess is that accumulate can be used in many more scenarios.

Regards,
-Dhruv.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 1:01 pm
Newsgroups: comp.lang.python
From: dhruvbird <dhruvb...@gmail.com>
Date: Mon, 19 Jul 2010 10:01:59 -0700 (PDT)
Local: Mon, Jul 19 2010 1:01 pm
Subject: Re: Accumulate function in python
On Jul 19, 4:28 pm, Peter Otten <__pete...@web.de> wrote:

> dhruvbird wrote:
> >   I have a list of integers: x = [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]
> >   And would like to compute the cumulative sum of all the integers
> > from index zero into another array. So for the array above, I should
> > get: [ 0, 1, 3, 4, 5, 5, 5, 7, 10 ]
> >   What is the best way (or pythonic way) to get this.

> Homework?

not really :)

It's just that I was wondering if a built-in function for doing such
things (which I find myself doing increasingly with an explicit loop)
exists.

Regards,
-Dhruv.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 1:51 pm
Newsgroups: comp.lang.python
From: Duncan Booth <duncan.bo...@invalid.invalid>
Date: 19 Jul 2010 17:51:34 GMT
Local: Mon, Jul 19 2010 1:51 pm
Subject: Re: Accumulate function in python

Why would you find yourself doing it more than once? Write it once in a
function and then just re-use the code.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 2:45 pm
Newsgroups: comp.lang.python
From: Paul Rubin <no.em...@nospam.invalid>
Date: Mon, 19 Jul 2010 11:45:33 -0700
Local: Mon, Jul 19 2010 2:45 pm
Subject: Re: Accumulate function in python

Brian Victor <homeusen...@brianhv.org> writes:
> def running_sum(result, current_value):
>     return result + [result[-1]+current_value if result else current_value]

> reduce(running_sum, x, [])

That is not really any good because Python lists are actually vectors,
so result+[...] actually copies the whole old list, making your function
take quadratic time.  It would be ok in a FP language where lists were
chains of cons nodes and result+[...] just allocated a single cons.

I think Peter Otten's solution involving a generator is the one most in
the current Python spirit.  It's cleaner (for my tastes) than the ones
that use things like list.append.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 19 2010, 6:08 pm
Newsgroups: comp.lang.python
From: Joel Goldstick <joel.goldst...@columbuswebmakers.com>
Date: Mon, 19 Jul 2010 18:08:25 -0400
Local: Mon, Jul 19 2010 6:08 pm
Subject: Re: Accumulate function in python

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 21 2010, 11:17 am
Newsgroups: comp.lang.python
From: John Nagle <na...@animats.com>
Date: Wed, 21 Jul 2010 08:17:36 -0700
Local: Wed, Jul 21 2010 11:17 am
Subject: Re: Accumulate function in python
On 7/19/2010 9:56 AM, dhruvbird wrote:

> On Jul 19, 9:12 pm, Brian Victor<homeusen...@brianhv.org>  wrote:
>> dhruvbird wrote:
>> Having offered this, I don't recall ever seeing reduce used in real
>> python code, and explicit iteration is almost always preferred.

> Yes, even I have noticed that reduce is a tad under-used function.

Yes, I had a use case for it once, but it wasn't worth the trouble.
"map" is often useful, but "reduce", not so much.

Python isn't really a functional language.  There's no bias toward
functional solutions, lambdas aren't very general, and the performance
isn't any better.  Nor is any concurrency provided by "map" or "reduce".
So there's no win in trying to develop cute one-liners.

John Nagle

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 26 2010, 4:24 pm
Newsgroups: comp.lang.python
From: dhruvbird <dhruvb...@gmail.com>
Date: Mon, 26 Jul 2010 13:24:28 -0700 (PDT)
Local: Mon, Jul 26 2010 4:24 pm
Subject: Re: Accumulate function in python
On Jul 21, 8:17 pm, John Nagle <na...@animats.com> wrote:

Yes agreed.

However, there is:

1. now scope for optimization (for example returning generators
instead of lists) at every stage if using functions -- these functions
can be internally changed as long as the external guarantees they
provide remain essentially unchanged.

rather than anything else.
For example, if I want the product of the square roots of all odd
integers in an array, I can say:
answer = reduce(product, map(math.sqrt, filter(lambda x: x%2 == 0,
some_array_with_ints)))

While I agree that python may not have been initially seen as a
functional language, it is powerful and flexible enough to be one or
at least decently support such paradigms.

Regards,
-Dhruv.

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 27 2010, 6:54 am
Newsgroups: comp.lang.python
From: geremy condra <debat...@gmail.com>
Date: Tue, 27 Jul 2010 03:54:07 -0700
Local: Tues, Jul 27 2010 6:54 am
Subject: Re: Accumulate function in python

Too bad about the lack of concurrency, would be many places where that
would be nice.

Geremy Condra

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 27 2010, 7:16 am
Newsgroups: comp.lang.python
From: Stefan Behnel <stefan...@behnel.de>
Date: Tue, 27 Jul 2010 13:16:59 +0200
Local: Tues, Jul 27 2010 7:16 am
Subject: Re: Accumulate function in python
geremy condra, 27.07.2010 12:54:

Besides the many places where the current properties match just fine, there
are some places where concurrency would be helpful. So I wouldn't call it
"lack" of concurrency, as that seems to imply that it's a missing feature
in what both builtins are targeted to provide. Just use one of the
map-reduce frameworks that are out there if you need concurrency in one way
or another. Special needs are not what builtins are there for.

Stefan

To post a message you must first join this group.
You do not have the permission required to post.
More options Jul 27 2010, 9:51 am
Newsgroups: comp.lang.python
From: sturlamolden <sturlamol...@yahoo.no>
Date: Tue, 27 Jul 2010 06:51:21 -0700 (PDT)
Local: Tues, Jul 27 2010 9:51 am
Subject: Re: Accumulate function in python
On 19 Jul, 13:18, dhruvbird <dhruvb...@gmail.com> wrote:

> Hello,
>   I have a list of integers: x = [ 0, 1, 2, 1, 1, 0, 0, 2, 3 ]
>   And would like to compute the cumulative sum of all the integers
> from index zero into another array. So for the array above, I should
> get: [ 0, 1, 3, 4, 5, 5, 5, 7, 10 ]
>   What is the best way (or pythonic way) to get this.

At least for large arrays, this is the kind of task where NumPy will
help.

>>> import numpy as np
>>> np.cumsum([ 0, 1, 2, 1, 1, 0, 0, 2, 3 ])

array([ 0,  1,  3,  4,  5,  5,  5,  7, 10])

To post a message you must first join this group.
You do not have the permission required to post.
More options Aug 2 2010, 1:29 pm
Newsgroups: comp.lang.python
From: a...@pythoncraft.com (Aahz)
Date: 2 Aug 2010 10:29:03 -0700
Local: Mon, Aug 2 2010 1:29 pm
Subject: Re: Accumulate function in python
In article <7xpqyjgvjm....@ruckus.brouhaha.com>,
Paul Rubin  <no.em...@nospam.invalid> wrote:

>I think Peter Otten's solution involving a generator is the one most in
>the current Python spirit.  It's cleaner (for my tastes) than the ones
>that use things like list.append.

Agreed
--
Aahz (a...@pythoncraft.com)           <*>         http://www.pythoncraft.com/

"....Normal is what cuts off your sixth finger and your tail..."  --Siobhan