Sorry - correcting mxsasumcrude (below) - some brackets went missing.
It should be
mxsasumcrude =: >./@:(>./@:(+/\)\)
Time and space much the same as below.
Mike
Here's what I previously posted, with inline correction...
=====================================================
Thanks to Raul for pointing out the Rosetta Stone entries at
https://rosettacode.org/wiki/Greatest_subsequential_sum#J
I tried
ts ' maxss q16' [q16 =: 2#8000$ '
but gave up waiting, seeing Windows' Task Manager's display of total
memory
climbing towards 15GB.
Then I spotted maxSS and maxSS2 in the Rosetta posting, both of which are
much faster than my mxsa and mxsasum, though they use more space:
ts'mxsasum q16'
0.033302 134208
ts'mxsa q16'
0.115605 265216
ts'maxSS q16' NB. Rosetta
0.00455016 1.15693e6
ts'maxSS2 q16' NB. Rosetta
0.00405449 1.15757e6
ts'f q16' NB. Jon Hough's post
2.63228 3.48282e6
I had second thoughts about a crude but simple approach - this isn't as bad
as all that:
mxsasumcrude =: >./@:(+/\)\ NB. NO! corrected - should be:
mxsasumcrude =: >./@:(>./@:(+/\)\)
ts'mxsasumcrude q16' NB. this is typical of the corrected version.
1.10747 263616
Still not too bad for space, but pretty slow.
Cheers,
Mike
On 24/02/2019 14:06, 'Mike Day' via Programming wrote:
OK, Jon - I looked at wiki and implemented Kadane, with mxsasum
(explicit) and mxsasumt (tacit)
returning just the best sum, while mxsa returns the subarray.
NB. Kadane's algorithm as presented in wiki
NB. def max_subarray(A):
NB. max_ending_here = max_so_far = A[0]
NB. for x in A[1:]:
NB. max_ending_here = max(x, max_ending_here + x)
NB. max_so_far = max(max_so_far, max_ending_here)
NB. return max_so_far
NB. returns maximal subarray sum only, not subarray
mxsasum =: 3 : 0
mxeh =. mxsf =. {. a =. y
for_x. }.a do.
mxeh =. x + 0 >. mxeh
mxsf =. mxsf >. mxeh
end.
)
NB. first pass at a tacit form of the above - a bit rough!
NB. bolts on mxeh and mxsf to the front of }. of array
NB. and then works through until no array left...
mxsasumt =: ({.`(((2&{+0>.{.)>./\@:,(1&{)),3&}. ) @.(2<#))^:_@: (,~{.)
NB. returns maximal subarray - only the last if more than one!
mxsa =: 3 : 0
mxeh =. mxsf =. {. a =. y
ii =. i =. j =. 0
for_x. }.a do.
ii =. >: ii
i =. (ii, i) {~ ok =. 0 < mxeh
mxeh =. x + ok * mxeh
j =. (ii, j) {~ ok =. mxeh < mxsf
mxsf =. ok { mxeh, mxsf
end.
NB. could just return i,j !
a {~ i ([ + i.@>:@-~ ) j
)
Some timings
ts
6!:2 , 7!:2@]
q =: 8000$3 4 _5 2 1 1 1
ts'mxsasum q'
0.0168 68672
ts'mxsasumt q'
0.11534 1.25056e6
ts'mxsa q'
0.0590112 134144
ts'f q' NB. Jon's one-liner
0.696457 1.74189e6
ts'>./;(+/\)\. q' NB. NOT THE WAY TO DO IT!
1.98149 8.82859e8
>./;(+/\)\. q
8001
mxsasum q
8001
I very much doubt the book is closed on this one!
Mike
On 24/02/2019 11:39, 'Jon Hough' via Programming wrote:
Reference: https://en.wikipedia.org/wiki/Maximum_subarray_problem
This is the problem:
Given an array of numbers, find the contiguous subset of maximum sum.
i.e. find the maximum sum subarray.
Example:
R=: 3 4 _5 2 1 1
The maximum subarray is 3 4
Kadane's algorithm is a linear time algorithm to solve this. Rather
than explicitly implementing this, I wanted a J verb to solve this,
using J primitives.
I wrote a horrendously long one-liner to solve this:
f=: ({.@:I.@:(= >./)@:>@:({:&.>) { ])@:(>:@:i.@:# (({.@:I.@:(= >./)
([ , {) ])@:(+/\) <@,~ [)"0 _ ]) ((i.@:{. + {:)@:}:@:,@:>@:[ { ]) ]
Empirically, I found this to be O(n) in time. e.g.
For an array of length 8000
timespacex gives: 0.25468 3.40134e6
For array of length 16000: 1.03293 6.80102e6
For array of length 32000: 4.09139 1.36004e7
For array of length 64000: 16.3896 2.71991e7
Any better solutions (faster, and more elegant)?
Thanks,
Jon
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
