Need help in understanding a python code

Discussion in 'Python' started by silverburgh.meryl@gmail.com, Nov 16, 2008.

  1. Guest

    Hi,

    I am trying to understand the following line:
    # a is an integer array

    max([(sum(a[j:i]), (j,i))

    Can you please tell me what that means,
    I think sum(a[j:i] means find the some from a[j] to a
    But what is the meaning of the part (j,i)?
    , Nov 16, 2008
    #1
    1. Advertising

  2. Chris Rebert Guest

    On Sat, Nov 15, 2008 at 8:41 PM,
    <> wrote:
    > Hi,
    >
    > I am trying to understand the following line:
    > # a is an integer array
    >
    > max([(sum(a[j:i]), (j,i))


    This code isn't valid. You have a [ with no closing ].

    Cheers,
    Chris
    --
    Follow the path of the Iguana...
    http://rebertia.com

    >
    > Can you please tell me what that means,
    > I think sum(a[j:i] means find the some from a[j] to a
    > But what is the meaning of the part (j,i)?
    >
    > --
    > http://mail.python.org/mailman/listinfo/python-list
    >
    Chris Rebert, Nov 16, 2008
    #2
    1. Advertising

  3. John Machin Guest

    On Nov 16, 3:41 pm, ""
    <> wrote:
    > Hi,
    >
    > I am trying to understand the following line:
    > # a is an integer array
    >
    > max([(sum(a[j:i]), (j,i))
    >
    > Can you please tell me what that means,
    > I think sum(a[j:i] means find the some from a[j] to a
    > But what is the meaning of the part (j,i)?


    0. "integer array" is a very loose term in Python. Fortunately the
    answer to your question is not affected by that.
    1. Sorry, the max... line is not syntactically correct; there are two
    [s and only one ]; there are 4 (s and only 3 )s. Try copying the line
    and pasting, not re-typing.
    2. I'm not going to try to guess how to fix the bracket mismatches.
    3. Note that you have left off a ) from your question about "sum" ...
    it probably should be sum([j:i]).
    4. That is the sum (not "some"!!) of a[j] to a[i-1] both inclusive.
    It's a standard idiom in Python for the end of a range to be expressed
    as the first unused element.
    5. Even after fixing the bracket mismatches, it looks like you will
    have an expression whose value is thrown away. Perhaps you might like
    to give us a few lines of context before and after the line of
    interest.
    John Machin, Nov 16, 2008
    #3
  4. This is the full source code:
    def A(w, v, i,j):
    if i == 0 or j == 0: return 0
    if w[i-1] > j: return A(w, v, i-1, j)
    if w[i-1] <= j: return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))

    I am reading this blog

    http://20bits.com/articles/introduction-to-dynamic-programming/


    On Sat, Nov 15, 2008 at 10:54 PM, Chris Rebert <> wrote:
    > On Sat, Nov 15, 2008 at 8:41 PM,
    > <> wrote:
    >> Hi,
    >>
    >> I am trying to understand the following line:
    >> # a is an integer array
    >>
    >> max([(sum(a[j:i]), (j,i))

    >
    > This code isn't valid. You have a [ with no closing ].
    >
    > Cheers,
    > Chris
    > --
    > Follow the path of the Iguana...
    > http://rebertia.com
    >
    >>
    >> Can you please tell me what that means,
    >> I think sum(a[j:i] means find the some from a[j] to a
    >> But what is the meaning of the part (j,i)?
    >>
    >> --
    >> http://mail.python.org/mailman/listinfo/python-list
    >>

    >
    Meryl Silverburgh, Nov 16, 2008
    #4
  5. Aaron Brady Guest

    See below.

    On Nov 15, 11:15 pm, "Meryl Silverburgh" <>
    wrote:
    > This is the full source code:
    > def A(w, v, i,j):
    >     if i == 0 or j == 0: return 0
    >     if w[i-1] > j:  return A(w, v, i-1, j)
    >     if w[i-1] <= j: return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))
    >
    > I am reading this blog
    >
    > http://20bits.com/articles/introduction-to-dynamic-programming/
    >
    > On Sat, Nov 15, 2008 at 10:54 PM, Chris Rebert <> wrote:
    > > On Sat, Nov 15, 2008 at 8:41 PM,
    > > <> wrote:
    > >> Hi,

    >
    > >> I am trying to understand the following line:
    > >> # a is an integer array

    >
    > >> max([(sum(a[j:i]), (j,i))

    >
    > > This code isn't valid. You have a [ with no closing ].

    >
    > > Cheers,
    > > Chris
    > > --
    > > Follow the path of the Iguana...
    > >http://rebertia.com

    >
    > >> Can you please tell me what that means,
    > >> I think sum(a[j:i] means find the some from a[j] to a
    > >> But what is the meaning of the part (j,i)?

    >
    > >> --
    > >>http://mail.python.org/mailman/listinfo/python-list

    >
    >



    > if w[i-1] <= j: return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))


    This means:

    Calculate 'A(w,v, i-1, j)', calculate 'v[i-1] + A(w,v, i-1, j - w
    [i-1])', and return whichever is larger.
    Aaron Brady, Nov 16, 2008
    #5
  6. Guest

    silverburgh:
    > max([(sum(a[j:i]), (j,i))


    Other people have already answered you so I'll add only a small note:
    today the max() function has a key optional attribute, so that code
    can also be written as:

    max(((j, i) for ...), key=lambda (j, i): sum(a[j : i]))

    I think you have copied that part from code that runs in O(n^2);
    remember that you can find the max subarray with a well known O(n)
    algorithm too.

    Bye,
    bearophile
    , Nov 16, 2008
    #6
  7. John Machin Guest

    On Nov 16, 4:15 pm, "Meryl Silverburgh" <>
    wrote:
    > This is the full source code:
    > def A(w, v, i,j):
    >     if i == 0 or j == 0: return 0
    >     if w[i-1] > j:  return A(w, v, i-1, j)
    >     if w[i-1] <= j: return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))


    Huh??? There is only a very slight resemblance to the code that you
    posted previously ... both contain 'max, 'i', and 'j'

    > I am reading this blog
    >
    > http://20bits.com/articles/introduction-to-dynamic-programming/


    I suggest that you don't bother reading a blog written by somebody who
    (presumably consciously) keyed in that "if w[i-1] <= j: " above.

    Oh, very interesting, it contains:
    def msum(a):
    return max([(sum(a[j:i]), (j,i)) for i in range(1,len(a)+1) for j
    in range(i)])

    Would you care to tell us which part of which function you are now
    trying to understand?
    John Machin, Nov 16, 2008
    #7
  8. On Sun, 16 Nov 2008 01:50:16 -0800, John Machin wrote:

    > > def A(w, v, i,j):
    > >     if i == 0 or j == 0: return 0
    > >     if w[i-1] > j:  return A(w, v, i-1, j)
    > >     if w[i-1] <= j: return max(A(w,v, i-1, j), v[i-1] +
    > > A(w,v, i-1, j - w[i-1]))



    >> I am reading this blog
    >>
    >> http://20bits.com/articles/introduction-to-dynamic-programming/

    >
    > I suggest that you don't bother reading a blog written by somebody who
    > (presumably consciously) keyed in that "if w[i-1] <= j: " above.


    That is a translation of standard terminology for a hybrid function.
    Mathematics doesn't have an "else", so you write hybrid functions by
    enumerating each branch as an if.

    While it's not especially good Python technique, it's a perfectly
    idiomatic mathematical expression, and shouldn't be the basis for
    dismissing an entire blog.


    --
    Steven
    Steven D'Aprano, Nov 16, 2008
    #8
  9. John Machin Guest

    On Nov 16, 9:31 pm, Steven D'Aprano <st...@REMOVE-THIS-
    cybersource.com.au> wrote:
    > On Sun, 16 Nov 2008 01:50:16 -0800, John Machin wrote:
    > > > def A(w, v, i,j):
    > > >     if i == 0 or j == 0: return 0
    > > >     if w[i-1] > j:  return A(w, v, i-1, j)
    > > >     if w[i-1] <= j: return max(A(w,v, i-1, j), v[i-1] +
    > > >       A(w,v, i-1, j - w[i-1]))
    > >> I am reading this blog

    >
    > >>http://20bits.com/articles/introduction-to-dynamic-programming/

    >
    > > I suggest that you don't bother reading a blog written by somebody who
    > > (presumably consciously) keyed in that "if w[i-1] <= j: " above.

    >
    > That is a translation of standard terminology for a hybrid function.
    > Mathematics doesn't have an "else", so you write hybrid functions by
    > enumerating each branch as an if.


    An else is not required.
    if w[i-1] > j:
    return A(w, v, i-1, j)
    return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))

    > While it's not especially good Python technique, it's a perfectly
    > idiomatic mathematical expression, and shouldn't be the basis for
    > dismissing an entire blog.


    He's meant to be writing Python code, not mathematical expressions.
    John Machin, Nov 16, 2008
    #9
  10. On Sun, 16 Nov 2008 02:41:03 -0800, John Machin wrote:

    > On Nov 16, 9:31 pm, Steven D'Aprano <st...@REMOVE-THIS-
    > cybersource.com.au> wrote:
    >> On Sun, 16 Nov 2008 01:50:16 -0800, John Machin wrote:
    >> > > def A(w, v, i,j):
    >> > >     if i == 0 or j == 0: return 0
    >> > >     if w[i-1] > j:  return A(w, v, i-1, j) if w[i-1] <= j: return
    >> > >     max(A(w,v, i-1, j), v[i-1] +
    >> > >       A(w,v, i-1, j - w[i-1]))
    >> >> I am reading this blog

    >>
    >> >>http://20bits.com/articles/introduction-to-dynamic-programming/

    >>
    >> > I suggest that you don't bother reading a blog written by somebody
    >> > who (presumably consciously) keyed in that "if w[i-1] <= j: " above.

    >>
    >> That is a translation of standard terminology for a hybrid function.
    >> Mathematics doesn't have an "else", so you write hybrid functions by
    >> enumerating each branch as an if.

    >
    > An else is not required.
    > if w[i-1] > j:
    > return A(w, v, i-1, j)
    > return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))


    Which is also not valid terminology for hybrid functions.


    >> While it's not especially good Python technique, it's a perfectly
    >> idiomatic mathematical expression, and shouldn't be the basis for
    >> dismissing an entire blog.

    >
    > He's meant to be writing Python code, not mathematical expressions.


    And he's written Python code. Perfectly valid Python code. Just because
    it is not what you consider to be idiomatic Python code isn't a good
    reason to dismiss his entire blog.

    What you've done is rather like me saying that because you failed to use
    a colon after "required", and therefore haven't written what *I* consider
    good English style, not only is your specific post best avoided, but
    *all* your posts should be avoided. I trust you understand the logical
    fallacy I would be making, which you have already made.

    http://en.wikipedia.org/wiki/Style_over_substance_fallacy



    --
    Steven
    and now begins the arguments as to whether it is a fallacy, and if so, if
    it is the fallacy I have said it is...
    Steven D'Aprano, Nov 16, 2008
    #10
  11. John Machin Guest

    On Nov 16, 11:04 pm, Steven D'Aprano <st...@REMOVE-THIS-
    cybersource.com.au> wrote:
    > On Sun, 16 Nov 2008 02:41:03 -0800, John Machin wrote:
    > > On Nov 16, 9:31 pm, Steven D'Aprano <st...@REMOVE-THIS-
    > > cybersource.com.au> wrote:
    > >> On Sun, 16 Nov 2008 01:50:16 -0800, John Machin wrote:
    > >> > > def A(w, v, i,j):
    > >> > >     if i == 0 or j == 0: return 0
    > >> > >     if w[i-1] > j:  return A(w, v, i-1, j) if w[i-1] <= j: return
    > >> > >     max(A(w,v, i-1, j), v[i-1] +
    > >> > >       A(w,v, i-1, j - w[i-1]))
    > >> >> I am reading this blog

    >
    > >> >>http://20bits.com/articles/introduction-to-dynamic-programming/

    >
    > >> > I suggest that you don't bother reading a blog written by somebody
    > >> > who (presumably consciously) keyed in that "if w[i-1] <= j: " above.

    >
    > >> That is a translation of standard terminology for a hybrid function.
    > >> Mathematics doesn't have an "else", so you write hybrid functions by
    > >> enumerating each branch as an if.

    >
    > > An else is not required.
    > >     if w[i-1] > j:
    > >        return A(w, v, i-1, j)
    > >     return max(A(w,v, i-1, j), v[i-1] + A(w,v, i-1, j - w[i-1]))

    >
    > Which is also not valid terminology for hybrid functions.


    I couldn't care less. It's valid and efficient (compared to the
    original) Python.

    > >> While it's not especially good Python technique, it's a perfectly
    > >> idiomatic mathematical expression, and shouldn't be the basis for
    > >> dismissing an entire blog.

    >
    > > He's meant to be writing Python code, not mathematical expressions.

    >
    > And he's written Python code. Perfectly valid Python code. Just because
    > it is not what you consider to be idiomatic Python code isn't a good
    > reason to dismiss his entire blog.
    >
    > What you've done is rather like me saying that because you failed to use
    > a colon after "required", and therefore haven't written what *I* consider
    > good English style, not only is your specific post best avoided, but
    > *all* your posts should be avoided. I trust you understand the logical
    > fallacy I would be making, which you have already made.


    Nothing to do with style. It was the screaming inefficiency of:
    if non_trivial_condition: return x
    if not non_trivial_condition: return y
    that fired me up.

    > http://en.wikipedia.org/wiki/Style_over_substance_fallacy


    Quoted Wikipedia -> instant disqualification -> you lose. Good night.
    John Machin, Nov 16, 2008
    #11
  12. On Nov 16, 7:34 am, John Machin <> wrote:
    > On Nov 16, 11:04 pm, Steven D'Aprano <st...@REMOVE-THIS-
    >
    > >http://en.wikipedia.org/wiki/Style_over_substance_fallacy

    >
    > Quoted Wikipedia -> instant disqualification -> you lose. Good night.


    When quoting wikipedia became the new Godwin's law ?? :)

    George
    George Sakkis, Nov 16, 2008
    #12
  13. alex23 Guest

    On Nov 17, 5:26 am, George Sakkis <> wrote:
    > When quoting wikipedia became the new Godwin's law ?? :)


    Probably at the point the editors started becoming revisionists and
    culling anything they didn't consider notable enough.
    alex23, Nov 17, 2008
    #13
  14. Benjamin Kaplan wrote:
    > If you really believe that, you haven't been following this list long
    > enough. Every terminology dispute always includes at least 1 Wikipedia
    > link.
    >
    > Also, you might want to look at this study:
    > http://news.cnet.com/2100-1038_3-5997332.html


    That study has been disputed; see the links at the top of
    <http://en.wikipedia.org/wiki/Reliability_of_Wikipedia>.

    /me ducks
    --
    Matt Nordhoff, Nov 17, 2008
    #14
  15. alex23 Guest

    On Nov 17, 11:40 am, Matt Nordhoff <> wrote:
    > That study has been disputed; see the links at the top of
    > <http://en.wikipedia.org/wiki/Reliability_of_Wikipedia>.


    Now, if there was any independent refutation of the original study
    that isn't based on Britannica's - not that I'm outright accusing them
    of any bias here :) - that might make a reasonable disputation...
    alex23, Nov 17, 2008
    #15
  16. On Sun, 16 Nov 2008 04:34:40 -0800, John Machin wrote:

    > Nothing to do with style. It was the screaming inefficiency of:
    > if non_trivial_condition: return x
    > if not non_trivial_condition: return y
    > that fired me up.


    "Screaming inefficiency"?

    Try "micro-optimization". The difference in execution time between "if
    x... if not x..." versus "if x... else..." on my slow, underpowered
    machine is about 10**-8 seconds. If that's your idea of "screaming
    inefficiency" I can't understand why you're programming in Python in the
    first place.

    Of course, if x is an expensive function call (say, a network lookup or
    database query rather than a relatively cheap list indexing operation)
    then the more readable, Pythonic solution will also be significantly
    faster. There's no doubt that it should be preferred -- I'm not defending
    it, as such, just pointing out the over-reaction of dismissing what is a
    generally well-written and thought-out article on the basis of a
    triviality.



    >> http://en.wikipedia.org/wiki/Style_over_substance_fallacy

    >
    > Quoted Wikipedia -> instant disqualification -> you lose. Good night.



    Oh gosh, well, you've certainly proven your case, how could I be so
    stupid? My apology for thinking that you were acting like an arrogant,
    bad-tempered dick. I don't know *what* I was thinking.



    --
    Steven
    who would link to Wikipedia for the definition of sarcasm except I've
    already lost once in this thread and that's enough.
    Steven D'Aprano, Nov 18, 2008
    #16
    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. Replies:
    2
    Views:
    402
    Phlip
    Mar 15, 2007
  2. Need help in understanding c code

    , Jun 1, 2007, in forum: C Programming
    Replies:
    2
    Views:
    300
    Barry Schwarz
    Jun 2, 2007
  3. Daniel
    Replies:
    8
    Views:
    424
    Daniel
    Sep 13, 2007
  4. Elmbrook

    need help understanding this code.

    Elmbrook, Sep 28, 2003, in forum: Javascript
    Replies:
    7
    Views:
    144
    Elmbrook
    Sep 29, 2003
  5. Ben
    Replies:
    6
    Views:
    102
    Tim McDaniel
    Apr 16, 2009
Loading...

Share This Page