[Jprogramming] maximum running sum - understanding scan revisited

[Mike Day]

FWIW, "my" method can also provide the index,
with somewhat better time performance at the
expense of greater space consumption. 

   ((i.,])>./) (-<./\) +/\y     NB. Mike
10 18
   ts'((i.,])>./) (-<./\) +/\y' NB. time & space
0.000215111 199424

   ((i.,])>./) (0>. +)/scanl y  NB. Jasmin
10 18
   ts'((i.,])>./) (0>. +)/scanl y'
0.00619241 134400
 
Mike

Pascal Jasmin wrote:
> I like the scanl concept from haskell
> scanl =: \.(&.|.)
>    < scanl i.4
> +-+---+-----+-------+
> |0|1 0|2 1 0|3 2 1 0|
> +-+---+-----+-------+
>
> The advantage of using the scanl solution below is that you also easily get the location of the ending index that gives the maximum sum.  Its not much slower.
>
>    ts '>./ (0>. +)/\.   y'
> 0.00594102753319 67712
>    >./ (0>. +)/ scanl   y
> 18
>    ts '>./ (0>. +)/ scanl   y'
> 0.0107060647528 133888
>
> end index of maximum sum:
>    (i.>./) (0>. +)/ scanl   y
> 10
>
> ----- Original Message ----
> From: ramacd <ramacd at nbnet.nb.ca>
> To: Programming forum <programming at jsoftware.com>
> Sent: Tuesday, April 17, 2007 10:37:19 AM
> Subject: Re: [Jprogramming] maximum running sum - understanding scan revisited
>
> Mike;
>
> Bravo on discovering that insight. The page on ostermiller.org was #2 on 
> a Google search for "maximum
> running sum" so, note to self, Google is your friend.
>
>
>
> Mike Day wrote:
>   
>> 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
>>>       
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
>>     
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
>
>
>
>
>       Get news delivered with the All new Yahoo! Mail.  Enjoy RSS feeds right on your Mail page. Start today at http://mrd.mail.yahoo.com/try_beta?.intl=ca
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
>
>