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 <[EMAIL PROTECTED]>
To: Programming forum <[email protected]>
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
