NB. Find the index of some instance of a value
findxth=:4 : 0
'value list'=.y
try. x{,4$.$.value=list
catch. _1
end.
)
_20,\z=:?.100#10
4 6 8 6 5 8 6 6 6 9 3 2 3 1 9 2 7 0 9 5
7 7 9 7 4 8 7 4 2 1 1 0 4 3 9 3 2 7 4 4
0 3 7 5 9 6 3 2 8 2 0 3 5 4 0 0 3 1 5 0
4 0 2 9 2 4 0 0 7 7 5 7 3 1 6 3 1 5 8 9
8 5 3 9 9 8 9 5 1 1 0 4 1 7 3 2 3 4 0 4
NB. Find index of the second occurence of 2
1 findxth 2;z
15
NB. Find index of the third from last of 7
_3 findxth 7;z
69
NB. Try to find index of the tenth of 5 but does not exist
9 findxth 5;z
_1
NB. find the index of the middle or next to middle 8
({~<.@-:@#),4$.$.8=z
48
A=. ?. 1e8#1e3
100 (2 i.~ +/\)@:E. A
1599
timespacex '100 (2 i.~ +/\)@:E. A'
0.213069 1.20796e9
timespacex '100 findxth 2;A'
0.0890775 1.35533e8
On Mon, Aug 29, 2022 at 6:32 PM 'Pascal Jasmin' via General <
gene...@jsoftware.com> wrote:
> 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 <
> devon...@gmail.com> 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 <
> gene...@jsoftware.com> 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 <rauldmil...@gmail.com> 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
> > > <gene...@jsoftware.com> 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 <rauldmil...@gmail.com> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
