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
