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
