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
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
┌─┬──┬┬─┬
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!
┌┬──┬──
I've gone ahead and changed the page to address some functional issues.
(Note: I'm using "functional" here in the sense of "working" rather
than as a reference to "functional programming style". That said, I
have not tested everything on the page, and it's entirely possible
that I've overlooked so
(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
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
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.
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