Maximum segment sum: language comparison

Dev Shed Forums Sponsor:

SlickEdit: Code in over 40 languages across 7 platforms. SlickEdit’s unmatched power, speed, and flexibility allows even the most accomplished developers to write better code faster. Download a free trial today!

June 9th, 2006, 04:33 PM

jamieB

Contributing User

Join Date: Nov 2002

Posts: 592

Time spent in forums: 2 Days 1 h 55 m 17 sec
Reputation Power: 17

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:

Original - 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

June 10th, 2006, 04:15 AM

DevCoach

Contributing User

Join Date: Feb 2004

Location: London, England

Posts: 1,188

Time spent in forums: 1 Week 5 Days 11 h 25 m 43 sec
Reputation Power: 251

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

June 10th, 2006, 06:42 AM

jamieB

Contributing User

Join Date: Nov 2002

Posts: 592

Time spent in forums: 2 Days 1 h 55 m 17 sec
Reputation Power: 17

Quote:

Originally Posted by DevCoach

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

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.

June 16th, 2006, 02:29 PM

Lux Perpetua

Contributing User

Join Date: Feb 2004

Location: San Francisco Bay

Posts: 1,416

Time spent in forums: 3 Weeks 4 Days 22 h 4 m 53 sec
Reputation Power: 334

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

June 17th, 2006, 02:13 AM

Schol-R-LEA

Commie Mutant Traitor

Join Date: Jun 2004

Location: The People's Republic of Berkeley

Posts: 1,070

Time spent in forums: 3 Weeks 4 Days 39 m 40 sec
Reputation Power: 443

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.

__________________
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

Last edited by Schol-R-LEA : June 17th, 2006 at 02:38 AM.

June 17th, 2006, 04:43 AM

jamieB

Contributing User

Join Date: Nov 2002

Posts: 592

Time spent in forums: 2 Days 1 h 55 m 17 sec
Reputation Power: 17

Quote:

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.

Thread Tools	Search this Thread
Email this Page	Search this Thread: Advanced Search
Display Modes	Rate This Thread
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode	Rate This Thread: