#1
  1. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Nov 2002
    Posts
    596
    Rep Power
    23

    Maximum segment sum: language comparison


    I am reading Introduction to Functional Programming with Haskell (http://web.comlab.ox.ac.uk/oucl/publications/books/functional/) and was very impressed by the elegance of the solution to the maximum segment sum. The mss of the sequence
    Code:
    [-1, 2, -3, 5, -2, 1, 3, -2, -2, -3, 6]
    is 7, the sum of [5, -2, 1, 3]

    Bird's rather awesome solution to this is
    Code:
    mss = maxlist . scanr (maxZero) 0
                where maxZero x y = 0 `max` (x + y)
                           maxlist = foldr1 (max)
    (Edit - apols, can't get indetation right on haskell code...)
    This manages to be at once dense and not at all unreadable, even for someone learning the language...and I wondered what it would look like in other languages.

    What would this look like in your favourite language? Bring me your scheme, your assembler, your perl! :-) Java lovers win kudos for daring to show their face :-)

    The only one I've tried so far is python. I thought it would be pretty concise too, as lists are home turf and there is some support for higher order funtions, but I was surprised in the end at how may hoops I had to jump through. Python doesn't have anything like scanr and in the book Bird begins with a more easily understandable version
    Code:
    mss = maxlist . map sum . segs
               where segs = concat . map inits . tails
    so I decided to start there, recreating the haskell builtins concat (flatten a list one level), init (return all initial segments of a list) and tails (return all final segments of a list). I also needed to work around the fact that in python list.extend returns None, which is broken IMHO:
    python Code:
     
    from operator import add
    def mss(lst):
        if len(lst) == 0:
            return 0
        segs = getSegs(lst)
        return reduce(max, map ((lambda x: reduce(add, x)), segs))
     
    def getSegs(lst):
        return concat(map((lambda x: inits(x, 0)), tails(lst)))
     
    def myExtend(lst, val):
        lst.extend(val)
        return lst
     
    def tails(lst):
        if len(lst) == 0:
            return []
        return myExtend([lst], tails(lst[1:]))
     
    def inits(lst, count):
        if count > len(lst):
            return []
        return myExtend([lst[0:count]], inits(lst, (count + 1)))
     
    def concat(lst):
        """flatten 1 level and remove empty lists, because python's map won't deal nicely with them."""
        lst2 = []
        for l in lst:
            for m in l:
                if m != []:
                    lst2.append(m)
        return lst2

    So 1 Nil to haskell, and not only because of the builtins. I am no pythonista and hope that someone will prove me wrong with a better version than this.

    Disclaimer: this problem is ideal for a language like haskell, because it specialises in recursion over structures and the point-free and functional composition styles (omitting params from function definitions and syntax like f . g) make it possible to express this all very cleanly.
    Last edited by jamieB; June 10th, 2006 at 02:23 AM. Reason: fixing python function mss
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    London, England
    Posts
    1,585
    Rep Power
    1373
    The algorithm you give looks massively complex and slow - it is at least O(N^2), possibly more (I dont know enough haskell to say for sure).

    There is a much simpler algorithm that is O(N). Here it is in python:

    Code:
    >>> def mss(lst):
    ... 	maxSoFar = 0.0
    ... 	maxEndingHere = 0.0
    ... 	for val in lst:
    ... 	    maxEndingHere = max(maxEndingHere+val, 0.0)	
    ... 	    maxSoFar = max(maxSoFar, maxEndingHere)
    ... 	return maxSoFar
    ... 
    >>> mss([-1, 2, -3, 5, -2, 1, 3, -2, -2, -3, 6])
    7.0
    >>> mss([31,-41,59,26,-53,58,97,-93,-23,84])
    187.0
    This is adapted from the book Programming Pearls by Jon Bentley, which has a whole chapter on alternative algorithms for this problem.

    Bentley goes on to give comparisons of the runtime for the algorithms for different size lists. The difference can be huge -for a large list the runtime for O(N^2) can be measured in months, while for O(N) it is in seconds.

    Dave
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Nov 2002
    Posts
    596
    Rep Power
    23
    Originally Posted by DevCoach
    The algorithm you give looks massively complex and slow - it is at least O(N^2), possibly more (I dont know enough haskell to say for sure).

    There is a much simpler algorithm that is O(N). Here it is in python:

    Code:
    >>> def mss(lst):
    ... 	maxSoFar = 0.0
    ... 	maxEndingHere = 0.0
    ... 	for val in lst:
    ... 	    maxEndingHere = max(maxEndingHere+val, 0.0)	
    ... 	    maxSoFar = max(maxSoFar, maxEndingHere)
    ... 	return maxSoFar
    ... 
    >>> mss([-1, 2, -3, 5, -2, 1, 3, -2, -2, -3, 6])
    7.0
    >>> mss([31,-41,59,26,-53,58,97,-93,-23,84])
    187.0
    This is adapted from the book Programming Pearls by Jon Bentley, which has a whole chapter on alternative algorithms for this problem.

    Bentley goes on to give comparisons of the runtime for the algorithms for different size lists. The difference can be huge -for a large list the runtime for O(N^2) can be measured in months, while for O(N) it is in seconds.

    Dave
    Thanks Dave, that certainly is simpler! I plan to read Bentley's book asap...

    According to Bird the inefficient but easy to understand algorithm I transposed into python is O(n^3). There are about n^2 segments and summing them all takes n^3 steps. He refines this to end up with the first one I showed, which is linear-time like yours.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313

    Obligatory PostScript post :)


    Here is DevCoach's algorithm in PostScript:
    Code:
    /mss {
        0 exch 0 exch {
            add dup 0 lt {
                pop 0
            } if
            2 copy lt {
                exch pop dup
            } if
        } forall
        pop
    } def
    Code:
    GS> [-1 2 -3 5 -2 1 3 -2 -2 -3 6] mss ==
    7
    GS> [31 -41 59 26 -53 58 97 -93 -23 84] mss ==
    187

    Comments on this post

    • LinuxPenguin agrees : I think it's great you're using it a lot, since noone else is :)
  8. #5
  9. Commie Mutant Traitor
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2004
    Location
    Alpharetta, GA
    Posts
    1,806
    Rep Power
    1570
    Here's an admittedly somewhat clumsy version of the Bentley algorithm in Scheme:

    Code:
    (define (max-segment x)  
      (let mss ((segment x)
                (max-ending-here 0.0)
                (max-so-far 0.0))
        (let* ((next-segment (cdr segment))
               (new-sum (max 0.0 (+ (car segment) max-ending-here)))
               (new-max (max new-sum max-so-far)))
          (if (null? next-segment)
              new-max
              (mss next-segment new-sum new-max)))))
    This just doesn't sit well with me, though; I'll try coding the first solution in Scheme later.
    Last edited by Schol-R-LEA; June 17th, 2006 at 02:38 AM.
    Rev First Speaker Schol-R-LEA;2 JAM LCF ELF KoR KCO BiWM TGIF
    #define KINSEY (rand() % 7) λ Scheme is the Red Pill
    Scheme in Short Understanding the C/C++ Preprocessor
    Taming Python A Highly Opinionated Review of Programming Languages for the Novice, v1.1

    FOR SALE: One ShapeSystem 2300 CMD, extensively modified for human use. Includes s/w for anthro, transgender, sex-appeal enhance, & Gillian Anderson and Jason D. Poit clone forms. Some wear. $4500 obo. tverres@et.ins.gov
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Nov 2002
    Posts
    596
    Rep Power
    23
    Originally Posted by Schol-R-LEA
    Here's an admittedly somewhat clumsy version of the Bentley algorithm in Scheme:

    Code:
    (define (max-segment x)  
      (let mss ((segment x)
                (max-ending-here 0.0)
                (max-so-far 0.0))
        (let* ((next-segment (cdr segment))
               (new-sum (max 0.0 (+ (car segment) max-ending-here)))
               (new-max (max new-sum max-so-far)))
          (if (null? next-segment)
              new-max
              (mss next-segment new-sum new-max)))))
    This just doesn't sit well with me, though; I'll try coding the first solution in Scheme later.
    scheme should be a good fit for Bird's algorithm...I'd be interested to see how close you can get to haskell's brevity and elegance.

IMN logo majestic logo threadwatch logo seochat tools logo