Your kadane routines are all bound to have asymptotically poor space usage
under the present interpreter because >./ is not fused; so they all must
create an intermediate result array whose length is the same as ranvec, and
then apply >./. I think (haven't looked very closely) that locmax is the same
as your final answer; so you could skip generating the intermediate array and
simply look at locmax. Better yet, get rid of the global variable, and turn
this all into a fold single (rather than fold multiple), where locmax becomes
the running value.
On Mon, 3 Apr 2023, Elijah Stone wrote:
7!:2 '>./ 1 kadane\ ranvec' [ locmax=: __
1412576
7!:2 '>./ kadane"0 ranvec' [ locmax=: __
772960
7!:2 '>./ kadane"1 ranvec2' [ locmax=: __ [ ranvec2=: ,.ranvec
1412960
1 <@$@$\ i.5
┌─┬─┬─┬─┬─┐
│1│1│1│1│1│
└─┴─┴─┴─┴─┘
<@$@$"0 i.5
┌─┬─┬─┬─┬─┐
│0│0│0│0│0│
└─┴─┴─┴─┴─┘
1 kadane\ y applies kadane to length-1 subsequences of y--that is, in this
case, vectors, which have length 1. Whereas kadane"0 applies to cells of y,
which have rank 0. More space is required to store a length-1 vector than a
scalar, since in the former case the length also needs to be stored.
On Mon, 3 Apr 2023, Thomas McGuire wrote:
I’m wondering if someone with more J internals knowledge can tell me why my
Kadane algorithm implementation is taking up more memory than my naive brute
force method that generates all subsequences then sums them. The time is
about what I would expect except for the FOLD operation. The time space data
were generated on a MacBook Pro 2019 era I9 processor 2.3GHz.
ranvec =: _5 + ?10000$10
kadane =: 3 : 'locmax =: y >. locmax + y'
kadane1 =: 3 : 'locmax =: (] >. locmax&+) y'
NB. first brute force implementation
timespacex '>./(>./@(+/\))\.ranvec'
0.032948 396448
NB. fork version brute force
timespacex '>./([: >./ (+/\))\. ranvec'
0.034208 396448
NB. first kadane implementation
locmax =: __
timespacex '>./ 1 kadane\ranvec'
0.004034 1.41251e6
NB. fork kadane version
locmax =: __
timespacex '>./ 1 kadane1\ranvec'
0.005267 1.41277e6
NB. new dnfs anonymous kadane function
locmax =: __
timespacex '>./ 1 {{locmax =: y >. locmax + y}}\ranvec'
0.003625 1.41347e6
NB. fork dnfs anonymous kadane function
locmax =: __
timespacex '>./ 1 {{locmax =: (] >. locmax&+) y}}\ranvec'
0.004776 1.41386e6
NB. Fold kadane implementation
timespacex '>./ __ ] F:. ([ >. +) ranvec'
0.017393 905792
This was all part of a J Tutorial I have written
https://code.jsoftware.com/wiki/User:Tom_McGuire/KadaneAlgorithmTutorial
Tom McGuire
----------------------------------------------------------------------
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
