Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   Is there a list comprehension for this? (http://www.velocityreviews.com/forums/t396606-is-there-a-list-comprehension-for-this.html)

 liam_herron 11-21-2006 09:19 PM

Is there a list comprehension for this?

Given:
dw = [ 1, -1.1, +1.2 ]

Suppose I want to create a list 'w' that is defined as

w[0] = dw[0],
w[1] = w[0] + dw[1],
w[2] = w[1] + dw[2]

Is there a list comprehension or map expression to do it in one or 2
lines.

 Tim Chase 11-21-2006 09:45 PM

Re: Is there a list comprehension for this?

> dw = [ 1, -1.1, +1.2 ]
>
> Suppose I want to create a list 'w' that is defined as
>
> w[0] = dw[0],
> w[1] = w[0] + dw[1],
> w[2] = w[1] + dw[2]
>
> Is there a list comprehension or map expression to do it in one or 2
> lines.

Well, while it's not terribly efficient, you can do something like

w = [sum(dw[:i]) for i in xrange(1,len(dw)+1)]

Or, if you need the efficiencies for larger len(dw) values, you
could do something like

>>> def f(x):

.... i = 0
.... for item in x:
.... i += item
.... yield i
....
>>> list(i for i in f(dw))

[1, -0.10000000000000009, 1.0999999999999999]

Just a few ideas,

-tkc

 Mathias Panzenboeck 11-21-2006 09:58 PM

Re: Is there a list comprehension for this?

liam_herron wrote:
> Given:
> dw = [ 1, -1.1, +1.2 ]
>
> Suppose I want to create a list 'w' that is defined as
>
> w[0] = dw[0],
> w[1] = w[0] + dw[1],
> w[2] = w[1] + dw[2]
>
> Is there a list comprehension or map expression to do it in one or 2
> lines.
>

Is this a function where you just want to know a w[n]?

then:

def w(n):
return sum((1 + i * 0.1) * (i % 2 and 1 or -1) for i in xrange(n))

otherwise:

n, w, x = 3, [], 0

for y in ((1 + i * 0.1) * (i % 2 and 1 or -1) for i in xrange(n)):
x += y
w.append(x)

 Robert Kern 11-21-2006 10:41 PM

Re: Is there a list comprehension for this?

liam_herron wrote:
> Given:
> dw = [ 1, -1.1, +1.2 ]
>
> Suppose I want to create a list 'w' that is defined as
>
> w[0] = dw[0],
> w[1] = w[0] + dw[1],
> w[2] = w[1] + dw[2]
>
> Is there a list comprehension or map expression to do it in one or 2
> lines.

One way is to use numpy (numpy.scipy.org):

In [40]: from numpy import cumsum

In [41]: dw = [1, -1.1, +1.2]

In [42]: cumsum(dw)
Out[42]: array([ 1. , -0.1, 1.1])

If you're doing a lot of numerical computing, you'll probably want a number of
other things that numpy provides.

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
an underlying truth."
-- Umberto Eco

 Steven D'Aprano 11-22-2006 04:33 AM

Re: Is there a list comprehension for this?

On Tue, 21 Nov 2006 13:19:04 -0800, liam_herron wrote:

>
> Given:
> dw = [ 1, -1.1, +1.2 ]
>
> Suppose I want to create a list 'w' that is defined as
>
> w[0] = dw[0],
> w[1] = w[0] + dw[1],
> w[2] = w[1] + dw[2]
>
> Is there a list comprehension or map expression to do it in one or 2
> lines.

This isn't a list comp and it doesn't need map, but if you
absolutely have to have a one-liner:

w = [dw[0], dw[0] + dw[1], dw[0] + dw[1] + dw[2]]

Obviously that doesn't scale at all to larger lists, but it gives you a
better idea: replace the manual additions with sum().

w = [sum(dw[0:i]) for i in range(1, len(dw))]

but if your dw list is huge, you're spending a lot of time slicing
dw and adding up the same numbers over and over again. (This doesn't
matter if dw is small, but could become expensive if dw is huge.)

Which leads to the next version:

def running_sum(dw):
"""Return a list of the running sums of sequence dw"""
rs = [0]*len(dw)
for i in range(len(dw)):
rs[i] = dw[i] + rs[i-1]
return rs

It isn't a one-liner, but it is clear, the name is self-documenting, it
has a doc-string, you don't have to copy-and-paste code every time you
want to use it, and now that you've defined it once, you can use it as a
one-liner as many times as you like.

>>> running_sum(range(5)):

[0, 1, 3, 6, 10]

--
Steven D'Aprano

 John Machin 11-22-2006 05:00 AM

Re: Is there a list comprehension for this?

Steven D'Aprano wrote:

[snip]

> def running_sum(dw):
> """Return a list of the running sums of sequence dw"""
> rs = [0]*len(dw)
> for i in range(len(dw)):
> rs[i] = dw[i] + rs[i-1]

Please explain to the newbies why there is no exception raised when
rs[i-1] is executed for i == 0, and state whether you consider this is
a Good Idea or a Filthy Trick or a Fortunate Accident.

> return rs
>
> It isn't a one-liner, but it is clear, the name is self-documenting, it
> has a doc-string, you don't have to copy-and-paste code every time you
> want to use it, and now that you've defined it once, you can use it as a
> one-liner as many times as you like.
>
> >>> running_sum(range(5)):

> [0, 1, 3, 6, 10]

 Peter Otten 11-22-2006 07:54 AM

Re: Is there a list comprehension for this?

liam_herron wrote:

>
> Given:
> dw = [ 1, -1.1, +1.2 ]
>
> Suppose I want to create a list 'w' that is defined as
>
> w[0] = dw[0],
> w[1] = w[0] + dw[1],
> w[2] = w[1] + dw[2]
>
> Is there a list comprehension or map expression to do it in one or 2
> lines.

>>> from itertools import *
>>> data = [1, -1.1, 1.2]
>>> N = 2
>>> [sum(item) for item in izip(*[chain(repeat(0, i), di) for i, di in

enumerate(tee(data, N))])]
[1, -0.10000000000000009, 0.099999999999999867]

Should work for other values of N, too. No, I'm not serious about it...

Peter

 Steven D'Aprano 11-22-2006 10:18 AM

Re: Is there a list comprehension for this?

On Tue, 21 Nov 2006 21:00:02 -0800, John Machin wrote:

> Steven D'Aprano wrote:
>
> [snip]
>
>> def running_sum(dw):
>> """Return a list of the running sums of sequence dw"""
>> rs = [0]*len(dw)
>> for i in range(len(dw)):
>> rs[i] = dw[i] + rs[i-1]

>
> Please explain to the newbies why there is no exception raised when
> rs[i-1] is executed for i == 0, and state whether you consider this is
> a Good Idea or a Filthy Trick or a Fortunate Accident.

Because rs[0-1] is just rs[-1], which fetches the LAST item of the list. I
cunningly initialised the list to all zeroes, so adding zero to the first
term doesn't change the result value.

It is a variation of the sentinel technique, where you add an extra value
to the beginning or end of a list so that you don't need to treat the
first or last item differently. In this specific case, I think it is a
combination of Good Idea and Fortunate Accident, but since the
meaning of list[-1] is both deliberate and well-documented, it is
certainly not a Filthy Trick.

--
Steven.

 John Machin 11-22-2006 10:28 AM

Re: Is there a list comprehension for this?

Steven D'Aprano wrote:
> On Tue, 21 Nov 2006 21:00:02 -0800, John Machin wrote:
>
> > Steven D'Aprano wrote:
> >
> > [snip]
> >
> >> def running_sum(dw):
> >> """Return a list of the running sums of sequence dw"""
> >> rs = [0]*len(dw)
> >> for i in range(len(dw)):
> >> rs[i] = dw[i] + rs[i-1]

> >
> > Please explain to the newbies why there is no exception raised when
> > rs[i-1] is executed for i == 0, and state whether you consider this is
> > a Good Idea or a Filthy Trick or a Fortunate Accident.

>
> Because rs[0-1] is just rs[-1], which fetches the LAST item of the list. I
> cunningly initialised the list to all zeroes, so adding zero to the first
> term doesn't change the result value.
>
> It is a variation of the sentinel technique, where you add an extra value
> to the beginning or end of a list so that you don't need to treat the
> first or last item differently. In this specific case, I think it is a
> combination of Good Idea and Fortunate Accident, but since the
> meaning of list[-1] is both deliberate and well-documented, it is
> certainly not a Filthy Trick.
>

Fair enough. But it does make the concerned reader go back a couple of
lines to see why it doesn't run amok. Here's my attempt at a

def running_sum_2(dw):
rs = dw[:1]
for i in xrange(1, len(dw)):
rs.append(dw[i] + rs[-1])
return rs

Cheers,
John

 Steven D'Aprano 11-22-2006 11:41 AM

Re: Is there a list comprehension for this?

On Wed, 22 Nov 2006 02:28:04 -0800, John Machin wrote:

>
> Steven D'Aprano wrote:
>> On Tue, 21 Nov 2006 21:00:02 -0800, John Machin wrote:
>>
>> > Steven D'Aprano wrote:
>> >
>> > [snip]
>> >
>> >> def running_sum(dw):
>> >> """Return a list of the running sums of sequence dw"""
>> >> rs = [0]*len(dw)
>> >> for i in range(len(dw)):
>> >> rs[i] = dw[i] + rs[i-1]
>> >
>> > Please explain to the newbies why there is no exception raised when
>> > rs[i-1] is executed for i == 0, and state whether you consider this is
>> > a Good Idea or a Filthy Trick or a Fortunate Accident.

>>
>> Because rs[0-1] is just rs[-1], which fetches the LAST item of the list. I
>> cunningly initialised the list to all zeroes, so adding zero to the first
>> term doesn't change the result value.
>>
>> It is a variation of the sentinel technique, where you add an extra value
>> to the beginning or end of a list so that you don't need to treat the
>> first or last item differently. In this specific case, I think it is a
>> combination of Good Idea and Fortunate Accident, but since the
>> meaning of list[-1] is both deliberate and well-documented, it is
>> certainly not a Filthy Trick.
>>

>
> Fair enough. But it does make the concerned reader go back a couple of
> lines to see why it doesn't run amok.

Nobody said that every piece of code should be instantly comprehensible
just at a glance. Sometimes you do actually have to think about code to
understand it, even in Python :)

> Here's my attempt at a
>
> def running_sum_2(dw):
> rs = dw[:1]
> for i in xrange(1, len(dw)):
> rs.append(dw[i] + rs[-1])
> return rs
>

Even with xrange() instead of range, it is a little slower than my version
for largish input lists because you are repeatedly appending to a list.

>>> timeit.Timer("running_sum(L)",

.... "from __main__ import running_sum; L = range(500)").timeit(1000)
0.56354999542236328
>>> timeit.Timer("running_sum_2(L)",

.... "from __main__ import running_sum_2; L = range(500)").timeit(1000)
0.68534302711486816

Although the speed difference disappears (or even reverses) for small
enough lists. Either way, it isn't really a major speed difference --
Python's resizing of lists is very smart.

But why build a list of all the running sums when you probably only need
them one at a time? Here's a generator version that can take any iterable,
not just a sequence:

def running_sum_3(iterable):
sum_ = 0
for x in iterable:
sum_ += x
yield sum_

And it is considerably faster than either of the list-only versions:

>>> timeit.Timer("list(running_sum_3(L))",

.... "from __main__ import running_sum_3; L = range(500)").timeit(1000)
0.33915305137634277

--
Steve.

All times are GMT. The time now is 03:34 PM.