{{max/w-min\w}+\w}
{max/(-min\)+\w}
The latter may be an equivalent formulation in
Dyalog APL (although probably not faster).
----- Original Message -----
From: Mike Day <[EMAIL PROTECTED]>
Date: Tuesday, April 17, 2007 6:54 am
Subject: [Jprogramming] maximum running sum - understanding scan revisited
> Hacking away at yet another MathsChallenge problem,
> (see http://projecteuler.net/index.php?section=about)
> I needed an efficient verb for finding the maximum
> running sum of an array. I seem to have stumbled on
> a really good one, which surprisingly appears to be
> better than Eugene's J version of a K verb mentioned
> in the correspondence below. Eugene's article is
> also available online at
> http://www.jsoftware.com/jwiki/Doc/Articles/Play152
>
> [Mathschallengers - this was for problem 149. You
> might wish to ignore the details below!]
>
> Apologies to the K group for the verbosity, but
> I'm trying to cover three languages here.
>
> Given Eugene's example vector:
> x =: 31 _41 59 26 _53 58 97 _93 _23 84
> define two verbs:
> mrs =: >./@(- <./\)@(+/\) NB. max run sum
> NB. ie max over (element - min so far) of cumulative sum
>
> NB. cf Eugene MacDonell's max infix sum ...
> mis =: [: >./ [: (0 >. +)/\. 0 ,~ ]
>
> (mrs,mis) x NB. same answer
> 187 187
>
> Timing for 10000 elements
> y=:10000$0 _3 8 _1 _8 2 5 _5 5 3 8 0 _10 _5 _1 _4 4 _10 _4 _6
> (mrs-:mis) y
> 1
> Time & Space
> >ts each ('mrs y');'mis y'
> 9.4146e_5 197440
> 0.00611307 132288
>
> Here's a K version:
> kmrs=:{|/{x-&\x}0+\x} / new K max run sum NB. K version
> f : |/0(0|+)\ / EM's quoted K function
> y: 0 -3 8 -1 -8 2 5 -5 5 3 8 0 -10 -5 -1 -4 4 -10 -4 -6
> \t do[1000;f 10000#y] / time for 1000 applications of f on 10000
> elts of y
> 2954
> \t do[1000;kmrs 10000#y]
> 100
>
> And a Dyalog APL Dfn:
> y <- 10000 rho 0 -3 8 -1 -8 2 5 -5 5 3 8 0 -10 -5 -1 -4 4 -
> 10 -4 -6
> {{max/w-min\w}+\w} y @ "max" "min" and "w" are APL symbols
> 18
> @ time it using compare (cmpx) function:
>
> cmpx'{{max/w-min\w}+\w}y ' @ 10x slower than J & K!
>
> {{max/w-min\w}+\w}y 6.7E¯4
>
> I discovered this independently a couple of days ago, but
> must confess to finding that someone had got there before:
> http://ostermiller.org/calc/sum.html,
> according to his description of his algorithm.
> Hardly surprising, though that I couldn't see anything
> better in recent J K or APL discussion group messages.
>
> Mike
>
>
> back in October 2007, Eugene McDonnell wrote:
> >
> > On Oct 16, 2006, at 3:00 PM, Miller, Raul D wrote:
> >
> >> I wrote:
> >>> (0 >. +)/&.|.\ a
> >>>
> >>> / is right to left, but gambler uses left to right.
> >>> /(&.|.) is left to right.
> >>
> >> &. is unnecessary and could cause problems in the general
> >> case (not this specific case). As & is sufficient, I should
> >> have said:
> >>
> >> (0 >. +)/&|.\ a
> >>
> >> and so on.
> >>
> >> -- Raul
> >
> > The At Play With J article in Vector 15.2, October 1998, has a
> > discussion of what it calls "Maximum Infix Sums" which may
> pertain to
> > this problem.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
