Thanks Elijah, I am still getting used to the application of rank as a way of applying a function to individual elements within a vector/array. I don’t have a problem using it to apply things across rows or columns. I still haven’t internalized it as a way to apply it to each individual atom.
kadane”0 it is still much higher memory wise than the brute force methodology operating on suffixes. timespacex 'kadane"0 ranvec' [ locmax=: __ 0.00378 772576 The kadane”0 operating on ranvec takes up about 5 times as much memory as a simple operation. This seems to be due to the assignment to the global accumulator locmax. I ran the following tests: madd =: 3 : 'y + 2 * y' timespacex 'madd"0 ranvec' 0.002836 132640 madd2 =: 3 : 'y + locmax * y' timespacex 'madd2"0 ranvec' 0.003275 132640 sum =: 0 sumv =: 3 : 'sum =: sum + y' timespacex 'sumv"0 ranvec' 0.003425 772576 Once I add an assignment to a global, the memory space goes way up. Not sure from Eljah’s explaination why a single global assignment of an operation on a cell should cause such a large memory requirement? Tom McGuire > On Apr 3, 2023, at 5:22 AM, Elijah Stone <elro...@elronnd.net> 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