Both >./ and ([ >. +)/\. are linear; thus kad ought to be linear. I think a
more representative test is,
kad=. >./@:(([ >. +)/\.)
Y4=. ?1e4#0
Y5=. ?1e5#0
Y6=. ?1e6#0
Y7=. ?1e7#0
Y8=. ?1e8#0
stp 5
kad Y4
kad Y5
kad Y6
kad Y7
kad Y8
)
Mismatch!
┌────────┬──────────┬──────────┬────────────┐
│Sentence│Space │Time │Space * Time│
├────────┼──────────┼──────────┼────────────┤
│kad Y4 │132256 │0.00064946│85.895 │
├────────┼──────────┼──────────┼────────────┤
│kad Y5 │1049760 │0.00708874│7441.48 │
├────────┼──────────┼──────────┼────────────┤
│kad Y6 │8389792 │0.0835266 │700771 │
├────────┼──────────┼──────────┼────────────┤
│kad Y7 │134218912 │0.756735 │1.01568e8 │
├────────┼──────────┼──────────┼────────────┤
│kad Y8 │1073743008│7.56513 │8.123e9 │
└────────┴──────────┴──────────┴────────────┘
This seems pretty linear to me
On Fri, Apr 7, 2023 at 3:54 AM Raul Miller <rauldmil...@gmail.com> wrote:
> Actually, my summary line should have been
>
> 2 %/\ 5.98958 0.57413 0.0674812 0.0142999 0.002802
> 10.4324 8.508 4.719 5.10346
>
> Also, for comparison:
>
> timex '?1e4#0'
> 0.0002895
> timex '?1e5#0'
> 0.0034291
> timex '?1e6#0'
> 0.0150786
> timex '?1e7#0'
> 0.081682
> timex '?1e8#0'
> 0.927786
>
> 2 %/\ 0.927786 0.081682 0.0150786 0.0034291 0.0002895
> 11.3585 5.41708 4.39725 11.8449
>
> There's two major sources of timing discrepancies here for what would
> "theoretically" be a linear (factor of 10) increase:
>
> (1) arbitrary conflicts with system processes, and
>
> (2) memory cache.
>
> FYI,
>
> --
> Raul
>
> On Fri, Apr 7, 2023 at 3:47 AM Raul Miller <rauldmil...@gmail.com> wrote:
> >
> > This does't look like O(n^2)
> >
> > kad=. >./@:(([ >. +)/\.)
> > timex 'kad ?1e4#0'
> > 0.002802
> > timex 'kad ?1e5#0'
> > 0.0142999
> > timex 'kad ?1e6#0'
> > 0.0674812
> > timex 'kad ?1e7#0'
> > 0.57413
> > timex 'kad ?1e8#0'
> > 5.98958
> >
> > 2 %~/\ 5.98958 0.57413 0.0674812 0.0142999 0.002802
> > 0.0958548 0.117536 0.211909 0.195945
> >
> > --
> > Raul
> >
> > On Fri, Apr 7, 2023 at 3:09 AM Thomas McGuire <tmcguir...@gmail.com>
> 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
