For what it is worth... kad=. >./@:(([ >. +)/\.)
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
