I thought that perhaps this could be fast:
A=. ?. 1e8#1e3
timespacex '100 (2 i.~ +/\)@:E. A' NB. or = instead of E.
0.460527 1.20796e9
This application happens to everyone at least once, if
(u { I.@E.)
had special code where the result of u (or simply m) is presumed (for speed
optimization) to be a list/atom of top (rather than last) occurrences of
matches.
Here is a dyad that returns the xth occurrences (indexes) of x in y if they
exist. where x is in format x (, or ;) m where m is the list of indexes
requested.
It is a bit slow due to the y =. n }. y step.
xm =: {. ,&boxopen }. NB. split arguments as head ; tail. assignment as 'h t'
=. xm y
findxth =: 4 : 0
'x m' =. xm x NB. m is sorted list of find indexes. x is match value.
if. 0 = #m do. m =. 0 end.
acc =. i.0
oset =. 0
for_i. i. >./ m do.
idx =. x i.~ y
if. idx = # y do. acc return. end.
if. i e. m do. acc =. acc , oset + idx end.
oset =. oset + >: idx
y =. (>: idx) }. y
end.
acc , oset + x i.~ y
)
1 1 3 4 6 findxth 0 1 0 0 1 0 1 1 1
4 7 8
(1 ; 1 3 4 6) findxth 0 1 0 0 1 0 1 1 1
4 7 8
1 findxth 0 1 0 0 1 0 1 1 1
1 NB. m is 0 (first item) if omitted.
5 {. 100 I.@E. A
990 1599 2797 4550 5073
100 0 1 4 findxth A
990 1599 5073
On Friday, August 26, 2022 at 05:27:46 p.m. EDT, Devon McCormick
<[email protected]> wrote:
I get these timings on J 9.04:
A=. ?1e8#1e3
ts '100 find2 A'
2.4e_6 1536
ts '100 (1{I.@E.) A'
0.19722 8.39853e6
ts '100 ({.@}.@(I.@E.)) A'
0.200139 8.39866e6
(100 find2 A) -: 100 (1{I.@E.) A
1
find2
([: >: i.~) + [ i.~ ] }.~ [: >: i.~
On Fri, Aug 26, 2022 at 3:53 PM 'Mike Day' via General <
[email protected]> wrote:
> Does that include drop, }. ? I suppose it can, since we only need to
> move the pointer to the start... I’ll check on the laptop, once I’ve done
> my Listener xwd.
>
> (Last week’s was the quarterly numeric puzzle, an ingenious construction
> including among all the digits a few decimal points and solidus ( / ) for
> rationals!)
>
> Cheers,
> Mike
>
>
>
> Sent from my iPad
>
> > On 26 Aug 2022, at 20:36, Raul Miller <[email protected]> wrote:
> >
> > Updating arrays without generating a new copy was introduce in J805 --
> > https://code.jsoftware.com/wiki/System/ReleaseNotes/J805
> >
> > So in J701, that approach would indeed be slower (since it's creating
> > a complete copy of the array).
> >
> > Also, virtual blocks (which speed up the }. approach) were introduced
> > in J807. I guess I need to roll up my sleeves and do some
> > benchmarking...
> >
> > Thanks,
> >
> > --
> > Raul
> >
> > On Fri, Aug 26, 2022 at 3:20 PM 'Mike Day' via General
> > <[email protected]> wrote:
> >>
> >> These seem simpler and are possibly quicker, at least in J701 on this
> oldish iPad:
> >> 100 (1{I.@E.) A NB. Fails if there’s no (second) 100 in A
> >> 719
> >> 100 ({.@}.@(I.@E.)) A NB. Returns 0 in that case
> >> 719
> >> Easy to correct for such errors, of course.
> >>
> >> I tried
> >> A =. ?1000000#1000
> >> find2 =: 13 : 'F + ((F=.>:y i. x) }. y) i. x' NB. No direct defs in
> J701
> >> ts'100 find2 A'
> >> 0.020555 8.39091e6
> >> ts'100 (1{I.@E.) A'
> >> 0.011503 76160
> >> ts'100 ({.@}.@(I.@E.)) A'
> >> 0.007626 84864
> >>
> >> Speed a bit better, space quite a lot, if happy with time & space
> tests.
> >>
> >> Only you know if it’s wise to overwrite the first occurrence of V in A!
> >>
> >> Cheers,
> >>
> >> Mike
> >>
> >>
> >>
> >> Sent from my iPad
> >>
> >>> On 26 Aug 2022, at 19:36, Raul Miller <[email protected]> wrote:
> >>>
> >>> i. returns the index of the first occurrence of a value within an
> array.
> >>>
> >>> So, when implementing an algorithm which needs the index of the second
> >>> occurrence of the value within a (large) array, we need to do some
> >>> additional work.
> >>>
> >>> let's say that our array is A, the value is V
> >>>
> >>> F=: A i. V NB. the index of the first occurrence of V
> >>>
> >>> What's the most efficient way of finding the second occurrence?
> >>>
> >>> One possibility is
> >>> S=: (1+F) + ((1+F) }. A) i. V
> >>>
> >>> Another possibility, assuming that V is numeric and not zero, would be
> >>> S=: (0 F} A) i. V
> >>>
> >>> But A is large, so perhaps a faster approach would be:
> >>> S=: {{ while. V~:y{A do. y=. y+1 end. y }} F
> >>>
> >>> (Which has me wishing that S=: A i.!.F V would do the job, though I'm
> >>> not sure that that's completely appropriate...)
> >>>
> >>> But, we can probably eliminate the need to generate a copy of A with a
> >>> little extra work:
> >>>
> >>> A=: 0 F} A
> >>> S=: A i. V
> >>> A=: V F} A
> >>>
> >>> It seems to me that this is probably going to be the fastest approach.
> >>>
> >>> Can anyone think of a faster approach (or something with comparable
> >>> speed which isn't quite so unwieldy?)
> >>>
> >>> Thanks,
> >>>
> >>> --
> >>> Raul
> >>> ----------------------------------------------------------------------
> >>> 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
>
--
Devon McCormick, CFA
Quantitative Consultant
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
