Re: [Jprogramming] kadane algorithm vs brute force timing and memory

Generally speaking, when thinking about performance, benchmarking is a critical step. There's a *lot* of theoretical issues which are only approximations, at best. That said, in this case, there's also documentation (if you know where to look). For example: https://wiki.jsoftware.com/wiki/Vocabu

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

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 ┌─┬──┬┬─┬

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

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! ┌┬──┬──

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

(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. He

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

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

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

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.

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

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

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

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

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

> On Apr 3, 2023, at 1:28 PM, Jose Mario Quintana > 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 o

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

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.

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

For what it is worth... kad=. >./@:(([ >. +)/\.) 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 wrote: > Your kadane routines are all bound to have asymptotically poor space usage > under the present inter

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

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 th

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

Fold is a bit slow because it is implemented in j. 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

Re: [Jprogramming] kadane algorithm vs brute force timing and memory

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 appl

[Jprogramming] kadane algorithm vs brute force timing and memory

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 spac