OK thanks to you, Raul and Henry I think I have gotten this through my thick
head. The crux of my misunderstanding are the results you get from performing
the box verb with the suffixes adverb:
<\. _2 1 _3 4 _1 2 1 _5 4
┌─────────────────────┬──────────────────┬────────────────┬─────────────┬───────────┬────────┬──────┬────┬─┐
│_2 1 _3 4 _1 2 1 _5 4│1 _3 4 _1 2 1 _5 4│_3 4 _1 2 1 _5 4│4 _1 2 1 _5 4│_1 2 1
_5 4│2 1 _5 4│1 _5 4│_5 4│4│
└─────────────────────┴──────────────────┴────────────────┴─────────────┴───────────┴────────┴──────┴────┴─┘
From what you are saying this is made by a linear walk through the list. The
results being displayed are essentiall intermediate results from serial
appending going on inside of J.
So when I broke down the ‘kad’ algorithm it was my ignorance that made me line
up the above with the ([ >. +)/ operation and think this was being done more
than a single pass through the original list.
Wow.
Thanks for being so patient with me.
Tom McGuire
> On Apr 7, 2023, at 9:51 AM, Henry Rich <henryhr...@gmail.com> wrote:
>
> (u/\. y) is defined as operating on successive suffixes, making it apparently
> O(n^2), but the implementation runs right to left in (n-1) applications of u.
> The result of each suffix is fed into the next-larger suffix.
>
> (u/\ y), OTOH, runs in O(n^2) time unless u is known to be associative.
>
> Henry Rich
>
> On 4/7/2023 3:09 AM, Thomas McGuire wrote:
>> In my haste to produce an email after finally figuring out how Pepe’s
>> elegant J implementation of the maximal sum of the subsequences worked ,I
>> can see how you might interpret this as I was disappointed in the
>> implementation as not being “pure” kadane. I meant only to classify the
>> implementation so that the CPU times I was recording made sense
>>
>> From the perspective of big O analysis. Pure kadane is O(n). Where Pepe’s
>> algorithm is being applied to a list (of length n) of lists of varying
>> length 1..n, The operation performed 1+1+2+…+n-1 times. Which places it
>> about O(n^2) though it’s been a while since I have done any algorithm
>> analysis.
>>
>> In terms of a J implementation of the broader category of maximal sum of the
>> subsequences of a list of numbers, Pepe’s algorithm is fantastic. From the
>> perspective of my tutorial it is an incredibly insightful jump from the
>> naive brute force implementations I had used. It is such a concise J
>> implementation that highlights a significant portion of J’s advanced
>> techniques. I intend on adding it to my tutorial I just hope I can explain
>> it well enough to make it accessible to my target audience.
>>
>>
>>> On Apr 6, 2023, at 10:55 PM, Henry Rich <henryhr...@gmail.com> wrote:
>>>
>>> I think that when you say Pepe's code is not the Kadane algorithm you are
>>> conflating algorithm and implementation.
>>>
>>> Kadane's idea is that (1) at each new prospective starting point for the
>>> maximal sequence, you have the option of starting at 0 or the previous best
>>> total; (2) every position is a prospective ending point. Pepe's algorithm
>>> follows these observations.
>>>
>>> The usual implementations keep two values through the loop: (a) the maximum
>>> value found on sequences that have ended; (b) the current total on
>>> sequences that the new value may add onto.
>>>
>>> Well, that's one way to do it. Another is to produce (a) as an
>>> intermediate result for each possible ending position, and then at the end
>>> see which of those values is the largest. That's what Pepe did. I approve
>>> his decision, since keeping two values through the scan would require
>>> ponderous indexing operations. This is the sort of implementation decision
>>> that surprises users of compiled languages.
>>>
>>> Pepe's implementation in no way changes the algorithm. It's merely a
>>> reordering of when comparisons are made. Pepe's algorithm is O(n), just as
>>> the usual algorithms are.
>> As I tried to explain above the ([ >. +)/ is O(n) but when used on suffixes
>> with the ‘\.’ operator it becomes O(n^2). the kadane”0 implementation that
>> Elijah proposed operates through the array one at a time in O(n) producing a
>> list of possible maximal sums which is extracted with >./ also in O(n). That
>> kadane algorithm uses your technique in Chapter 25 Loopless Code VI, to
>> perform a single run through the array.
>>
>> Just trying to be accurate so I can explain the implementations correctly in
>> my essay.
>>> Pepe knew that >./ is very fast, probably 10% of the time of the other bit.
>>> The time spent in (([ >. +)/\.) is O(n), not worth our discussion; but if
>>> you want to blame someone for the speed, blame the implementation (i. e.
>>> me), not the algorithm. Perhaps (+ 00&>.)~/\. would be faster; I haven't
>>> tested it, but we're down to minute questions of instruction ordering.
>> No complaints about J’s speed. Even the naive brute force implementation
>> runs in less than a second on a 10000 element array. I have been using the
>> timings as a relative guage that the various implementations work the way I
>> think they are supposed to.
>>
>> The one thing I did have a question on now that I’ve drawn you into this
>> thread. Is that the memory requirement for Pepe’s algorithm is about 1/5 the
>> size of the kadane”0 algorithm. The global variable assignment appears to be
>> the operation that causes the large amount of memory to be used. Elijah
>> tried to explain it and hsi explanation is valid for some of the
>> implementations such as the use of ‘\’ and Fold. But I don’t understand in
>> the setting of a global variable.
>>
>> Tom McGuire
>>> Henry Rich
>>>
>>>
>>>
>>>
>>> On 4/6/2023 8:12 PM, Thomas McGuire wrote:
>>>>> On Apr 3, 2023, at 1:28 PM, Jose Mario Quintana
>>>>> <jose.mario.quint...@gmail.com> 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 <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
>>>> ----------------------------------------------------------------------
>>>> 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
