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
