Is there a list comprehension for this?

Discussion in 'Python' started by liam_herron, Nov 21, 2006.

  1. liam_herron

    liam_herron Guest

    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.
    liam_herron, Nov 21, 2006
    #1
    1. Advertising

  2. liam_herron

    Tim Chase Guest

    > 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
    Tim Chase, Nov 21, 2006
    #2
    1. Advertising

  3. 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)
    Mathias Panzenboeck, Nov 21, 2006
    #3
  4. liam_herron

    Robert Kern Guest

    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
    that is made terrible by our own mad attempt to interpret it as though it had
    an underlying truth."
    -- Umberto Eco
    Robert Kern, Nov 21, 2006
    #4
  5. 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 = dw + 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
    Steven D'Aprano, Nov 22, 2006
    #5
  6. liam_herron

    John Machin Guest

    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 = dw + 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]
    John Machin, Nov 22, 2006
    #6
  7. liam_herron

    Peter Otten Guest

    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
    Peter Otten, Nov 22, 2006
    #7
  8. 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 = dw + 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.
    Steven D'Aprano, Nov 22, 2006
    #8
  9. liam_herron

    John Machin Guest

    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 = dw + 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
    no-reader-backtracking solution:

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

    Comments invited.

    Cheers,
    John
    John Machin, Nov 22, 2006
    #9
  10. 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 = dw + 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
    > no-reader-backtracking solution:
    >
    > def running_sum_2(dw):
    > rs = dw[:1]
    > for i in xrange(1, len(dw)):
    > rs.append(dw + rs[-1])
    > return rs
    >
    > Comments invited.


    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.
    Steven D'Aprano, Nov 22, 2006
    #10
  11. liam_herron

    John Machin Guest

    Steven D'Aprano wrote:
    > 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 = dw + 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.


    That's correct. I didn't say it, and nobody else did. You argue ad
    extremis, in extremis :)

    My point was merely that it is preferable to be able to understand code
    without having to go "OMG!" and then read backwards ...

    > Sometimes you do actually have to think about code to
    > understand it, even in Python :)


    Correct. However I raised the question explicitly in the context of an
    answer to a *newbie* ("Please explain to the newbies").
    Notwithstandingly, you then mentioned "cunningly" and
    "[well-]documented" and now "think" :)

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

    >


    [snip]

    >
    > Although the speed difference disappears (or even reverses) for small
    > enough lists. Either way, it isn't really a major speed difference --


    As you say. Perhaps I should have stated in advance how many goalposts
    and whether they had a cross-bar or not :) I was hoping for comments
    on the understandibility or otherwise of rs[-1]. My use of xrange was
    out of habit; it wasn't intended to provoke the cannonball run.
    >
    > 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:
    >


    .... and whether the cross-bar had a net slung from it :)

    Why? (1) Because that's what the OP was asking for IIRC. (2) Because
    some applications (at least back when the storage mechanism was squared
    paper) involved cumulative sums of cumulative sums of ... generator
    version, please :)

    N.B. This is even more fun than discussing cricket with my Pommie
    neighbour; keep it up :)

    Best regards,
    John
    John Machin, Nov 22, 2006
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Shane Geiger
    Replies:
    4
    Views:
    376
    bullockbefriending bard
    Mar 25, 2007
  2. Debajit Adhikary
    Replies:
    17
    Views:
    674
    Debajit Adhikary
    Oct 18, 2007
  3. Vedran Furac(
    Replies:
    4
    Views:
    318
    Marc 'BlackJack' Rintsch
    Dec 19, 2008
  4. Peng Yu
    Replies:
    8
    Views:
    339
    Steven D'Aprano
    Nov 20, 2009
  5. Patrick Sabin
    Replies:
    1
    Views:
    309
    Paul Rudin
    Nov 20, 2009
Loading...

Share This Page