> On Apr 3, 2023, at 1:28 PM, Jose Mario Quintana > <[email protected]> wrote: > > For what it is worth... > > kad=. >./@:(([ >. +)/\.) > OK that is worth a lot. But it’s not really the kadane algorithm. It inserts a kadane-like summation in between elements for each suffix generated. Kadane obtains the sum on a single pass through the array. However it’s an incredibly elegant refactoring of the brute force example and saves performing partial sums on the suffixes.
I will say after figuring out exactly what is was doing it wasn’t intuitively obvious (to me anyway) that this should work. A naive view is that the largest sum in the example below is produced by the subsequence : 4 _1 2 1 So that sequence is never generated in Jose’s version of maximum sum. However due to it’s Kadane-like properties it is generating the highest sum for each suffix as if the partial sum started at the first element. In essence using a kadane-like approach in place of performing partial sums. Therefore in one pass on each suffix you find the greatest partial sum without having to calculate each partial sum individually. Jose’s version is fairly quick coming in at about double the processing time of Jose’s kadane”0 version and well below the brute force method of taking the partial sums of all the suffixes. Tom McGuire > For example, the maximum sum subarray, > > > kad _2 1 _3 4 _1 2 1 _5 4 > 6 > > > kad i.0 > __ > > > > > > On Mon, Apr 3, 2023 at 5:22 AM Elijah Stone <[email protected]> wrote: > >> 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 >> > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
